hello~ 这里是nihachu（叫niki就好）！
这里是各种算法的模板集合，主要是方便自己背板子用的，后续会不定期更新，希望能帮到和我一样的小伙伴，也希望各路大神可以帮忙指正或补充，thanks~
(部分代码来自网络，若有侵权，请联系我删除，感谢！)
二叉树相关：
深度优先：
前序遍历(根，左子树，右子树)
void dfs(int x){
printf("%d\n",x);
if(ls[x]) dfs(ls[x]);
if(rs[x]) dfs(rs[x]);
}
中序遍历（左子树，根，右子树）
void dfs(int x){
if(ls[x]) dfs(ls[x]);
printf("%d\n",x);
if(rs[x]) dfs(rs[x]);
}
后续遍历（左子树，右子树，根）
void dfs(int x){
if(ls[x]) dfs(ls[x]);
if(rs[x]) dfs(rs[x]);
printf("%d\n",x);
}
广度优先：
层次遍历（从上到下，从左到右依次输出同一层的节点）：
void bfs(int x){
q[++top] = x;
for(int i = 1; i <= top; i ++){
int now = q[i];
printf("%d\n",now);
if(ls[now]) q[++top] = ls[now];
if(rs[now]) q[++top] = rs[now];
}
}
动态规划：
01背包（已降维）
for(int i = 1; i <= n; i ++){
for(int j = m; i >= w[i]; j --){
dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
}
}
完全背包
for(int i = 1; i <= n ; i ++){
for(int j = w[i]; i <= m; j ++){
dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
}
}
背包计数
for(int i = 1; i <= n; i ++){
for(int j = m; i >= w[i]; j --){
dp[j] += dp[j - w[i]];
}
}
（若要求恰好为m，则dp[0]初始化为1，其他均为0）；
二进制拆分（用于多重背包）
for(int i = 1; i <= n1; i ++){
scanf("%d %d %d",&a, &b, &c);
for(int k = 1; k <= c; k <<= 1){
v[++u] = k * a; w[u] = k * b;
c -= k;
}
if(c) v[++u] = a * c,w[u] = b * c;
}
卡时间
快读
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
快写
void write(int x)
{
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
return;
}
手动o2优化
#pragma GCC optimize(2)
并查集
查询 + 路径压缩
int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
合并x，y所属集合
void marge(int x, int y){
int u = find(x), v = find(y);
if(u == v) return;
fa[u] = v;
}
合并x， y 所属集合（按秩合并）
void marge(int x, int y){
int u = find(x), v = find(y);
if(u == v) return;
if(rk[u] > rk[v]) swap(u,v); // 把深度小的合并到深度大的上面；
fa[u] = v;
rk[v] += rk[u] == rk[v]; //如果同级，则合并后深度加一，否则不变；
}
图论
链式前向星
void add(int x, int y){
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
}
图的遍历
dfs：
void dfs(int x){
vis[x] = 1;
printf("%d\n",x);
for(int i = head[x];i;i = nxt[i])
if(!vis[to[i]]) dfs(to[i]);
}
bfs :
void bfs(int x){
z[++top] = x;
for(int i = 1; i <= top; i ++){
int now = z[top ++];
printf("%d\n",now);
for(int j = head[now]; j; j = nxt[j]){
if(!vis[to[j]])
vis[to[j]] = 1, z[++top] = to[j];
}
}
欧拉路径/回路
1)判断是不是欧拉路径/回路
for(int i = 64; i <= 125; i ++){
if(du[i] % 2) jud ++ ; //记录入度为奇数的点
}
if(!jud) //是欧拉回路
if(jud == 2) //是欧拉路径
if(jud && jud != 2)//啥也不是
}
2)欧拉路径/回路的遍历
void dfs(int x){
for(int i = head[x]; i; i = nxt[i])
if(!vis[i]) vis[i] = 1, dfs(to[i]);
printf("%d",x);
}
3）遍历环并记录长度
void dfs(int x,int dt){
if(vis[x]){
ans = min(ans,dt - d[x]);
}
else{
vis[x] = true;
d[x] = dt;
dfs(to[x],dt + 1);
}
}
拓扑排序
for(int i = 1; i <= n ; i ++) if(du[i] == 0) z[++top];
for(int i = 1; i <= top; i ++){
for(int j = head[z[i]]; j; j = nxt[j]){
du[to[j]] --;
if(du[to[j]] == 0) z[++top] = to[j];
}
}
tarjan
void tarjan(int u){
dfn[u] = low[u] = ++dfs_clock;
s.push(u);
for(int i = head[u]; i; i = nxt[i]){
int v = to[i];
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(!sccnum[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]){
scccnt ++;
while(1){
int x = s.top();
s.pop();
sccnum[x] = scccnt;
sccsu[scccnt] += w[x];
// sccsz[scccnt] ++;
if(x == u) break;
}
}
}
tarjan + 拓扑排序 + dp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int dfn[N],low[N],sccnum[N],sccsu[N],sccsz[N],scccnt,dfs_clock;
int head[N],nxt[N],to[N],cnt;
int afhe[N],afnx[N],afto[N],afcnt;
stack <int> s;
int n, m, du[N], val[N], v[N], w[N], ans;
queue<int> q;
void add(int x, int y){
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
}
void afad(int x, int y){
afto[++afcnt] = y;
afnx[afcnt] = afhe[x];
afhe[x] = afcnt;
}
void tarjan(int u){
dfn[u] = low[u] = ++dfs_clock;
s.push(u);
for(int i = head[u]; i; i = nxt[i]){
int v = to[i];
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(!sccnum[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]){
scccnt ++;
while(1){
int x = s.top();
s.pop();
sccnum[x] = scccnt;
sccsu[scccnt] += w[x];
// sccsz[scccnt] ++;
if(x == u) break;
}
}
}
void afbuild(){
for(int i = 1; i <= n; i ++){
for(int u = head[i]; u; u = nxt[u]){
int v1 = to[u];
if(sccnum[i] != sccnum[v1]){
afad(sccnum[i],sccnum[v1]);
// printf("%d %d %d %d e\n",i,v1,sccnum[i],sccnum[v1]);
++du[sccnum[v1]];
}
}
}
}
void topo(){
for(int i = 1; i <= scccnt; i ++) if(du[i] == 0) q.push(i), val[i] += sccsu[i];
while(!q.empty()){
int x = q.front();
q.pop();
// printf("x = %d, val = %d\n",x,val[x]);
for(int i = afhe[x]; i; i = afnx[i]){
int v1 = afto[i];
du[v1] --;
// printf("%d %d\n",val[v1],val[x] + sccsu[v1]);
val[v1] = max(val[v1],val[x] + sccsu[v1]);
// printf("v1 = %d, val = %d\n",v1,val[v1]);
if(du[v1] == 0){
q.push(v1);
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n ; i ++)
scanf("%d",&w[i]);
// return 0;
for(int i = 1, u, v; i <= m ; i ++){
scanf("%d%d",&u,&v);
add(u,v);
}
// return 0;
for(int i = 1; i <= n ; i ++){
if(!dfn[i]) tarjan(i);
}
// for(int i = 1; i <= n ; i ++){
// printf("i = %d, sccnum = %d\n",i,sccnum[i]);
// }
// for(int i = 1; i <= scccnt; i ++){
// printf("num = %d, sum = %d\n",i,sccsu[i]);
// }
afbuild();
topo();
for(int i = 1; i <= scccnt; i ++) ans = max(ans,val[i]);
printf("%d\n",ans);
return 0;
}
数据结构
倍增求LCA
void dfs(int s, int fath){
f[s][0] = fath;
dep[s] = dep[fath] + 1;
for(int u = 1; u <= 20; u ++){
f[s][u] = f[f[s][u - 1]][u - 1];
}
for(int i = head[s]; i; i = nxt[i]){
int t = to[i];
if(t == fath) continue;
dis[t] = dis[s] + v[i];
dfs(t,s);
}
}
int lca(int x, int y){
if(dep[x] < dep[y]){
swap(x,y);
}
for(int i = 20; i >= 0; i --){
if(dep[f[x][i]] >= dep[y]) x = f[x][i];
}
if(x == y) return x;
for(int i = 20; i >= 0; i --){
if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
}
return f[x][0];
}
void ask(int x, int y, int lca){
printf("%d\n",dis[x] + dis[y] - 2 * dis[lca]);
return;
}
树状数组
int lowbit(int x){
return x & (-x);
}
void add(int x, int y){
for(int i = x; i <= n; i += lowbit(i)){
c1[i] += y;
c2[i] += y * x;
}
}
int query(int x){
int res = 0;
for(int i = x; i ; i -= lowbit(i)){
res += c1[i] * (x + 1) - c2[i];
}
return res;
}
ans = query(r) - query(l));
二维树状数组
int lowbit(int x){
return x & (-x);
}
void add(int x,int y, int z){
for(int i = x; i <= n ; i += lowbit(i)){
for(int u = y; u <= m; u += lowbit(u)){
c1[i][u] += z;
c2[i][u] += z * x;
c3[i][u] += z * y;
c4[i][u] += z * x * y;
}
}
}
int query(int x, int y){
int res = 0;
for(int i = x; i; i -= lowbit(i)){
for(int u = y;u; u -= lowbit(u)){
res += (x + 1)*(y + 1)*c1[i][u] - (y + 1)*c2[i][u] - (x + 1)*c3[i][u] + c4[i][u];
}
}
return res;
}
ans = query(a - 1,b - 1) + query(c,d) - query(a - 1,d) - query(c,b - 1);
单调队列
//n为数据个数，m为窗口长度；
for(int i = 1; i <= n; i ++){
if(q[head] <= i - m) head ++;
while(head <= tail && a[q[tail]] < a[i]) tail --;
q[++tail] = i;
ans[i] = a[q[head]];
}
for(int i = m ; i <= n ; i ++){
//对每个窗口中已选出的数据进行处理 ；
}
ST表
void pre() {
logn[1] = 0;
logn[2] = 1;
for (int i = 3; i <= N - 1; i++) { //注意这里一定是N - 1 绝对不能是N
logn[i] = logn[i / 2] + 1;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &st[i][0]);
pre();
for (int u = 1; u <= 20; u++) {
for (int i = 1; i + (1 << u) - 1 <= n; i++) {
st[i][u] = max(st[i][u - 1], st[i + (1 << (u - 1))][u - 1]);
}
}
for (int i = 1; i <= m; i++) {
scanf("%d%d", &l, &r);
int k = logn[r - l + 1];
printf("%d\n", max(st[l][k], st[r - (1 << k) + 1][k]));
}
return 0;
}
二维st表
scanf("%d%d%d",&n,&m,&k1);
for(int i = 1; i <= n ; i ++){
for(int u = 1; u <= m; u ++){
scanf("%d",&st[i][0][u][0]);
}
}
logn[1] = 0;
logn[2] = 1;
for(int i = 3; i <= N - 1; i ++){
logn[i] = logn[i / 2] + 1;
}
for(int k = 0; k <= 20; k ++){
for(int h = 0; h <= 20; h ++){
if(!k && !h) continue;
for(int i = 1; i + (1 << k) - 1 <= n; i ++){
for(int u = 1; u + (1 << h) - 1 <= m; u ++){
if(k) st[i][k][u][h] = max(st[i][k - 1][u][h],st[i + (1 << (k - 1))][k - 1][u][h]);
else st[i][k][u][h] = max(st[i][k][u][h - 1],st[i][k][u + (1 << (h - 1))][h - 1]);
// st[i][k][u][h] = max({st[i][k - 1][u][h - 1],
// st[i + (1 << (k - 1))][k - 1][u][h - 1],
// st[i][k - 1][u + (1 << (h - 1))][h - 1],
// st[i + (1 << (k - 1))][k - 1][u + (1 << (h - 1))][h - 1]});
}
}
}
}
for(int i = 1,x1,y1,x2,y2; i <= k1; i ++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int k1 = logn[x2 - x1 + 1];
int k2 = logn[y2 - y1 + 1];
printf("%d\n",max({st[x1][k1][y1][k2],
st[x2 - (1 << k1) + 1][k1][y1][k2],
st[x1][k1][y2 - (1 << k2) + 1][k2],
st[x2 - (1 << k1) + 1][k1][y2 - (1 << k2) + 1][k2]}));
}
分块
scanf("%lld%lld",&n,&m);
for(int i = 1; i <= n ; i ++){
scanf("%lld",&a[i]);
sum1[i] = sum1[i - 1] + a[i];
}
k = sqrt(n);
for(int i = 1; i <= n / k + 1 ; i ++){
for(int u = 1; u <= k && u <= n; u ++){
pos[u + (i - 1) * k] = i;
if(!pl[i])pl[i] = u + i * k - k;
pr[i] = min(u + i * k - k,n);
}
sum[i] = sum1[pr[i]] - sum1[pl[i] - 1];
}
for(int u = 1; u <= m ; u ++){
scanf("%lld%lld%lld",&opt,&l,&r);
if(opt == 1){
scanf("%lld",&c);
if(pos[r] - pos[l] > 1){
int l1 = pos[l] + 1;
while(l1 < pos[r]) tag[l1] += c,l1 ++;
for(int i = l; i <= pr[pos[l]]; i ++) a[i] += c,sum[pos[i]] += c;//printf("%d %d\n",i,a[i]);
for(int i = r; i >= pl[pos[r]]; i --) a[i] += c,sum[pos[i]] += c;//printf("%d %d\n",i,a[i]);
}
else for(int i = l; i <= r; i ++) a[i] += c,sum[pos[i]] += c;
}
else{
ans = 0;
if(pos[r] - pos[l] > 1){
int l1 = pos[l] + 1;
while(l1 < pos[r]){
ans = ans + sum[l1] + tag[l1] * (pr[l1] - pl[l1] + 1), l1++;
}
for(int i = l; i <= pr[pos[l]]; i ++) ans += a[i] + tag[pos[i]];//printf("%d %d\n",i,ans);
for(int i = r; i >= pl[pos[r]]; i --) ans += a[i] + tag[pos[i]];//printf("%d %d\n",i,ans);
}
else for(int i = l; i <= r; i ++) ans += a[i] + tag[pos[i]] ;
printf("%lld\n",ans);
}
数论
快速幂
注意：不开ll会炸
long long quickpow(long long a, long long b, long long n){
long long res = 1;
while(b){
if(b % 2 == 1) res = res * a % n;
a = a * a % n;
b /= 2;
}
return res % n;
}
矩阵快速幂
const int mod = 1e9 + 7;
const int lim = ;
long long n;
struct mat{
ll m[lim + 2][lim + 2];
};
mat f, ans, t, f1;
void matinit(mat &x){
for(int i = 1; i <= lim; i ++){
for(int u = 1; u <= lim; u ++){
if(i == u) x.m[i][u] = 1ll;
else x.m[i][u] = 0ll;
}
}
}
mat matmul(mat x, mat y){
mat z;
memset(z.m,0,sizeof(z.m));
for(int i = 1; i <= lim ; i ++){
for(int k = 1; k <= lim; k ++){
if(x.m[i][k]){
for(int u = 1; u <= lim; u ++){
z.m[i][u] += x.m[i][k] % mod * y.m[k][u] % mod;
z.m[i][u] %= mod;
}
}
}
}
return z;
}
mat matquickpow(mat a, long long b){
mat res;
matinit(res);
while(b){
if(b & 1) res = matmul(res,a);
a = matmul(a,a);
b >>= 1;
}
return res;
}
欧拉筛
void getprime(){
for(int i = 2; i <= n ; i ++){
if(pflag[i] == false) pri[++top] = i;
for(int q = 1; pri[q] * i <= n ; q ++){
pflag[pri[q] * i] = true;
if(i % pri[q] == 0) break;
}
}
}
算术基本定理
for(int i = 2; i * i <= A ; i ++){
if(A % i != 0) continue;
int num = 0;
while(A % i == 0){
A /= i;
num ++;
}
printf("%d %d\n",i,num);
work(i,B * num + 1);
}
if(A > 1) printf("%d %d",A,1);
exgcd
void exgcd(ll a, ll b, ll &x, ll &y){
if(!b){x = 1, y = 0; return;}
exgcd(b, a % b, y, x);
y -= x * (a / b);
}
lucas定理
ll C(ll n, ll m,ll mod){
if(m > n) return 0;
return jie[n] * qpow(jie[m],mod - 2, mod) % mod * qpow(jie[n - m],mod - 2, mod) % mod;
}
ll lucas(ll n, ll m,ll mod){
if(m == 0) return 1;
return C(n % mod, m % mod,mod) * lucas(n / mod, m / mod,mod) % mod;
}
中国剩余定理
ll crt(){
ll ans = 0;
for(int i = 1; i <= 4; i ++){
ll x, y; exgcd(mod / b[i],b[i],x,y);
x = (x + b[i]) % b[i];
a[i] = (a[i] + b[i]) % b[i];
ans = (ans + qmul(mod / b[i] * x, a[i])) % mod;
}
return ans % mod;
}
线性求逆元
inv[1] = 1;
for (int i = 2; i <= n; i++) {
inv[i] = (p - p / i) * inv[p % i];
inv[i] %= p;
}
求一个数的欧拉函数
int phi(int n){
int ans=n,num=1;
for(int i=2;i*i<=n;i++)
{
if(n%i)continue;
ans=ans/i*(i-1);
while(!(n%i))n/=i;
}
if(n^1) ans=ans/n*(n-1);
return ans;
}
线性筛欧拉函数
void init(int n){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i])p[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt&&i*p[j]<=n;j++){
vis[i*p[j]]=1;
if(!(i%p[j])){
phi[i*p[j]]=phi[i]*p[j];
break;
}
phi[i*p[j]]=phi[i]*phi[p[j]];
}
}
}
字符串
哈希（习惯性采用双哈希）
for (int i = 1; i <= n; i++) {
cin >> s;
unsigned long long t1 = 0, t2 = 0;
for (int u = 0; u < s.size(); u++) {
t1 = s[u] * p1 + t1 * p1;
t2 = s[u] * p2 + t2 * p2;
}
hash1[i] = t1 + t2;
}
KMP
void kmp1(){
int j = 0;
for(int i = 2; i <= lb; i ++){
if(j&& b[i] != b[j + 1]) j = kmp[j];
if(b[i] == b[j + 1]) j ++;
kmp[i] = j;
}
j = 0;
for(int i = 1; i <= la; i ++){
while(j && a[i] != b[j + 1]) j = kmp[j];
if(a[i] == b[j + 1]) j ++;
if(j == lb){
cnt ++;
j = kmp[j];
}
}
}
trie树
void triein(string s) {
int l = s.size();
int p = 0;
for (int i = 0; i < l; i++) {
int c = s[i] - 'a';
if (!nex[p][c])
nex[p][c] = ++cnt;
p = nex[p][c];
// printf("1 %d %d %d\n",i,c,nex[p][c]);
}
++exist[p];
}
int triequery(string s) {
int l = s.size();
int p = 0;
int tot = 0;
for (int i = 0; i < l; i++) {
int c = s[i] - 'a';
p = nex[p][c];
//执行操作
}
return tot;
}
AC自动机
struct trie {
int fail, exist, nex[27];
bool vis;
};
trie tr[N];
void build(string s) {
int p = 0;
int l = s.size();
for (int i = 0; i < l; i++) {
int c = s[i] - 'a';
if (!tr[p].nex[c])
tr[p].nex[c] = ++cnt;
p = tr[p].nex[c];
}
tr[p].exist++;
}
void getfail() {
queue<int> q;
for (int i = 0; i < 26; i++)
if (tr[0].nex[i])
q.push(tr[0].nex[i]);
// for(int i = 0; i < )
while (!q.empty()) {
int now = q.front();
q.pop();
// printf("now = %d\n",now);
for (int i = 0; i < 26; i++) {
if (!tr[now].nex[i])
tr[now].nex[i] = tr[tr[now].fail].nex[i];
else
tr[tr[now].nex[i]].fail = tr[tr[now].fail].nex[i], q.push(tr[now].nex[i]);
}
}
}
int AC(string s) {
int l = s.size();
int res = 0;
int p = 0;
for (int i = 0; i < l; i++) {
int c = s[i] - 'a';
p = tr[p].nex[c];
for (int u = p; tr[u].exist != -1; u = tr[u].fail) {
res += tr[u].exist;
tr[u].exist = -1;
}
}
return res;
}
Manacher
char ms[N];
int l, mana[N], c = -1, r = -1, ans = -10;
int main(){
cin>>s;
for(int i = 1; i <= s.size(); i ++){
ms[i * 2 - 2] = '@';
ms[i * 2 - 1] = s[i - 1];
}
ms[s.size() * 2] = '@';
l = s.size()* 2;
for(int i = 0; i <= l; i ++){
if(i > r){
int pr = i;
while(ms[pr] == ms[i * 2 - pr] && i * 2 - pr >= 0){
mana[i] ++;
pr ++;
}
}
else{
int i1 = c * 2 - i;
int l1 = c * 2 - r;
if(i1 - mana[i1] + 1 > l1){
mana[i] = mana[i1];
}
else{
mana[i] = i1 - l1 + 1;
int r1 = r + 1;
while(ms[r1] == ms[i * 2 - r1] && i * 2 - r1 >= 0){
mana[i] ++;
r1 ++;
}
}
}
if(i + mana[i] - 1 > r) r = i + mana[i] - 1, c = i;
}
for(int i = 0; i <= l; i ++){
ans = max(ans, mana[i] - 1);
}