ACM 模板库 - 开发语言

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

Template For ACM

一. 字符串

标准库

sscanf

sscanf(const char *__source, const char *__format, ...) ：从字符串 __source 里读取变量，比如 sscanf(str,"%d",&a) 。

sprintf

sprintf(char *__stream, const char *__format, ...) ：将 __format 字符串里的内容输出到 __stream 中，比如 sprintf(str,"%d",i) 。

strcmp

int strcmp(const char *str1, const char *str2)：按照字典序比较 str1 str2 若 str1 字典序小返回负值，一样返回 0，大返回正值请注意，不要简单的认为只有 0, 1, -1 三种，在不同平台下的返回值都遵循正负，但并非都是 0, 1, -1

strcpy

char *strcpy(char *str, const char *src) : 把 src 中的字符复制到 str 中， str src 均为字符数组头指针，返回值为 str 包含空终止符号 '\0' 。

strncpy

char *strncpy(char *str, const char *src, int cnt) ：复制至多 cnt 个字符到 str 中，若 src 终止而数量未达 cnt 则写入空字符到 str 直至写入总共 cnt 个字符。

strcat

char *strcat(char *str1, const char *str2) : 将 str2 接到 str1 的结尾，用 *str2 替换 str1 末尾的 '\0' 返回 str1 。

strstr

char *strstr(char *str1, const char *str2) ：若 str2 是 str1 的子串，则返回 str2 在 str1 的首次出现的地址；如果 str2 不是 str1 的子串，则返回 NULL 。

strchr

char *strchr(const char *str, int c) ：找到在字符串 str 中第一次出现字符 c 的位置，并返回这个位置的地址。如果未找到该字符则返回 NULL 。

strrchr

char *strrchr(const char *str, char c) ：找到在字符串 str 中最后一次出现字符 c 的位置，并返回这个位置的地址。如果未找到该字符则返回 NULL 。

KMP

//以 1 为起点, 求nxt数组 nxt[1] = 0; for(int i=2,j=0; i<=n; i++){ while(j > 0 && a[i] != a[j+1]) j = nxt[j]; if(a[i] == a[j+1]) j++; nxt[i] = j; }//求 f 匹配数组 for(int i=1,j=0;i<=m;i++){ while(j > 0 && (j == n || b[i] != a[j+1])) j=nxt[j]; if(b[i] == a[j+1]) j++; f[i] = j; //if(f[i] == n) 此时为A在B中的某一次出现 }

EXKMP

z[i] 是 s 和从 i 开始的 s 的后缀的最大公共前缀长度。

//初始下标为0 for(int i=1,l=0,r=0;i<n;i++){ if(i <= r) z[i] = min(r-i+1, z[i-l]); while(i + z[i] < n && s[z[i]] == s[i + z[i]])++z[i]; if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1; }

Manacher

const int N = 11000000 + 5; char s[N], ma[N*2]; int mp[N*2];//mp[i] 为在s中以对应位置为中心的极大子回文串的总长度+1 int Manacher(char *s, int n){ int len = 0; ma[len++] = '$'; ma[len++] = '#'; for(int i=0;i<n;i++){ ma[len++] = s[i]; ma[len++] = '#'; } ma[len] = 0; int mx = 0, id = 0; int res = 0; for(int i=0;i<len;i++){ mp[i] = mx > i ? min(mp[2*id-i], mx - i) : 1; while(ma[i+mp[i]] == ma[i-mp[i]]) mp[i]++; if(i + mp[i] > mx) { mx = mp[i] + i; id = i; } res = max(res, mp[i] - 1); } return res; } int main(){ scanf("%s", s); printf("%d", Manacher(s, strlen(s))); return 0; }

AC自动机

#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int n; char s[N]; namespace AC{ int tr[N][26],tot; int e[N],fail[N]; queue<int> q; void init(){ for(int i=0;i<=tot;i++){ memset(tr[i],0,sizeof tr[i]); fail[i] = e[i] = 0; } tot = 0; } void insert(char *s){ int u = 0; int len = strlen(s + 1); for(int i=1;i<=len;i++){ if(!tr[u][s[i] - 'a']){ tr[u][s[i] - 'a'] = ++tot; } u = tr[u][s[i] - 'a']; } e[u] ++; } void build(){ for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]); while(q.size()){ int u = q.front();q.pop(); for(int i=0;i<26;i++){ if(tr[u][i])fail[tr[u][i]] = tr[fail[u]][i],q.push(tr[u][i]); else tr[u][i] = tr[fail[u]][i]; } } } int query(char *t){ int u = 0,res = 0; for(int i=1;t[i];i++){ u = tr[u][t[i] - 'a']; for(int j=u;j && e[j] != -1;j = fail[j]) res += e[j],e[j] = -1; } return res; } } int main(){ int T;scanf("%d",&T); while(T--){ scanf("%d",&n); AC::init(); for(int i=1;i<=n;i++)scanf("%s",s+1),AC::insert(s); scanf("%s",s+1); AC::build(); printf("%d\n",AC::query(s)); } return 0; }

后缀数组

1. 倍增

int wa[N],wb[N],wv[N],c[N], rk[N]; int sa[N], height[N]; int cmp(int *r,int a,int b,int l){ return r[a] == r[b] && r[a + l] == r[b + l]; } void build_sa(int *r,int * sa,int n,int m){ int i,j,p,*x = wa,*y = wb, *t; for(i=0;i<m;i++)c[i] = 0; for(i=0;i<n;i++)c[x[i] = r[i]] ++; for(i=1;i<m;i++)c[i] += c[i-1]; for(i=n-1;i>=0;i--)sa[--c[x[i]]] = i; for(j=1,p=1;p<n;j *= 2,m=p){ for(p=0,i=n-j;i<n;i++) y[p++] = i; for(i = 0; i < n; i++)if(sa[i] >= j)y[p++] = sa[i] - j; for(i=0;i<n;i++)wv[i] = x[y[i]]; for(i=0;i<m;i++)c[i] = 0; for(i=0;i<n;i++)c[wv[i]] ++; for(i=1;i<m;i++)c[i] += c[i-1]; for(i=n-1;i>=0;i--)sa[--c[wv[i]]] = y[i]; for(t = x,x = y,y = t,p = 1,x[sa[0]] = 0,i = 1;i<n;i++) x[sa[i]] = cmp(y,sa[i-1],sa[i],j) ? p-1 : p ++; } }

2. DC3

#define F(x) ((x) / 3 + ((x) % 3 == 1 ? 0 : tb)) #define G(x) ((x) < tb ? (x) * 3 + 1 : ((x) - tb) * 3 + 2) int n; char s[N], t[N]; int a[N], wa[N], wb[N], c[N], wv[N], sa[N], be[N]; int rk[N], height[N];int c0(int *r, int a, int b) { return r[a] == r[b] && r[a + 1] == r[b + 1] && r[a + 2] == r[b + 2]; } int c12(int k, int *r, int a, int b) { if (k == 2) return r[a] < r[b] || r[a] == r[b] && c12(1, r, a + 1, b + 1); return r[a] < r[b] || r[a] == r[b] && wv[a + 1] < wv[b + 1]; } void sort(int *r, int *a, int *b, int n, int m) { for (int i = 0; i < n; i++) wv[i] = r[a[i]]; for (int i = 0; i < m; i++) c[i] = 0; for (int i = 0; i < n; i++) c[wv[i]]++; for (int i = 1; i < m; i++) c[i] += c[i - 1]; for (int i = n - 1; i >= 0; i--) b[--c[wv[i]]] = a[i]; } void dc3(int *r, int *sa, int n, int m) { int i, j, *rn = r + n, *san = sa + n, ta = 0, tb = (n + 1) / 3, tbc = 0, p; r[n] = r[n + 1] = 0; for (i = 0; i < n; i++) if (i % 3 != 0) wa[tbc++] = i; sort(r + 2, wa, wb, tbc, m); sort(r + 1, wb, wa, tbc, m); sort(r, wa, wb, tbc, m); for (p = 1, rn[F(wb[0])] = 0, i = 1; i < tbc; i++) rn[F(wb[i])] = c0(r, wb[i - 1], wb[i]) ? p - 1 : p++; if (p < tbc) dc3(rn, san, tbc, p); else for (i = 0; i < tbc; i++) san[rn[i]] = i; for (i = 0; i < tbc; i++) if (san[i] < tb) wb[ta++] = san[i] * 3; if (n % 3 == 1) wb[ta++] = n - 1; sort(r, wb, wa, ta, m); for (i = 0; i < tbc; i++) wv[wb[i] = G(san[i])] = i; for (i = 0, j = 0, p = 0; i < ta && j < tbc; p++) sa[p] = c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j++]; for (; i < ta; p++) sa[p] = wa[i++]; for (; j < tbc; p++) sa[p] = wb[j++]; }

3. 求$height$ 以及 $lcp$

void calheight(int *r, int * sa, int n){ int i, j, k = 0; for (int i = 1; i <= n;i++) rk[sa[i]] = i; for (int i = 0; i < n;height[rk[i++]] = k){ for (k ? k-- : 0, j = sa[rk[i] - 1]; r[i + k] == r[j + k];k++); } } struct RMQ{ int mi[N][20], kk[N]; void init(int n,int *a){ kk[1] = 0; for (int i = 2; i <= n;i++) kk[i] = kk[i / 2] + 1; for (int i = 1; i <= n;i++) mi[i][0] = a[i]; for (int j = 1; (1 << j) <= n;j++){ for (int i = 1; i + (1 << j) - 1 <= n;i++){ mi[i][j] = min(mi[i + (1 << (j - 1))][j - 1], mi[i][j - 1]); } } } int query(int l,int r){ int k = kk[r - l + 1]; return min(mi[l][k], mi[r - (1 << k) + 1][k]); } } rmq;

后缀自动机

最多 $2n$ 个点，$3n$ 条边

const int N = 200000 + 5; //N为字符串长度两倍 const int P = 26;//P过大时改用unordered_map char s[N], a[N]; struct node{ int link, len, trans[P]; void clear(){ memset(trans,0, sizeof trans); link = len = 0; } }; struct SAM{ node S[N]; int p, np, size; int b[N], c[N]; SAM():p(1),np(1),size(1){} void clear(){ for(int i=0;i<=size;i++)S[i].clear(); np = size = p = 1; } void insert(char ch){ int x = ch - 'a'; np = ++size; S[np].len = S[p].len + 1; while(p != 0 && !S[p].trans[x]) S[p].trans[x] = np, p = S[p].link; if(p == 0)S[np].link = 1; else{ int q, nq; q = S[p].trans[x]; if(S[q].len == S[p].len + 1) S[np].link = q; else{ nq = ++size; S[nq] = S[q]; S[nq].len = S[p].len + 1; S[np].link = S[q].link = nq; while(p != 0 && S[p].trans[x] == q) S[p].trans[x] = nq, p = S[p].link; } } p = np; } // 基数排序，从size倒序遍历可以自底向上更新，多组数据时，c 数组要更新 void sort(){ for(int i=1;i<=size;i++)++c[S[i].len]; for(int i=1;i<=size;i++)c[i] += c[i-1]; for(int i=1;i<=size;i++)b[c[S[i].len]--] = i; } }sam;

回文自动机

namespace PAT{ const int SZ = 6e5+10; int ch[SZ][26],fail[SZ],cnt[SZ],len[SZ],tot,last; int be[SZ],ok[SZ]; void init(int n){ for(int i=0;i<=n+10;i++){ fail[i] = cnt[i] = len[i] = 0; for(int j=0;j<26;j++)ch[i][j] = 0; be[i] = ok[i] = 0; } s[0] = -1;fail[0] = 1;last = 0; len[0] = 0;len[1] = -1;tot = 1; } inline int newnode(int x){ len[++tot] = x;return tot; } inline int getfail(char *s, int x,int n){ while(s[n-len[x]-1] != s[n])x = fail[x]; return x; } void create(char *s){ s[0] = -1; for(int i=1;s[i];++i){ int t = s[i]- 'a'; int p = getfail(s, last,i); if(!ch[p][t]){ int q = newnode(len[p]+2); fail[q] = ch[getfail(s, fail[p],i)][t]; ch[p][t] = q; } ++cnt[last = ch[p][t]]; } } void solve(){ for(int i=tot;i>=2;i--){ if(be[i] == 0)be[i] = i; while(be[i] >= 2 && len[be[i]] > (len[i] + 1)/2)be[i] = fail[be[i]]; if(len[be[i]] == (len[i]+1)/2)ok[i] = 1; be[fail[i]] = be[i]; } for(int i=tot;i>=2;i--){ cnt[fail[i]] += cnt[i]; if(ok[i]) res[len[i]] += cnt[i]; } } }

二. 数论

筛质数

$O(\sum_{质数p\le n}{n\over p}) = O(nlogn)$

void primes(int n){ memset(v,0,sizeof v); for(int i=2;i<=n;i++){ if(v[i])continue; for(int j=i;j<=n/i;j++)v[i*j] = 1; } }

$O(n)$

第一种，v[i] 为 i 的最小质因子

int v[MAX_N],prime[MAX_N]; void primes(int n){ memset(v,0,sizeof v); m = 0; for(int i=2;i<=n;i++){ if(v[i] == 0){v[i] = i; prime[++m] = i;} for(int j=1;j<=m;j++){ if(prime[j] > v[i] || prime[j] > n/i)break; v[i*prime[j]] = prime[j]; } } }

第二种: v[i] 表示 i 是否为质数

int v[MAX_N],prime[MAX_N]; void primes(int n){ memset(v,0,sizeof v); m = 0; for(int i=2;i<=n;i++){ if(v[i] == 0) prime[++m] = i; for(int j=1;j<=m;j++){ if(prime[j] > n / i)break; v[i*prime[j]] = 1; if(i % prime[j] == 0)break; } } }

质因子分解

void divide(int n){ m = 0; for(int i=2;i<=sqrt(n);i++){ if(n % i == 0){ p[++m] = i,c[m] = 0; while(n % i == 0)n /= i,c[m]++; } } if(n > 1) p[++m] = n,c[m] = 1; }

正因数集合

一个整数N的约数上界约为$2\sqrt(N)$

$1\sim N$ 每个数的约数个数的总和约为$NlogN$

vector<int> fac[500010]; for(int i=1;i<=n;i++) for(int j=1;j<=n/i;j++) fac[i*j].push_back(i);

Miller Rabin Prollard Rho

/* Miller_Rabin 算法进行素数测试速度快可以判断一个 < 2^63 的数是不是素数 */ const int S = 8; typedef long long ll; //计算 res = (a*b)%c ll mult_mod(ll a, ll b, ll c){ a %= c; b %= c; ll res = 0; ll tmp = a; for (; b;b>>=1){ if(b & 1) { res += tmp; if(res > c) res -= c; } tmp <<= 1; if(tmp > c) tmp -= c; } return res; } ll pow_mod(ll a,ll b, ll mod){ ll res = 1; a %= mod; for (; b;b>>=1){ if(b & 1) res = mult_mod(res, a, mod); a = mult_mod(a, a, mod); } return res; } /* 通过 a^(n-1)=1(mod n)来判断 n 是不是素数 n - 1 = x * 2^t 中间使用二次判断是合数返回true，不一定是合数返回false */ bool check(ll a,ll n,ll x,ll t){ ll res = pow_mod(a, x, n); ll last = res; for (int i = 1; i <= t;i++){ res = mult_mod(res, res, n); if(res == 1 && last != 1 && last != n-1) return true; last = res; } if(res != 1) return true; return false; } /* Miller_Rabin 算法是素数返回true 不是素数返回false */ bool Miller_Rabin(ll n){ if(n < 2) return false; if(n == 2) return true; if((n&1) == 0) return false; ll x = n - 1; ll t = 0; while((x & 1) == 0) { x >>= 1, t++; } for (int i = 0; i < S;i++){ ll a = rand() % (n - 1) + 1; if(check(a,n,x,t)) return false; } return true; } /* Pollard_rho 算法进行质因数分解 */ ll fac[100]; int tol; ll gcd(ll a,ll b){ ll t; while(b){ t = a; a = b; b = t % b; } if(a >= 0) return a; else return -a; } //找出一个因子 ll pollard_rho(ll x,ll c){ ll i = 1, k = 2; ll x0 = rand() % (x - 1) + 1; ll y = x0; while(1){ i++; x0 = (mult_mod(x0, x0, x) + c) % x; ll d = gcd(y - x0, x); if(d != 1 && d != x) return d; if(y == x0) return x; if(i == k) { y = x0; k += k; } } } //对 n 进行质因数分解，存入factor，k设置为107左右 void findfac(ll n,int k){ if(n == 1) return; if(Miller_Rabin(n)){ fac[tol++] = n; return; } ll p = n; int c = k; while(p >= n) p = pollard_rho(p, c--); findfac(p, k); findfac(n / p, k); } ll a[100010]; ll cal(ll n, ll x){ ll ans = 0; while(n / x){ ans += n / x; n /= x; } return ans; } unordered_map<ll, int> mp; int main(){ int T; ll n,x,y; scanf("%d", &T); while(T--){ tol = 0; mp.clear(); scanf("%lld%lld%lld", &n, &x, &y); for (int i = 1; i <= n;i++){ scanf("%lld", &a[i]); } ll res = 1ll << 60; findfac(x, 107); for (int i = 0; i < tol;i++) mp[fac[i]]++; for (auto it = mp.begin(); it != mp.end(); it++) { ll num = 0; for (int i = 1; i <= n; i++) { num += cal(a[i], it->first); } res = min(res, (cal(y, it->first) - num) / it->second); } printf("%lld\n", res); } }

高斯消元

const int N = 100 + 5; int n; double d[N][N], res[N];int gauss(int n, int m){ int row = 1; for(int col = 1; col <= n; col++){ for(int i=row;i<=n;i++) { if(fabs(d[i][col]) > 1e-12) { for(int j=col;j<=m;j++) swap(d[i][j], d[row][j]); } } if(fabs(d[row][col]) < 1e-12) break; for(int j=m;j>=col;j--) d[row][j] /= d[row][col]; for(int i=1;i<=n;i++) if(i != row){ // 只限定 i!=row即可，不用画蛇添足 for(int j=m;j>=col;j--){ d[i][j] -= d[i][col] * d[row][j]; } } row++; } for(int i=1;i<=n;i++) { if(fabs(d[i][i]) < 1e-12) return -1; res[i] = d[i][m] /= d[i][i]; } return 1; }int main(){ scanf("%d", &n); for(int i=1;i<=n;i++){ for(int j=1;j<=n+1;j++){ scanf("%lf", &d[i][j]); } } if(gauss(n, n+1) == -1) puts("No Solution"); else { for(int i=1;i<=n;i++) printf("%.2f\n", res[i]); } return 0; }

矩阵快速幂

struct matrix{ int r, c; ll s[N][N]; matrix(int r=0,int c=0):r(r),c(c){ memset(s, 0, sizeof s); } }; matrix operator*(const matrix&a, const matrix&b){ matrix c = matrix(a.r, b.c); for (int i = 0; i < c.r;i++){ for (int j = 0; j < c.c;j++) for (int k = 0; k < a.c;k++) c.s[i][j] += a.s[i][k] * b.s[k][j]; } return c; } matrix power(matrix a,int b){ matrix res = a; b--; for (; b;b>>=1){ if(b & 1) res = res * a; a = a * a; } return res; }

欧拉函数

$N = p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$

$\phi(N) = N * {p_1-1 \over p_1} * {p_2 - 1 \over p_2} * \cdots {p_m-1\over p_m} = N * \prod_{质数p|N}(1-{1\over p})$

性质：

$\forall n>1,1\sim n$ 中与n互质的数的和为$n*\psi (n)/2$
若a，b互质，则$\psi (ab) = \psi(a)\psi(b)$
若$f$ 是积性函数，且在算术基本定理中 $n = \prod _{i=1}^m p_i^{c_i}$ ，则$f(n) = \prod _{i=1}^mf(p_i^{c_i})$
若 $p|n$ 且 $p^2|n$ ，则 $\psi(n) = \psi (n/p) * p$
若 $p|n$ 但 $n \% p^2 != 0$ , 则 $\psi(n) = \psi(n/p) * (p-1)$
$\Sigma_{d|n}\psi(d) = n$

积性函数：如果当a，b互质时，有 $f(ab) = f(a)*f(b)$ 那么称函数 $f$ 为积性函数

欧拉定理：若正整数 a，n互质，则 $a^{\psi(n)} \equiv 1\pmod n$

当n为质数时，$\psi (n)$ 为 $n-1$，当a不为n的倍数时，a与n互质，故有欧拉定理成立：$a^{n-1} \equiv 1 \pmod n$ ，左右两边同乘a有$a^n\equiv a \pmod n$ 。当a为n的倍数时，该式依然成立

费马小定理：若 p 是质数，则对于任意整数a，有 $a^p \equiv a \pmod p$

int phi(int n){ int ans = n; for(int i=2;i*i<=n;i++){ if(n % i == 0){ ans = ans / i * (i - 1); while(n % i == 0) n /= i; } } if(n > 1)ans = ans / n * (n - 1); return ans; }

void enlur(int n){ for(int i=2;i<=n;i++)phi[i] = i; for(int i=2;i<=n;i++) if(phi[i] == i) for(int j = i;j <= n;j += i) phi[j] = phi[j] / i * (i - 1); }

const int N = 10000010; int primes[N],v[N],m,n; ll phi[N]; void prime(){ phi[1] = 1; for(int i=2;i<=n;i++){ if(!v[i]){ primes[++m] = i; phi[i] = i-1; } for(int j=1;j<=m;j++){ if(primes[j] > n / i)break; v[primes[j] * i] = 1; if(i % primes[j] == 0){ phi[i*primes[j]] = phi[i] * primes[j]; break; }else{ phi[i*primes[j]] = phi[i] * (primes[j]-1); } } } }

逆元

扩展欧几里得

typedef long long ll; void extgcd(ll a,ll b,ll& d,ll& x,ll& y){ if(!b){ d=a; x=1; y=0;} else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); } } ll inverse(ll a,ll n){ ll d,x,y; extgcd(a,n,d,x,y); return d==1?(x+n)%n:-1; }

费马小定理
当模 p 不是素数时候需要用到欧拉定理
线性递推逆元

$inv[i] = (P - \lfloor P/i \rfloor) * inv[P\%i] \% P$

typedef long long ll; const int N = 1e5 + 5; ll fac[N], inv[N], fac_inv[N]; void getFac(int n){ fac[0] = fac_inv[0] = 1; for(int i=1;i<=n;i++) fac[i] = fac[i-1] * i % mod; inv[1] = 1; for(int i=2;i<=n;i++) inv[i] = 1ll * (mod-mod/i)*inv[mod%i] % mod; for(int i=1;i<=n;i++) fac_inv[i] = fac_inv[i-1] * inv[i] % mod; }

组合数学相关

一. 组合数学性质

$C_n^m = C_n^{n-m}$
$C_n^m = C_{n-1} ^ m + C_{n-1} ^{m-1}$ (可用杨辉三角推到)
$C_n^0 + C_n^1 + C_n^2 + C_n^3 + \cdots + C_n^n = 2^n$
$\sum_{i=0}^m C_n^i C_m^{m-i} = C_{m+n}^m(n \geq m)$ 分开取和一起取是一样的（也可以理解成先取和后取）

二. 多重集的排列数

设集合 $S = \{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$ ,是由$n_1$ 个$a_1$，$n_2$个$a_2$$\cdots$ $n_k$ 个 $a_k$ 组成的多重集。S的全排列个数为：

\[n!\over n_1!n_2! \cdots n_k!
\]

三. 多重集组合数

n种不一样的球，每种球的个数是无限的，从中选k个出来组成一个多重集（不考虑元素的顺序），产生的不同多重集的数量为：

$C_{n+k-1} ^ {k-1}$

四. 不相邻的排列

$1\sim n$ 这 n 个自然数中选k 个，这k 个数中任何两个数不相邻数的组合有 $C_{n-k+1}^k$种

五. 错位排列

胸口贴着编号为$1,2,\cdots,n$ 的 n 个球员分别住在编号为$1,2,\cdots ,n$ 的n个房间里面。现规定每个人住一个房间，自己的编号不能和房间的编号一样

$d[n] = (n-1)(d[n-1] + d[n-2]) (n\ge 3)$

$d[n] = n \times d[n-1]+ (-1)^n$

六. 圆排列

n 个人全部来围成一圈为 $Q_n^n$ ，其中已经排好的一圈，从不同位置断开，又变成不同的队列。所以:$Q_n^n \times n = A_n^n \rightarrow Q_n = (n-1)!$

由此可知部分圆排列为 $Q_n^r = {A_n^r \over r} = {n! \over r \times (n-r)!}$

七. 卢卡斯定理

$C_n^k = C_{n\over p}^{k\over p} * C_{n\%p}^{k\%p} \pmod p$

#include <bits/stdc++.h> using namespace std; const int N = 2e5+10; typedef long long ll; int T; ll n,m,p; ll j[N]; ll pow(ll a,ll b ,ll p){ ll res = 1; for(;b;b>>=1){ if(b & 1) res = (res * a)%p; a = a * a % p; } return res; } ll C(ll n,ll m){ if(m > n)return 0; return ((j[n] * pow(j[m],p-2,p))%p * pow(j[n-m],p-2,p)%p); } ll Lucas(ll n,ll m){ if(!m)return 1; return C(n%p,m%p)*Lucas(n/p,m/p)%p; } int main(){ j[0] = 1; cin>>T; while(T--){ cin >> n >> m >> p; for(int i=1;i<=p;i++) j[i] = j[i-1] * i % p; cout<<Lucas(n+m,n)<<endl; } return 0; }

八. 斯特林数

把n个不同的球分成r个非空循环排列的方法数
递推形式 : $s(n,r) = (n-1)s(n-1,r) + s(n-1,r-1),n>r \ge 1$
把n个不同的球放到r个盒子里，假设没有空盒，则放球方案数记作S(n,r)，称为第二类Stirling数
$S(n,r) = rS(n-1,r) + S(n-1,r-1),n>r\ge 1$

九. 莫比乌斯函数

$\mu$ 为莫比乌斯函数

\[\mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因子}\\ (-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\\ \end{cases}
\]

通俗的讲，当n包含相等的质因子时，$\mu(N)=0$ 。当N的所有质因子各不相等时，若N有偶数个质因子，$\mu(N) = 1$，若N有奇数个质因子，$\mu(N)=-1$ 。

若只求一项Mobius函数，则分解质因数即可计算，若求 $1\sim N$的每一项Mobius函数，可以利用线性筛法来求mobius函数

void getMu(){ mu[1] = 1; for(int i=2;i<=n;++i){ if(!v[i])p[++tot] = i,mu[i] = -1; for(int j=1;j<=tot && i * p[j] <= n;++j){ flg[i * p[j]] = 1; if(i % p[j] == 0){ mu[i * p[j]] = 0; break; } mu[i * p[j]] = - mu[i]; } } } void getMu(int n) { mu[1] = 1; for (int i = 2; i <= n; ++i) { if (!flg[i]) p[++tot] = i, mu[i] = -1; for (int j = 1; j <= tot && i * p[j] <= n; ++j) { flg[i * p[j]] = 1; if (i % p[j] == 0) { mu[i * p[j]] = 0; break; } mu[i * p[j]] = -mu[i]; } } }

十. 把n个物品分成m堆

n个相同物品分成m个相同的堆，可以空

$R(n,m) = \sum_{k=1}^mS(n,k)$

把n 个相同物品分成m个相同的堆，不可空

$S(n,m) = S(n-1,m-1) + S(n-m,m)$

把n个相同物品分成m个不同的堆，可空

$T(n,m) = C_{n+m-1}^{m-1}$

把n个相同物品分成m个不同的堆，不可空

$U(n,m) = C_{n-1}^{m-1}$

把n 个不同物品分成m 个相同的堆，可空

$P(n,m) = \sum_{k=1}^mQ(n,k)$

性质：$\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty({1\over 1-x^k})$

应用：

集合的划分数（$B_n$ 是基数为n 的集合的划分方法的数目，贝尔数）。

递推：$B_{n+1} = \sum_{k=0}^n(_k^n)B_k$
$Dobinski$ 公式： $B_n = {1\over e}\sum_{k=0}^\infty{k^n\over k!}$
$Touchard$ 同余：$B_{p+n} \equiv B_n+B_{n+1} \pmod p$
第二类$Stirling$ 数的和$B_n = \sum_{k=1}^nS(n,k)$
指数母函数：$\sum_{n=0}^\infty {B_n\over n!}x^n = e^{e^x-1}$
贝尔三角形&Aitken阵列&Peirce三角形

第一行第一项为1 ($a_{1,1} = 1$)
对于$n>1$，第$n$ 行第一项等同于第 $n-1$ 行最后一项（$a_{n,1} = a_{n-1,n-1}$
对于$m,n>1$ ，$a_{n,m} = a_{n,m-1} + a_{n-1,m-1}$

\[\begin{matrix}
1\\
1&2\\
2&3&5\\
5&7&10&15\\
15&20&27&37&52\\
52&67&87&114&151&203\\
203&255&322&409&523&674&877\\
877&1080&1335&1657&2066&2589&3263&4140\\
\end{matrix}
\]

每行首项是贝尔数。每行之和是第二类$Stirling$数

把n 个不同的物品分成m 个相同的堆，不空

$Q(n,m) = mQ(n-1,m) + Q(n-1,m-1)$

三. 数据结构

并查集

带删除并查集

#include <bits/stdc++.h> using namespace std; const int N = 4000010; int fa[N],to[N],sz[N],cnt,a[N],b[N],tot; int n,m,k,x,y; int ok[N]; int find(int x){ return x == fa[x]?x:fa[x] = find(fa[x]); } void merge(int x,int y){ int a = find(to[x]); int b = find(to[y]); if(a==b) return; fa[b] = a; sz[a] += sz[b]; sz[b] = 0; } void update(int x,int y){ sz[find(to[x])]--; to[x] = ++cnt; sz[cnt] = 1; fa[cnt] = cnt; merge(x,y); } int main(){ scanf("%d%d",&n,&m);cnt = n; for(int i=1;i<=n;i++)fa[i] = i,to[i] = i,sz[i] = 1; for(int i=1;i<=m;i++){ scanf("%d%d",&k,&x);if(k!=3)scanf("%d",&y); if(k == 5){ a[++tot] = x; b[tot] = y;continue; } if(k == 1)merge(x,y); if(k == 2)update(x,y); if(k == 4){ if(find(to[x]) == find(to[y]))printf("Yes\n"); else printf("No\n"); } if(k == 3)printf("%d\n",sz[find(to[x])]-1); } for(int i=1;i<=tot;i++){ if(find(to[a[i]]) == find(to[b[i]])) ok[find(to[a[i]])] = 1; } int res = -1; for(int i=1;i<=n;i++) if(!ok[find(to[i])])res = max(res,sz[find(to[i])]); cout<<res<<endl; return 0; }

可持久化并查集

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; #define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0) void err() { cout << "\033[39;0m" << endl; } template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); } const int N = 200000 + 5;int n, m; struct TreeNode{ int l, r; }; int root[N]; class Union_Find{ public: int fa[N*30], dep[N*30], tot; TreeNode t[N*30]; void build(int &p, int l, int r){ p = ++tot; if(l == r){ fa[p] = l; return; } int mid = l + r >> 1; build(t[p].l, l, mid); build(t[p].r, mid+1, r); } void change(int last, int &p, int l, int r, int pos, int val){ p = ++tot; t[p].l = t[last].l, t[p].r = t[last].r; if(l == r){ fa[p] = val; dep[p] = dep[last]; return; } int mid = (l + r) >> 1; if(pos <= mid) change(t[last].l, t[p].l, l, mid, pos, val); else change(t[last].r, t[p].r, mid + 1, r, pos, val); } int getIndex(int p, int l, int r, int pos){ if(l == r) return p; int mid = l + r >> 1; if(pos <= mid) return getIndex(t[p].l, l, mid, pos); else return getIndex(t[p].r, mid+1, r, pos); } void add(int p, int l, int r, int pos){ if(l == r){ dep[p] ++; return; } int mid = l + r >> 1; if(pos <= mid) add(t[p].l, l, mid, pos); else add(t[p].r, mid+1, r, pos); } // find 返回的是祖先节点的下标 int find(int p, int pos){ int index = getIndex(p, 1, n, pos); if(fa[index] == pos) return index; else return find(p, fa[index]); } void merge(int last, int &p, int x, int y){ int fax = find(p, x), fay = find(p, y); if(fa[fax] == fa[fay]) return; if(dep[fax] > dep[fay]) swap(fax, fay); change(last, p, 1, n, fa[fax], fa[fay]); if(dep[fax] == dep[fay]) add(p, 1, n, fa[fay]); } }uf;int main(){ scanf("%d%d", &n, &m); uf.build(root[0], 1, n); for(int i=1;i<=m;i++){ int op, x, y; scanf("%d%d", &op, &x); if(op == 1){ scanf("%d", &y); root[i] = root[i-1]; uf.merge(root[i-1], root[i], x, y); } else if(op == 2) root[i] = root[x]; else{ scanf("%d", &y); root[i] = root[i-1]; int fax = uf.find(root[i], x); int fay = uf.find(root[i], y); if(uf.fa[fax] == uf.fa[fay]) puts("1"); else puts("0"); } } return 0; }

带权删除并查集

2019南昌A

k a b: merge the tribe containing the a-th family and the tribe containing the b-th family;
k a: make the a-th family into extermination;
k a b: the a-th family moves away from their tribe and join in the tribe containing the b-th family;
k a b: report that if the a-th family and the b-th one belong to the same tribe;
k a: report the total number of families in the tribe which contains the a-th family.

树链剖分

int fa[N], dep[N], sz[N], son[N], top[N], dfn[N], rnk[N], cnt; int head[N], ver[N << 1], nxt[N << 1], tot; void dfs1(int x){ sz[x] = 1; son[x] = 0; for (int i = head[x]; i;i=nxt[i]){ int y = ver[i]; if(y == fa[x]) continue; dep[y] = dep[x] + 1; fa[y] = x; dfs1(y); sz[x] += sz[y]; if(sz[y] > sz[son[x]]) son[x] = y; } } void dfs2(int x,int tp){ dfn[x] = ++cnt; rnk[cnt] = x; top[x] = tp; if(son[x]) dfs2(son[x], tp); for (int i = head[x]; i;i=nxt[i]){ int y = ver[i]; if(y == fa[x] || y == son[x]) continue; dfs2(y, y); } } ll querysum(int x,int y){ ll res = 0; while(top[x] != top[y]){ if(dep[top[x]] < dep[top[y]]) swap(x, y); res = (res + query(1, dfn[top[x]], dfn[x])) % mod; x = fa[top[x]]; } if(dep[x] < dep[y]) swap(x, y); res = (res + query(1, dfn[y], dfn[x])) % mod; return res; }

左偏树

#include <bits/stdc++.h> using namespace std; const int maxn = 100010; int tot,v[maxn],l[maxn],r[maxn],d[maxn]; int n,m,fa[maxn],del[maxn]; int merge(int x,int y){ if(!x)return y; if(!y)return x; if(v[x] > v[y] || (v[x] == v[y] && x > y)) swap(x,y); r[x] = merge(r[x],y); fa[l[x]] = fa[r[x]] = fa[x] = x; if(d[l[x]] < d[r[x]]) swap(l[x],r[x]); d[x] = d[r[x]] + 1; return x; } int init(int x){ tot ++; v[tot] = x; l[tot] = r[tot] = d[tot] = 0; } int insert(int x,int y){ return merge(x,init(y)); } int top(int x){ return v[x]; } int pop(int x){ del[x] = 1; fa[l[x]] = l[x]; fa[r[x]] = r[x]; return fa[x] = merge(l[x],r[x]); } int find(int x){ return x == fa[x] ? x : fa[x] = find(fa[x]); } int main(){ d[0] = -1; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ int x;scanf("%d",&x); v[i] = x; fa[i] = i; } while(m--){ int op,x,y; scanf("%d",&op); if(op == 1){//合并，若删除或者xy在同一个堆则无视 scanf("%d%d",&x,&y); if(del[x] || del[y])continue; x = find(x);y = find(y); if(x == y)continue; fa[x] = fa[y] = merge(x,y); } else{//输出所在堆的最小数，并将其删除 scanf("%d",&x); if(del[x]){ puts("-1");continue; } x = find(x); printf("%d\n",v[x]); //cout << l[x] << ' ' << r[x] << endl; pop(x); } } return 0; }

树哈希

Method I (Hacked)

$f_{now} = size_{now} \times \sum f_{{son}_{now,i}} \times seed^{i-1}$

注：要对子节点以 f 关键字排序

Method II (Hacked)

$f_{now}=\bigoplus f_{son_{now,i}}\times seed+size_{son_{now,i}} $

Method III

$f_{now} = 1 + \sum f_{{son}_{now,i}} \times primes(size_{{son}_{now,i}})$

线段树合并

const int N = 200000 + 5; int head[N], ver[N<<1], nxt[N<<1], tot; int dep[N], f[N][20]; int n, m; void add(int x, int y){ ver[++tot] = y, nxt[tot] = head[x], head[x] = tot; } void dfs(int x, int fa){ for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(y == fa) continue; f[y][0] = x; dep[y] = dep[x] + 1; dfs(y, x); } } int lca(int x, int y){ if(dep[x] > dep[y]) swap(x, y); for(int i=19;i>=0;i--) if(dep[f[y][i]] >= dep[x]) y = f[y][i]; if(x == y) return x; for(int i=19;i>=0;i--) if(f[y][i] != f[x][i]) y = f[y][i], x = f[x][i]; return f[x][0]; } struct SegTree{ int l, r; int mx, pos; }t[N*40]; int rt[N], cnt; int res[N], st[N*40], top; int newnode(){ if(top) return st[top--]; return ++cnt; } void rubbish(int p){ st[++top] = p; t[p].l = t[p].r = t[p].mx = t[p].pos = 0; } void pushup(int p){ int ls = t[p].l, rs = t[p].r; if(t[ls].mx >= t[rs].mx){ t[p].mx = t[ls].mx; t[p].pos = t[ls].pos; } else { t[p].mx = t[rs].mx; t[p].pos = t[rs].pos; } } void change(int &p, int l, int r, int pos, int val){ if(!p) p = newnode(); if(l == r){ t[p].mx += val; if(t[p].mx) t[p].pos = l; else t[p].pos = 0; return ; } int mid = l + r >> 1; if(pos <= mid) change(t[p].l, l, mid, pos, val); else change(t[p].r, mid+1, r, pos, val); pushup(p); } int merge(int u, int v, int l, int r){ if(!u) return v; if(!v) return u; int w = newnode(); if(l == r){ t[w].mx = t[u].mx + t[v].mx; if(t[w].mx)t[w].pos = l; return w; } int mid = l + r >> 1; t[w].l = merge(t[u].l, t[v].l, l, mid); t[w].r = merge(t[u].r, t[v].r, mid + 1, r); pushup(w); rubbish(u);rubbish(v); return w; } void get(int x, int fa){ for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(y == fa) continue; get(y, x); rt[x] = merge(rt[x], rt[y], 1, 1e5); } res[x] = t[rt[x]].pos; } int main(){ scanf("%d%d", &n, &m); for(int i=1;i<n;i++){ int x, y;scanf("%d%d", &x, &y); add(x, y); add(y, x); } dep[1] = 1; dfs(1, 0); for(int j=1;j<20;j++)for(int i=1;i<=n;i++) f[i][j] = f[f[i][j-1]][j-1]; while(m--){ int x, y, z; scanf("%d%d%d", &x, &y, &z); int t = lca(x, y); if(t != x && t != y){ change(rt[x], 1, 1e5, z, 1); change(rt[y], 1, 1e5, z, 1); change(rt[t], 1, 1e5, z, -1); change(rt[f[t][0]], 1, 1e5, z, -1); }else if(t == x){ change(rt[y], 1, 1e5, z, 1); change(rt[f[t][0]], 1, 1e5, z, -1); }else if(t == y){ change(rt[x], 1, 1e5, z, 1); change(rt[f[t][0]], 1, 1e5, z, -1); } } get(1, 0); for(int i=1;i<=n;i++) printf("%d\n", res[i]); return 0; }

洛谷P5494

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; #define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0) void err() { cout << "\033[39;0m" << endl; } template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); } const int N = 200000 + 5; /* 0, p, x, y, p 中[x,y] 中的数字放入新的可重集合 1, p, t 将 t 放入 p，并且清空 t 2, p, x, q, 在 p 中放入 x 个q 3，p, x, y，查询p中[x,y] 4, p,k，查询p中第 k 小的数字 */ int n, m; struct SegTree{ int ls, rs; ll sum;// 区间数字个数 }t[N*40]; int root[N]; int st[N*40], top, tot; int newnode(){ if(top) return st[top--]; return ++tot; } void rubbish(int p){ st[++top] = p; t[p].ls = t[p].rs = t[p].sum = 0; } // 0 p x y void build(int &p, int &q, int l, int r, int x, int y){ if(!q) return ; if(l >= x && r <= y){ // 信息要传输完整，除了考虑sum，还要考虑其他 p = q; q = 0; return; } if(!p) p = newnode(); int mid = l + r >> 1; if(mid >= x) build(t[p].ls, t[q].ls, l, mid, x, y); if(mid < y) build(t[p].rs, t[q].rs, mid+1, r, x, y); t[q].sum = t[t[q].ls].sum + t[t[q].rs].sum; t[p].sum = t[t[p].ls].sum + t[t[p].rs].sum; }// 1 p q int merge(int p, int q, int l, int r){ if(!p || !q) return p | q; int w = newnode(); t[w].sum = t[p].sum + t[q].sum; if(l == r){ //t[w].sum = t[p].sum + t[q].sum; return w; } int mid = l + r >> 1; t[w].ls = merge(t[p].ls, t[q].ls, l, mid); t[w].rs = merge(t[p].rs, t[q].rs, mid+1, r); rubbish(p); rubbish(q); //t[w].sum = t[t[w].ls].sum + t[t[w].rs].sum; return w; } // 2, p, x, q; void change(int &p, int l, int r, int pos, int num){ if(!p) p = newnode(); if(l == r){ t[p].sum += num;return; } int mid = l + r >> 1; if(pos <= mid) change(t[p].ls, l, mid, pos, num); else change(t[p].rs, mid+1, r, pos, num); t[p].sum = t[t[p].ls].sum + t[t[p].rs].sum; } // 3 p x y ll ask(int p, int l, int r, int x, int y){ if(l >= x && r <= y) return t[p].sum; int mid = l + r >> 1; ll res = 0; if(t[p].ls && x <= mid) res += ask(t[p].ls, l,mid, x, y); if(t[p].rs && mid < y) res += ask(t[p].rs, mid+1, r, x, y); return res; } // 4 p, k ll ask(int p, int l, int r, ll k){ if(k > t[p].sum || k <= 0) return -1; if(l == r) return l; int mid = l + r >> 1; if(t[t[p].ls].sum >= k) return ask(t[p].ls, l, mid, k); else return ask(t[p].rs, mid+1, r, k - t[t[p].ls].sum); } int main(){ scanf("%d%d", &n, &m); int now = 1; for(int i=1;i<=n;i++){ int x;scanf("%d", &x); change(root[1], 1, n, i, x); } while(m--){ int op, p, x, y, q; scanf("%d%d", &op, &p); if(op == 0){ scanf("%d%d", &x, &y); now ++; build(root[now],root[p], 1, n, x, y); } else if(op == 1){ scanf("%d", &q); root[p] = merge(root[p], root[q], 1, n); } else if(op == 2){ scanf("%d%d", &x, &q); change(root[p], 1, n, q, x); } else if(op == 3){ scanf("%d%d", &x, &y); printf("%lld\n", ask(root[p], 1, n, x, y)); } else { ll x; scanf("%lld", &x); printf("%lld\n", ask(root[p], 1, n, x)); } } return 0; }

分块

莫队

#include <iostream> #include <algorithm> #include <math.h> #include <cstdio> using namespace std; const int N = 50010; typedef long long ll; int a[N],be[N],n,m; ll res = 0,sum[N]; struct node{ int l,r,id; ll A,B; }q[N]; //如果在同一块，则按照右端点排序，否则按照左端点 bool cmp1(node a,node b){ return be[a.l] == be[b.l] ? a.r < b.r : a.l < b.l; } bool cmp(node a,node b){ return a.id < b.id; } ll gcd(ll a,ll b){return b == 0 ? a : gcd(b,a%b);} ll S(ll x){return x * x;} //先减去上一次的影响，修改后再重新加新的影响 void move(int pos,int add){res -= S(sum[a[pos]]);sum[a[pos]] += add;res += S(sum[a[pos]]);} int main(){ scanf("%d%d",&n,&m); int base = sqrt(n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]);q[i].id = i; be[i] = (i-1) / base + 1;//be[i]即i在第几块 } for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r); sort(q+1,q+1+m,cmp1); int l = 1,r = 0; res = 0;//res为当点询问区间内出现的所有颜色的个数平方和 for(int i=1;i<=m;i++){ //暴力调整区间，维护res while(l < q[i].l)move(l++,-1); while(l > q[i].l)move(--l,1); while(r < q[i].r)move(++r,1); while(r > q[i].r)move(r--,-1); if(l == r){ q[i].A = 0;q[i].B = 1;continue; } q[i].A = res - (r - l + 1);//计算答案分子部分 q[i].B = 1ll * (r - l + 1) * (r - l);//分母部分 ll g = gcd(q[i].A,q[i].B);//约分 q[i].A /= g; q[i].B /= g; } sort(q+1,q+1+m,cmp); for(int i=1;i<=m;i++){ printf("%lld/%lld\n",q[i].A,q[i].B); } return 0; }

莫队优化

bool cmp1(node a,node b){ return be[a.l] == be[b.l] ? (be[a.l]&1 ? a.r < b.r : a.r > b.r) : a.l < b.l; }

带修莫队

#include <bits/stdc++.h> using namespace std; const int N = 10010; struct Query { int l,r,t,id; }q[N]; struct Modify { int pos,New,Old; }c[N]; int n,m,a[N],num[100*N],be[N],res,ans[N],l=1,r,now[N]; char op[3]; bool cmp(Query a,Query b){ return be[a.l] == be[b.l] ? (be[a.r] == be[b.r] ? a.t < b.t : (be[a.l]&1 ? a.r < b.r : a.r > b.r)) : a.l < b.l; } void move(int pos,int add){ num[a[pos]]+=add; if(num[a[pos]] == 0 && add < 0) res--; else if(num[a[pos]] == 1 && add > 0) res++; } void changeTime(int pos,int dat){ if(pos >= l && pos <= r){ move(pos,-1); a[pos] = dat; move(pos,1); } else a[pos] = dat; } int main(){ scanf("%d%d",&n,&m); int base = pow(n,0.666666); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); now[i] = a[i];be[i] = (i-1) / base + 1; } int t = 0,cur = 0; for(int i=1;i<=m;i++){ int x,y;scanf("%s%d%d",op,&x,&y); if(op[0] == 'Q')q[++t] = {x,y,cur,t}; else c[++cur] = {x,y,now[x]},now[x] = y; } sort(q+1,q+t+1,cmp); cur = 0; for(int i=1;i<=t;i++){ while(cur < q[i].t){ changeTime(c[cur+1].pos,c[cur+1].New);cur++; } while(cur > q[i].t){ changeTime(c[cur].pos,c[cur].Old);cur--; } while(l < q[i].l)move(l++,-1); while(l > q[i].l)move(--l,1); while(r < q[i].r)move(++r,1); while(r > q[i].r)move(r--,-1); ans[q[i].id] = res; } for(int i=1;i<=t;i++)printf("%d\n",ans[i]); return 0; }

树上莫队

#include <bits/stdc++.h> using namespace std; const int N = 40010; const int M = 100010; vector<int> G[N],alls; int be[N],f[N][19],n,m,ans[M],dep[N],u=1,v=1,sum[N],vis[N],a[N],base,cnt; int res; int st[N],top; struct Query{ int l,r; int id; }q[M]; void dfs(int x,int fa = -1){ for(int i=1;i<18;i++) f[x][i] = f[f[x][i-1]][i-1]; int bottom = top; for(int i = 0;i<G[x].size();i++){ int y = G[x][i]; if(y == fa)continue; dep[y] = dep[x] + 1; f[y][0] = x; dfs(y,x); if(top - bottom >= base){ cnt++; while(top != bottom){ be[st[top--]] = cnt; } } } st[++top] = x; } bool cmp(Query a,Query b){ return be[a.l] == be[b.l] ? be[a.r] < be[b.r] : be[a.l] < be[b.l]; } int LCA(int x,int y){ if(dep[x] > dep[y])swap(x,y); for(int i=18;i>=0;i--)if(dep[x] <= dep[f[y][i]]) y = f[y][i]; if(x == y)return x; for(int i=18;i>=0;i--)if(f[x][i] != f[y][i])x = f[x][i],y = f[y][i]; return f[x][0]; } void Run(int u){ if(vis[u] == 1){ vis[u] = 0; if(--sum[a[u]] == 0)res--; } else{ vis[u] = 1; if(sum[a[u]]++ == 0)res++; } } void move(int x,int y){ if(dep[x] < dep[y])swap(x,y); while(dep[x] > dep[y])Run(x),x = f[x][0]; while(x != y)Run(x),Run(y),x = f[x][0],y = f[y][0]; } int main(){ scanf("%d%d",&n,&m); base = sqrt(n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); alls.push_back(a[i]); } /*离散化*/ sort(alls.begin(),alls.end()); alls.erase(unique(alls.begin(),alls.end()),alls.end()); for(int i=1;i<=n;i++){ int id = lower_bound(alls.begin(),alls.end(),a[i]) - alls.begin() + 1; a[i] = id; } //存树 for(int i=1;i<n;i++){ int x,y;scanf("%d%d",&x,&y); G[x].push_back(y); G[y].push_back(x); } dep[1] = 1;//这里如果不单独设为wa dfs(1); while(top)be[st[top--]] = cnt; //存询问 for(int i=1;i<=m;i++){ scanf("%d%d",&q[i].l,&q[i].r); q[i].id = i; } sort(q+1,q+1+m,cmp); for(int i=1;i<=m;i++){ if(u != q[i].l){move(u,q[i].l);u=q[i].l;} if(v != q[i].r){move(v,q[i].r);v=q[i].r;} int anc = LCA(u,v); Run(anc);//单独考虑LCA ans[q[i].id] = res; Run(anc);// } for(int i=1;i<=m;i++)printf("%d\n",ans[i]); return 0; }

分块套路

#include <iostream> #include <cstdio> #include <math.h>using namespace std; typedef long long ll; const int N = 100010; ll a[N],sum[N],add[N]; //每段左右端点，每个位置所处哪一段 int L[N],R[N],pos[N]; int n,m,t; void change(int l,int r,ll d){ int p = pos[l],q = pos[r]; if(p == q){ for(int i=l;i<=r;i++)a[i] += d; sum[p] += d * (r - l + 1); } else{ for(int i = p + 1;i <= q-1;i++)add[i] += d; for(int i = l;i <= R[p];i++)a[i] += d; sum[p] += d * (R[p] - l + 1); for(int i=L[q];i<=r;i++)a[i] += d; sum[q] += d * (r - L[q] + 1); } } ll ask(int l,int r){ int p = pos[l], q = pos[r]; ll res = 0; if(p == q){ for(int i=l;i<=r;i++)res += a[i]; res += add[p] * (r-l+1); } else{ for(int i=l;i<=R[p];i++)res += a[i]; res += add[p] * (R[p] - l + 1); for(int i=L[q];i<=r;i++)res += a[i]; res += add[q] * (r - L[q] + 1); for(int i=p+1;i<=q-1;i++)res += sum[i] + add[i] * (R[i] - L[i] + 1); } return res; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); t = sqrt(n); for(int i=1;i<=t;i++){ L[i] = (i-1) * t+1; R[i] = i * t; } if(R[t] < n) t++,L[t] = R[t-1]+1,R[t] = n; for(int i=1;i<=t;i++){ for(int j=L[i];j<=R[i];j++){ pos[j] = i; sum[i] += a[j]; } } //指令 while(m--){ char op[3];int l,r,d; scanf("%s%d%d",op,&l,&r); if(op[0] == 'C'){ scanf("%d",&d); change(l,r,d); } else printf("%lld\n",ask(l,r)); } return 0; }

主席树

静态区间第k大

const int N = 200000 + 5; struct Seg{ int ls, rs; int sum; }t[N*40]; int rt[N], tot; vector<int> all; int n, a[N], l, r, k, m; int build(int l, int r){ int p = ++tot; if(l == r) { t[p].sum = 0; return p; } int mid = l + r >> 1; t[p].ls = build(l, mid); t[p].rs = build(mid+1, r); t[p].sum = 0; return p; } int insert(int now, int l, int r, int pos, int val){ int p = ++tot; t[p] = t[now]; if(l == r){ t[p].sum += val; return p; } int mid = l + r >> 1; if(pos <= mid) t[p].ls = insert(t[now].ls, l, mid, pos, val); else t[p].rs = insert(t[now].rs, mid+1, r, pos, val); t[p].sum = t[t[p].ls].sum + t[t[p].rs].sum; return p; } int ask(int p, int q, int l, int r, int k){ if(l == r) return l; int mid = (l + r) >> 1; int lcnt = t[t[q].ls].sum - t[t[p].ls].sum; if(k <= lcnt) return ask(t[p].ls, t[q].ls, l, mid, k); else return ask(t[p].rs, t[q].rs, mid+1, r, k - lcnt); } int main(){ scanf("%d%d", &n, &m); for(int i=1;i<=n;i++){ scanf("%d", &a[i]); all.push_back(a[i]); } sort(all.begin(),all.end()); all.erase(unique(all.begin(),all.end()),all.end()); for(int i=1;i<=n;i++){ a[i] = lower_bound(all.begin(),all.end(),a[i]) - all.begin() + 1; } rt[0] = build(1, all.size()); for(int i=1;i<=n;i++){ rt[i] = insert(rt[i-1], 1, all.size(), a[i], 1); } while(m--){ scanf("%d%d%d", &l, &r, &k); printf("%d\n", all[ask(rt[l-1], rt[r], 1, all.size(), k) - 1]); } return 0; }

树套树

树状数组套主席树

例题选自 2019徐州ICPC H

区间维护mex

using namespace std; using ll = long long; #define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0) void err() { cout << "\033[39;0m" << endl; } template<class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << " "; err(args...); } const int N = 2e5 + 10; int n, m, q, a[N], L[30][30], R[30][30], cl, cr; inline int lowbit(int x) { return x & -x; } struct SEG { struct node { int ls, rs; ll sum; void init() { ls = rs = sum = 0; } }t[N * 80]; int rt[N], tot; ll res; int newnode() { ++tot; t[tot].init(); return tot; } void init() { memset(rt, 0, sizeof rt); tot = 0; } void update(int &rt, int l, int r, int pos, int v) { if (!rt) rt = newnode(); t[rt].sum += v; if (l == r) return; int mid = (l + r) >> 1; if (pos <= mid) update(t[rt].ls, l, mid, pos, v); else update(t[rt].rs, mid + 1, r, pos, v); } void update(int x, int pos, int v) { for (; x <= n; x += lowbit(x)) { update(rt[x], 1, m, pos, v); } } void query(int dep, int l, int r, int ql, int qr) { if (ql > qr) return; if (l >= ql && r <= qr) { for (int i = 1; i <= cl; ++i) res -= t[L[dep][i]].sum; for (int i = 1; i <= cr; ++i) res += t[R[dep][i]].sum; return; } int mid = (l + r) >> 1; if (ql <= mid) { for (int i = 1; i <= cl; ++i) L[dep + 1][i] = t[L[dep][i]].ls; for (int i = 1; i <= cr; ++i) R[dep + 1][i] = t[R[dep][i]].ls; query(dep + 1, l, mid, ql, qr); } if (qr > mid) { for (int i = 1; i <= cl; ++i) L[dep + 1][i] = t[L[dep][i]].rs; for (int i = 1; i <= cr; ++i) R[dep + 1][i] = t[R[dep][i]].rs; query(dep + 1, mid + 1, r, ql, qr); } } }seg;int main() { m = 2e5; while (scanf("%d%d", &n, &q) != EOF) { for (int i = 1; i <= n; ++i) scanf("%d", a + i); seg.init(); for (int i = 1; i <= n; ++i) { seg.update(i, a[i], a[i]); } int op, x, y; for (int i = 1; i <= q; ++i) { scanf("%d%d%d", &op, &x, &y); if (op == 1) { seg.update(x, a[x], -a[x]); a[x] = y; seg.update(x, a[x], a[x]); } else { --x; cl = cr = 0; for (int j = x; j; j -= lowbit(j)) { L[0][++cl] = seg.rt[j]; } for (int j = y; j; j -= lowbit(j)) { R[0][++cr] = seg.rt[j]; } ll l = 0, r = 0; do{ r = l + 1; seg.res = 0; seg.query(0, 1, m, 1, min(1ll * m, r)); l = seg.res; } while (l >= r); printf("%lld\n", l + 1); } } } return 0; }

线段树套线段树

常数比较大

const int N = 50000 + 5; int rt[N << 2], n, m, maxn, tot; int b[N * 2], totn, L[N], R[N], op[N]; ll K[N]; struct SegTree{ int l, r; int tag; ll sz; } t[N * 400]; void pushdown(int p, int l, int r){ if(t[p].tag){ if(!t[p].l) t[p].l = ++tot; if(!t[p].r) t[p].r = ++tot; int ls = t[p].l, rs = t[p].r, &v = t[p].tag, mid = l + r >> 1; t[ls].tag += v, t[rs].tag += v; t[ls].sz += v * (mid - l + 1); t[rs].sz += v * (r - mid); v = 0; } } void update(int &p, int l,int r,int ql, int qr){ if(!p) p = ++tot; if(l >= ql && r <= qr){ t[p].tag++; t[p].sz += r - l + 1; return; } pushdown(p, l, r); int mid = l + r >> 1; if(mid >= ql) update(t[p].l, l, mid, ql, qr); if(mid < qr) update(t[p].r, mid + 1, r, ql, qr); t[p].sz = t[t[p].l].sz + t[t[p].r].sz; } void add(int p, int l, int r, int pos, int ql, int qr){ update(rt[p], 1, n, ql, qr); if(l == r) return; int mid = l + r >> 1; if(pos <= mid) add(p * 2, l, mid, pos, ql, qr); else add(p * 2 + 1, mid + 1, r, pos, ql, qr); } ll getsum(int &p, int l,int r,int ql, int qr){ if(!p) return 0; if(l >= ql && r <= qr) return t[p].sz; pushdown(p, l, r); int mid = l + r >> 1; ll res = 0; if(ql <= mid) res += getsum(t[p].l, l, mid, ql, qr); if(mid < qr) res += getsum(t[p].r, mid + 1, r, ql, qr); return res; } // [l,r] 是权值线段树区间，[ql,qr]是询问区间 int query(int p, int l,int r, int ql,int qr, ll x){ if(l == r) return b[l]; int mid = l + r >> 1; ll cnt = getsum(rt[p * 2 + 1], 1, n, ql, qr); //cout << l << ' ' << r << ' ' << cnt << endl; if(cnt < x) return query(p * 2, l, mid, ql, qr, x - cnt); else return query(p * 2 + 1, mid + 1, r, ql, qr, x); } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m;i++){ scanf("%d%d%d%lld", &op[i], &L[i], &R[i], &K[i]); if(op[i] == 1){ b[++totn] = K[i]; } } sort(b + 1, b + 1 + totn); totn = unique(b + 1, b + 1 + totn) - b - 1; for (int i = 1; i <= m;i++){ if(op[i] == 1){ K[i] = lower_bound(b + 1, b + 1 + totn, K[i]) - b; add(1, 1, totn, K[i], L[i], R[i]); } else { printf("%d\n", query(1, 1, totn, L[i], R[i], K[i])); } } return 0; }

四. 图论

最短路

1. Dijkstra

$n^2$

const int N = 3010 + 5; int a[N][N], d[N], n, m; bool v[N]; void dijkstra(){ memset(d, 0x3f, sizeof d); memset(v, 0, sizeof v); d[1] = 0; for(int i=1;i<n;i++){ // 重复进行 n-1 次 int x = 0; for(int j=1;j<=n;j++){ if(!v[j] && (x == 0 || d[j] < d[x])) x = j; } v[x] = 1; for(int y = 1; y <= n; y++) d[y] = min(d[y], d[x] + a[x][y]); } }

$(m+n)\log n$

const int N = 100010; const int M = 1000010; int head[N], ver[M], edge[M], nxt[M], d[N]; bool v[N]; int n, m, tot, s; typedef pair<int,int> pii; priority_queue<pii,vector<pii>, greater<pii> >q; void add(int x, int y, int z){ver[++tot] = y,edge[tot] = z, nxt[tot]=head[x],head[x] = tot; } void dijkstra(){ memset(d, 0x3f, sizeof d); memset(v, 0, sizeof v); d[1] = 0; q.push(make_pair(0,1)); while(q.size()){ int x = q.top().second;q.pop(); if(v[x])continue; v[x] = 1; for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(d[y] > d[x] + edge[i]){ d[y] = d[x] + edge[i]; q.push({d[y], y}); } } } } int main() { scanf("%d%d%d",&n,&m,&s); for(int i=1,x,y,z;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z);//此模板为有向图 } dijkstra(); for(int i=1;i<=n;i++)printf("%d ",d[i]); return 0; }

2. SPFA

$O(NM)$

const int N = 100000 + 5; const int M = 1000010; int head[N], ver[M], edge[M], nxt[M], d[N]; bool v[N]; int n, m, tot, s; queue<int> q; void add(int x, int y, int z){ver[++tot] = y,edge[tot] = z, nxt[tot]=head[x],head[x] = tot; } void spfa(){ memset(d, 0x3f, sizeof d); memset(v, 0, sizeof v); d[1] = 0, v[1] = 1; q.push(1); while(q.size()){ int x = q.front();q.pop(); v[x] = 0; for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(d[y] > d[x] + edge[i]){ d[y] = d[x] + edge[i]; if(!v[y]) q.push(y), v[y] = 1; } } } }int main() { scanf("%d%d%d",&n,&m,&s); for(int i=1,x,y,z;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z);//此模板为有向图 } spfa(); for(int i=1;i<=n;i++)printf("%d ",d[i]); return 0; }

3. Floyd

$O(n^3)$ 可以用来求传递闭包

void floyd(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); }

Johnson

利用势能与路径无关，至于起点和终点有关的性质，将负权边转换为正权边，进而利用dijkstra堆优化快速求解最短路

const int N = 3000 + 5; const int M = 20000 + 5; int n,m; int head[N], ver[M], nxt[M], edge[M], tot; int h[N],d[N],v[N],cnt[N]; priority_queue<pair<int,int> > q; void add(int x, int y, int z){ ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot; } bool spfa(){ memset(h, 0x3f, sizeof h); memset(v, 0, sizeof v); queue<int> q; q.push(0); h[0] = 0; v[0] = 1; while(q.size()){ int x = q.front();q.pop(); v[x] = 0; for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(h[y] > h[x] + edge[i]){ h[y] = h[x] + edge[i]; cnt[y] = cnt[x] + 1; if(cnt[y] >= n) return false; if(!v[y]) q.push(y), v[y] = 1; } } } return true; } void dijkstra(int s){ memset(d, 0x3f, sizeof d); memset(v, 0, sizeof v); q.push({0, s});d[s] = 0; while(q.size()){ int x = q.top().second;q.pop(); if(v[x])continue; v[x] = 1; for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(d[y] > d[x] + edge[i]){ d[y] = d[x] + edge[i]; q.push({-d[y],y}); } } } ll res = 0; for(int i=1;i<=n;i++){ if(d[i] == inf) res += 1ll * i * 1e9; else { // d[i] = f[i] + h[s] - h[i]; d[i] -= h[s] - h[i]; res += 1ll * i * d[i]; } } printf("%lld\n",res); } int main() { scanf("%d%d",&n,&m); for(int i=1,x,y,z;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); } for(int i=1;i<=n;i++) add(0,i,0); if(!spfa()){ puts("-1"); return 0; } for(int x=1;x<=n;x++){ for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; edge[i] = edge[i] + h[x] - h[y]; } } for(int x=1;x<=n;x++){ dijkstra(x); } return 0; }

最小生成树

1. Kruskal

$O(m\log m)$ 当边权比较小时可以直接桶排，降低复杂度（2019上海区域赛E）

struct rec{int x,y,z;} edge[500010]; int fa[100010], n, m, ans; bool operator < (rec a, rec b){ return a.z < b.z; } int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);} int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++)scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z); sort(edge+1,edge+m+1); for(int i=1;i<=n;i++) fa[i] = i; for(int i=1;i<=m;i++){ int x = find(edge[i].x); int y = find(edge[i].y); if(x == y)continue; fa[x] = y; ans += edge[i].z; } cout << ans << endl; return 0; }

2. Prim

$O(n^2)$

const int N = 3000 + 5; int a[N][N], d[N], n, m, ans; bool v[N]; void prim(){ memset(d, 0x3f, sizeof d); memset(v, 0, sizeof v); d[1] = 0; for(int i=1;i < n;i++){ int x = 0; for(int j=1;j<=n;j++) if(!v[j] && (x == 0 || d[j] < d[x])) x = j; v[x] = 1; for(int y=1;y<=n;y++) if(!v[y])d[y] = min(d[y], a[x][y]); } } int main() { cin >> n >> m; memset(a, 0x3f, sizeof a); for(int i=1;i<=n;i++) a[i][i] = 0; for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); a[y][x] = a[x][y] = min(a[x][y], z); } prim(); for(int i=2;i<=n;i++) ans += d[i]; cout << ans << endl; return 0; }

$O(m\log n)$

const int N = 400010; int n,m,st,ed; int head[N],ver[N],nxt[N],edge[N],tot; int d[N],v[N]; inline void add(int x,int y,int z){ ver[++tot] = y;edge[tot] = z;nxt[tot] = head[x];head[x] = tot; } int x,y,z; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } memset(d,0x3f,sizeof d); priority_queue<pair<int,int> > q; q.push({0,1});d[1] = 0; ll res = 0; while(q.size()){ int x = q.top().second;q.pop(); if(v[x])continue; res += d[x]; v[x] = 1; for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(d[y] > edge[i]){ d[y] = edge[i]; q.push({-d[y],y}); } } } cout << res << endl; return 0; }

最小斯坦纳树

给定一个包含 $n$ 个结点和 $m$ 条带权边的无向连通图 $G=(V,E)$。

再给定包含 $k$ 个结点的点集 $S$，选出 $G$ 的子图 $G'=(V',E')$ 使得：

$S\subseteq V'$
$G′$ 为连通图；
$E′$ 中所有边的权值和最小。

你只需要求出 $E′$中所有边的权值和。

$dp[i][s]$ 表示以 i 为根的一棵树，包含集合 S 中所有点的最小代价

$w[i][j] + dp[j][s] -> dp[i][s]$
$dp[i][T] + dp[i][S-T] -> dp[i][S]\quad(T \subseteq S)$

第二类转移可以用枚举子集来转移，第一类转移是一个三角不等式，可以用spfa或者dijkstra

const int N = 100 + 5; const int M = 1010; int n, m, k, x, y, z, tot; int head[N], ver[M], nxt[M], edge[M], dp[N][4200]; int p[N], vis[N]; priority_queue<pair<int,int>> q; void add(int x, int y, int z){ ver[++tot] = y; edge[tot] = z, nxt[tot] = head[x], head[x] = tot; } void dijkstra(int s){ memset(vis, 0, sizeof vis); while(q.size()){ auto t = q.top();q.pop(); int x = t.second; if(vis[x]) continue; vis[x] = 1; for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(dp[y][s] > dp[x][s] + edge[i]){ dp[y][s] = dp[x][s] + edge[i]; q.push(make_pair(-dp[y][s], y)); } } } } int main(){ scanf("%d%d%d", &n, &m, &k); for(int i=1;i<=m;i++){ scanf("%d%d%d", &x, &y, &z); add(x, y, z);add(y, x, z); } memset(dp, 0x3f, sizeof dp); for(int i=1;i<=k;i++){ scanf("%d", &p[i]); dp[p[i]][1<<(i-1)] = 0; } for(int s = 1; s < (1 << k); s++){ for(int i=1; i <= n; i++){ for(int subs = (s-1)&s; subs; subs = s & (subs-1)){ dp[i][s] = min(dp[i][s], dp[i][subs]+dp[i][s^subs]); } if(dp[i][s]!=inf) q.push(make_pair(-dp[i][s], i)); } dijkstra(s); } printf("%d\n", dp[p[1]][(1<<k)-1]); return 0; }

树的直径

树形dp

void dp(int x){ v[x] = 1; for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(v[y])continue; dp(y); ans = max(ans, d[x] + d[y] + edge[i]); d[x] = max(d[x], d[y], edge[i]); } }

两次dfs或bfs，bfs可以记录路径

const int N = 200010; vector<pair<int,int> > v[N]; int n, pre[N], vis[N],mark[N]; ll d[N]; int bfs(int s){ queue<int> q; q.push(s); memset(vis, 0, sizeof vis); memset(d, 0, sizeof d); memset(pre, 0, sizeof pre); vis[s] = d[s] = 0; int t = s; while(q.size()){ int x = q.front(); q.pop(); if(d[x] > d[t])*** t = x; vis[x] = 1; for (int i = 0; i < v[x].size();i++){ int y = v[x][i].first; if(vis[y]) continue; d[y] = d[x] + v[x][i].second; pre[y] = x;**** q.push(y); } } return t; } int main(){ scanf("%d", &n); for (int i = 1,x, y, z; i < n;i++){ scanf("%d%d%d", &x, &y, &z); v[x].push_back({y, z}); v[y].push_back({x, z}); } int s = bfs(1); int t = bfs(s); int p = t, np = pre[t]; ll len = d[t]; cout << len << endl; while(p != s){ mark[p] = 1; p = pre[p]; mark[p] = 1; } p = t; return 0; }

树上启发式合并

求每个子树上不同颜色的个数

// U41492 #include <cstdio> #include <iostream> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int N = 100000 + 5; int c[N], cou[N], res[N], son[N]; int dfn[N], cid[N],sz[N]; int cnt, num; vector<int> v[N]; int n,m; void dfs(int x, int fa){ dfn[x] = ++cnt, cid[cnt] = x; sz[x] = 1; for(int i=0;i<v[x].size();i++){ int y = v[x][i]; if(y == fa)continue; dfs(y,x); sz[x] += sz[y]; if(son[x] == 0 || sz[y] > sz[son[x]]) son[x] = y; } } //核心思想即所有重边只会走一次， void get(int x, int fa, int flag){ for(int i=0;i<v[x].size();i++){ int y = v[x][i]; if(y == fa || y == son[x])continue;//不保存答案遍历时，一定不能遍历重儿子 get(y, x, 0); } if(son[x]) get(son[x], x, 1); for(int i=0;i<v[x].size();i++){ int y = v[x][i]; if(y == fa || y == son[x])continue; for(int j=dfn[y];j<=dfn[y]+sz[y]-1;j++){ if(++cou[c[cid[j]]] == 1) num++; } } if(++cou[c[x]] == 1)num++; res[x] = num; if(flag == 0){ for(int j=dfn[x];j<=dfn[x]+sz[x]-1;j++){ if(--cou[c[cid[j]]] == 0) num--; } } } int main() { scanf("%d",&n); for(int i=1;i<n;i++){ int x,y;scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); } for(int i=1;i<=n;i++)scanf("%d",&c[i]); dfs(1, 0); get(1, 0, 0); scanf("%d",&m); while(m--){ int x;scanf("%d",&x); printf("%d\n",res[x]); } return 0; }

点分治

求是否存在路径权值和为k的路径

const int N = 10000 + 5; const int M = 20010; int head[N], ver[M], edge[M], nxt[M]; int sz[N], del[N], dis[N], st[N], q[N], cnt, top; int query[101], res[N]; bool has[10000010]; int n, m, tot, all, core, min_size; void add(int x, int y, int z){ ver[++tot] = y, nxt[tot] = head[x], edge[tot] = z, head[x] = tot; } void getsize(int x, int fa){ sz[x] = 1; int mx = 0; for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(y == fa || del[y]) continue; getsize(y, x); mx = max(mx, sz[y]); sz[x] += sz[y]; } mx = max(mx, all - sz[x]); if(mx < min_size) {min_size = mx, core = x;} } void getdis(int x, int fa){ if(dis[x] <= 10000000) st[++cnt] = x, q[++top] = x; for(int i=head[x];i;i=nxt[i]) { int y = ver[i]; if(del[y] || y == fa) continue; dis[y] = dis[x] + edge[i]; getdis(y, x); } } void get(int x){ cnt = top = 0; del[x] = 1; dis[x] = 0; has[dis[x]] = true; q[++top] = x; for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(del[y]) continue; dis[y] = edge[i]; cnt = 0; getdis(y, x); for(int j=1;j<=cnt;j++){ for(int k=1;k<=m;k++){ if(query[k] >= dis[st[j]]){ res[k] |= has[query[k] - dis[st[j]]]; } } } for(int j=1;j<=cnt;j++) has[dis[st[j]]] = true; } for(int i=1;i<=top;i++) has[dis[q[i]]] = false; for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(del[y]) continue; min_size = inf; all = sz[y]; getsize(y, 0); getsize(core, 0); get(core); } } int main(){ scanf("%d%d", &n, &m); for(int i=1;i<n;i++){ int x, y, z;scanf("%d%d%d", &x, &y, &z); add(x, y, z); add(y, x, z); } for(int i=1;i<=m;i++) scanf("%d", &query[i]); min_size = inf; all = n; core = 0; getsize(1, 0); getsize(core, 0); get(core); for(int i=1;i<=m;i++) puts(res[i] ? "AYE" : "NAY"); return 0; }

无向图连通性

求割边

无向边 $(x,y)$ 是桥，当且仅当搜索树上存在 $x$ 的一个子节点 $y$ ,满足：

\[dfn[x] < low[y]
\]

void tarjan(int x, int in_edge){ dfn[x] = low[x] = ++num; for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(!dfn[y]){ tarjan(y,i); low[x] = min(low[x], low[y]); if(low[y] > dfn[x]) bridge[i] = bridge[i ^ 1] = true; //标记为割边 } else if (i != (in_edge ^ 1)) { low[x] = min(low[x], dfn[y]); } } } //main函数中 //加边要保证第一条边编号为2 for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i, 0);

割点

若 $x$ 不是搜索树的根节点（$dfs$) ，则 $x$ 是割点当且仅当搜索树上存在 $x$ 的一个子节点$y$ 满足：$$dfn[x] \le low[y]$$

void tarjan(int x){ dfn[x] = low[x] = ++num; int flag = 0; for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(!dfn[y]){ tarjan(y); low[x] = min(low[x], low[y]); if(low[y] >= dfn[x]){ flag ++; if(x != root || flag >= 2) cut[x] = true; } } else low[x] = min(low[x], dfn[y]); } } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i);

边双连通分量 (e-DCC)

只需要求出无向图的所有的桥，把桥都删除后，无向图会分成若干个连通块，每个连通块就是一个“边联通分量”。

int c[N], dcc; void dfs(int x){ c[x] = dcc;// x所属的连通块编号 for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(c[y] || bridge[i])continue; // 不访问桥 dfs(y); } } //main函数中 for(int i=1;i<=n;i++)if(!c[i]){ ++dcc; dfs(i); }

e-DCC 的缩点

把每个$e-DCC$ 看作一个节点，把桥$(x,y)$ 看作连接编号为$c[x]$ 和 $c[y]$ 的$e-DCC$ 对应节点的无向边，会产生一棵树（若原来的图不连通，则产生森林）。

int hc[N], vc[N*2], nc[N*2], tc; void add_c(int x,int y){ vc[++tc] = y, nc[tc] = hc[x], hc[x] = tc; } //main函数中 tc = 1; for(int i=2;i<=tot;i++){ int x = ver[i ^ 1], y = ver[i]; if(c[x] == c[y])continue; add_c(c[x],c[y]); }

点双连通分量(v-DCC) 求法

点双连通分量并不是指“删除割点后图中剩余的连通块”

割点可能属于多个$v-DCC$。

void tarjan(int x){ dfn[x] = low[x] = ++num; st[++top] = x; if(x == root && head[x] == 0){ // 孤立点特判 dcc[++cnt].push_back(x); return ; } int flag = 0; for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(!dfn[y]){ tarjan(y); low[x] = min(low[x], low[y]); if(low[y] >= dfn[x]){ //割点成立条件满足 flag ++; if(x != root || flag > 1)cut[x] = true; cnt++; int z; do{ z = st[top--]; dcc[cnt].push_back(z); }while(z != y);//栈中直到 y 都出栈 dcc[cnt].push_back(x); } }else low[x] = min(low[x], dfn[y]); } }

v-DCC 的缩点

设图中共有 $p$ 个割点和 $t$ 个$v-DCC$。我们建立一张包含$p+t$ 个节点的新图，把每个$v-DCC$ 和每个割点作为新图中的节点，并在每个割点与包含它的所有$v-DCC$ 之间连边。容易发现，这张新图其实是一颗树（或森林）

//给每个割点一个新的编号（编号从cnt+1开始) num = cnt; for(int i=1;i<=n;i++) if(cut[i])new_id[i] = ++num; tc = 1; for(int i=1;i<=cnt;i++){ for(int j=0;j<dcc[i].size();j++){ int x = dcc[i][j]; if(cut[x]){ add_c(i,new_id[x]); add_c(new_id[x],i); }else c[x] = i; // 除割点外，其他点仅属于1个v-DCC } }

有向图连通性

求强连通分量

const int N = 100010, M = 1000010; int head[N], ver[M], nxt[M], dfn[N], low[N]; int st[N], ins[N], c[N]; vector<int> scc[N]; int n, m, tot, num, top, cnt; void add(int x, int y){ ver[++tot] = y, nxt[tot] = head[x], head[x] = cnt; } void tarjan(int x){ dfn[x] = low[x] = ++num; st[++top] = x, ins[x] = 1; for(int i=head[x];i;i=nxt[i]){ if(!dfn[ver[i]]){ tarjan(ver[i]); low[x] = min(low[x], low[ver[i]]); }else if(ins[ver[i]]) //有作用的横叉边以及返祖边 low[x] = min(low[x], dfn[ver[i]]); } if(dfn[x] == low[x]){//x可以作为这个连通分量的入口 cnt ++;int y; do{ y = st[top--], ins[y] = 0; c[y] = cnt, scc[cnt].push_back(y); }while(x != y); } }

缩点

for(int x=1;x<=n;x++){ for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(c[x] == c[y])continue; add_c(c[x],c[y]); } }

欧拉路

void enlur(){ st[++top] = 1; while(top > 0){ int x = st[top] , i = head[x]; while(i && vis[i]) i = nxt[i]; if(i){ st[++top] = ver[i]; vis[i] = vis[i ^ 1] = 1; head[x] = nxt[i]; // 会修改head[x] 的值 }else{ top --; ans[++t] = x; } } }

二分图

1. 二分图判定

染色法

int n; int head[N],edge[M],nxt[M],tot; int color[N]; bool dfs(int u,int fa,int c){ co[u] = c; for(int i=head[u];i;i=nxt[i]){ int j = edge[i]; if(co[j] == -1) if(!dfs(j,u,!c))return false; else if(co[j] == c)return false; } return true; } bool check(){ memset(co,-1,sizeof co); bool flag = true; for(int i=1;i<=n;i++){ if(co[i] == -1){ if(!dfs(i,-1,0)){ flag = false; break; } } } return flag; }

2. 二分图最大匹配

匈牙利算法复杂度 $O(NM)$

bool dfs(int x){ for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(!vis[y]){ vis[y] = 1; if(!match[y] || dfs(match[y])){ match[y] = x; return true; } } } return false; } for(int i=1;i<=n;i++){ memset(vis, 0, sizeof vis); if(dfs(i)) res++; }

3. 二分图带权最大匹配

KM $O(n^3)$

2019南京 J spy

ll n, a[N],b[N],c[N],p[N]; ll w[N][N]; ll lx[N] , ly[N]; ll match[N]; ll slack[N]; bool vy[N]; ll pre[N]; void bfs( ll k ){ ll x , y = 0 , yy = 0 , delta; memset( pre , 0 , sizeof(pre) ); for( ll i = 1 ; i <= n ; i++ ) slack[i] = inf; match[y] = k; while(1){ x = match[y]; delta = inf; vy[y] = true; for( ll i = 1 ; i <= n ;i++ ){ if( !vy[i] ){ if( slack[i] > lx[x] + ly[i] - w[x][i] ){ slack[i] = lx[x] + ly[i] - w[x][i]; pre[i] = y; } if( slack[i] < delta ) delta = slack[i] , yy = i ; } } for( ll i = 0 ; i <= n ; i++ ){ if( vy[i] ) lx[match[i]] -= delta , ly[i] += delta; else slack[i] -= delta; } y = yy ; if( match[y] == -1 ) break; } while( y ) match[y] = match[pre[y]] , y = pre[y]; }ll KM(){ memset( lx , 0 ,sizeof(lx) ); memset( ly , 0 ,sizeof(ly) ); memset( match , -1, sizeof(match) ); for( ll i = 1 ; i <= n ; i++ ){ memset( vy , false , sizeof(vy) ); bfs(i); } ll res = 0 ; for( ll i = 1 ; i <= n ; i++ ){ if( match[i] != -1 ){ res += w[match[i]][i] ; } } return res; }int main() { scanf("%lld",&n); for(ll i=1;i<=n;i++) scanf("%lld",&a[i]); for(ll i=1;i<=n;i++) scanf("%lld",&p[i]); for(ll i=1;i<=n;i++) scanf("%lld",&b[i]); for(ll i=1;i<=n;i++) scanf("%lld",&c[i]); for(ll i=1;i<=n;i++){ for(ll j=1;j<=n;j++){ ll s=0; for(ll k=1;k<=n;k++){ if(b[i]+c[j]>a[k]) s+=p[k]; } w[i][j]=s; } } printf("%lld\n",KM()); return 0; }

虚树

P2495

#include <cstdio> #include <iostream> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int N = 250000 + 5; const int M = 2*N; int n, q, k, a[N], mark[N]; int head[N], ver[M], edge[M], nxt[M], tot; int dfn[N], cid[N], cnt; int dep[N], f[N][20], minval[N][20]; int st[N], top; ll d[N]; struct Graph{ int head[N], ver[M], edge[M], nxt[M], tot; void add(int x, int y, int z){ ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot; } }G; void add(int x, int y, int z){ ver[++tot] = y, nxt[tot] = head[x], edge[tot] = z, head[x] = tot; } void dfs(int x,int fa){ dfn[x] = ++cnt, cid[cnt] = x; for(int i=head[x];i;i=nxt[i]){ int y = ver[i]; if(y == fa)continue; f[y][0] = x; dep[y] = dep[x] + 1; minval[y][0] = edge[i]; dfs(y, x); } } int MinVal; int lca(int x, int y){ MinVal = inf; if(dep[x] > dep[y]) swap(x, y); for(int i=19;i>=0;i--){ if(dep[f[y][i]] >= dep[x]){ MinVal = min(MinVal, minval[y][i]); y = f[y][i]; } } if(x == y)return x; for(int i=19;i>=0;i--){ if(f[y][i] != f[x][i]){ MinVal = min(MinVal, min(minval[x][i], minval[y][i])); y = f[y][i], x = f[x][i]; } } return f[x][0]; } void insert(int x){ if(x == 1) return; int t = lca(x, st[top]); if(t != st[top]){ while(top > 1 && dfn[st[top-1]] > dfn[t]){ lca(st[top-1], st[top]); G.add(st[top-1], st[top], MinVal); top --; } if(dfn[t] > dfn[st[top-1]]){ // t 不在栈中 G.head[t] = 0; lca(t, st[top]); G.add(t, st[top], MinVal); st[top] = t; } else { // 说明 t 已经在栈中 lca(t,st[top]); G.add(t, st[top--], MinVal); } } G.head[x] = 0, st[++top] = x; } bool cmp(int x, int y){return dfn[x] < dfn[y];} void build(){ sort(a + 1, a + 1 + k, [=](const int a, const int b)->bool{return dfn[a] < dfn[b];}); st[top=1] = 1; G.tot = 0, G.head[1] = 0; for(int i=1,l;i<=k;i++) insert(a[i]); for(int i=1;i<top;i++){ lca(st[i], st[i+1]); G.add(st[i], st[i+1], MinVal); } } void dfs(int x){ d[x] = 0; for(int i=G.head[x];i;i=G.nxt[i]){ int y = G.ver[i]; //cout << x << ' ' << y << ' ' << G.edge[i] << endl; dfs(y); if(mark[y]) d[x] += G.edge[i]; else d[x] += min(1ll*G.edge[i], d[y]); } }int main() { memset(minval, 0x3f, sizeof minval); scanf("%d",&n); for(int i=1,x,y,z;i<n;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } dep[1] = 1; dfs(1, 0); for(int j=1;j<20;j++) for(int i=1;i<=n;i++) f[i][j] = f[f[i][j-1]][j-1], minval[i][j] = min(minval[i][j-1], minval[f[i][j-1]][j-1]); scanf("%d",&q); while(q--){ scanf("%d",&k); for(int i=1;i<=k;i++)scanf("%d",&a[i]), mark[a[i]] = 1; build(); dfs(1); printf("%lld\n", d[1]); for(int i=1;i<=k;i++) mark[a[i]] = 0; } return 0; }

网络流

一定要注意边序号初始为1

最大流

1. $EK$

$O(nm^2)$ 一般可以处理$10^3\sim 10^4$ 规模的网络

const int inf = 1 << 29, N = 2010, M = 20010; int head[N],ver[M],edge[M],nxt[M],v[N],incf[N],pre[N]; int n,m,s,t,tot,maxflow; void add(int x, int y, int z){ ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot; ver[++tot] = x, edge[tot] = 0, nxt[tot] = head[y], head[y] = tot; } bool bfs(){ memset(v,0,sizeof v); queue<int> q; q.push(s); v[s] = 1; incf[s] = inf; while(q.size()){ int x = q.front(); q.pop(); for(int i=head[x];i;i=nxt[i]){ if(edge[i]){ int y = ver[i]; if(v[y])continue; incf[y] = min(incf[x], edge[i]); pre[y] = i; q.push(y), v[y] = 1; if(y == t) return 1; } } } return 0; } void update(){ int x = t; while(x != s){ int i = pre[x]; edge[i] -= incf[t]; edge[i ^ 1] += incf[t]; x = ver[i ^ 1]; } maxflow += incf[t]; } int main(){ while(cin >> n >> m){ memset(head,0,sizeof head); s = 1, t = n, tot = 1, maxflow = 0; for(int i=1;i<=m;i++){ int x,y,z;scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } while(bfs()) update(); cout << maxflow << endl; } }

2. Dinic

$O(n^2m)$ 该算法求解二分图最大匹配的时间复杂度为$O(m\sqrt{n})$

const int inf = 1<<29, N = 50010,M=30010; int head[N], ver[M], edge[M], nxt[M], d[N]; int n, m, s, t, tot, maxflow; queue<int> q; void add(int x, int y, int z){ ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot; ver[++tot] = x, edge[tot] = 0, nxt[tot] = head[y], head[y] = tot; } bool bfs(){ memset(d, 0, sizeof d); while(q.size())q.pop(); q.push(s);d[s] = 1; while(q.size()){ int x = q.front();q.pop(); for(int i=head[x];i;i=nxt[i]){ if(edge[i] && !d[ver[i]]){ q.push(ver[i]); d[ver[i]] = d[x] + 1; if(ver[i] == t) return 1; } } } return 0; } int dinic(int x, int flow){ if(x == t) return flow; int rest = flow, k; for(int i=head[x];i && rest; i=nxt[i]){ if(edge[i] && d[ver[i]] == d[x] + 1){ k = dinic(ver[i], min(rest, edge[i])); if(!k) d[ver[i]] = 0; edge[i] -= k; edge[i ^ 1] += k; rest -= k; } } return flow - rest; } int main(){ cin >> n >> m; cin >> s >> t; tot = 1; for(int i=1;i<=m;i++){ int x, y, c;scanf("%d%d%d",&x,&y,&c); add(x,y,c); } int flow = 0; while(bfs()) while(flow = dinic(s,inf)) maxflow += flow; cout << maxflow << endl; }

费用流

const int N = 5000 + 5; const int M = 100010; int head[N], ver[M], nxt[M], cost[M], edge[M]; int d[N], v[N], pre[N], incf[N]; int n, m, s, t, tot; int maxflow, ans; void add(int x, int y, int z, int c){ ver[++tot] = y, nxt[tot] = head[x], edge[tot] = z, cost[tot] = c, head[x] = tot; ver[++tot] = x, nxt[tot] = head[y], edge[tot] = 0, cost[tot] = -c, head[y] = tot; } bool spfa(){ memset(d, 0x3f, sizeof d); memset(v, 0, sizeof v); d[s] = 0; v[s] = 1; incf[s] = inf; queue<int> q; q.push(s); while(q.size()){ int x = q.front();q.pop(); v[x] = 0;//注意这里 for(int i=head[x];i;i=nxt[i])if(edge[i]){ int y = ver[i]; if(d[y] > d[x] + cost[i]){ d[y] = d[x] + cost[i]; incf[y] = min(incf[x], edge[i]); pre[y] = i; if(!v[y]) v[y] = 1, q.push(y); } } } return d[t] != inf; } void update(){ int x = t; while(x != s){ int i = pre[x]; edge[i] -= incf[t]; edge[i^1] += incf[t]; x = ver[i^1]; } maxflow += incf[t]; ans += incf[t] * d[t]; } int main(){ tot = 1;//注意这里 scanf("%d%d%d%d", &n, &m, &s, &t); for(int i=1;i<=m;i++){ int x, y, z, c;scanf("%d%d%d%d", &x, &y, &z, &c); add(x, y, z, c); } while(spfa()) update(); printf("%d %d\n", maxflow, ans); return 0; }

灭绝树

DAG

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back const int N = 200010; //E：原图，G反图，T支配树 //dep：T中的深度，deg:反向图中的入度 vector<int> E[N],G[N],T[N]; int n,m,deg[N],rt,a[N],dep[N],val[N]; int f[N][20],tot; void BFS(){ queue<int> q; rt = n+1;//超级源点.....nmb for(int i=1;i<=n;i++)if(!deg[i]){q.push(i);E[rt].pb(i);G[i].pb(rt);} int tot = 0; while(!q.empty()){ int u = q.front();q.pop(); a[++tot] = u; for(int v : E[u])if((--deg[v]) == 0)q.push(v); } } int LCA(int x,int y){ if(dep[x] > dep[y])swap(x,y); for(int i=19;i>=0;i--)if(dep[y] > dep[x] && dep[f[y][i]] >= dep[x])y = f[y][i]; if(x == y)return x; for(int i=19;i>=0;i--)if(f[x][i] != f[y][i]) x = f[x][i],y=f[y][i]; return f[x][0]; } int main(){ int tt;scanf("%d",&tt); while(tt--){ scanf("%d%d",&n,&m); for(int i=1;i<=n+1;i++){ E[i].clear();G[i].clear();T[i].clear(); dep[i] = deg[i] = 0; } for(int i=1,u,v;i<=m;i++){ scanf("%d%d",&u,&v); E[v].pb(u);G[u].pb(v);deg[u] ++; } BFS(); dep[rt] = 1; for(int i=1;i<=n;i++){ int u = a[i],fa = -1; for(int v:G[u])fa = (fa == -1 ?v:LCA(fa,v)); dep[u] = dep[fa]+1; f[u][0] = fa;T[fa].pb(u); for(int i=1;i<=19;i++)f[u][i] = f[f[u][i-1]][i-1]; } int q;scanf("%d",&q); while(q--){ int u,v;scanf("%d%d",&u,&v); int lca = LCA(u,v); printf("%d\n",dep[u] + dep[v] - dep[lca] - 1); } } }

有向图+DAG

#include <bits/stdc++.h> using namespace std; const int N = 3e5+10; struct Map{ int head[N],ver[N<<1],nxt[N<<1],cnt; void reset(){cnt = 0;memset(head,0,sizeof head);} void link(int x,int y){ver[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;} }E,G,T,TR,D; int deg[N],dep[N],dfn[N],id[N],fa[N],f[N][20],semi[N],mm[N],tot,anc[N],ans[N],top[N],cnt,n,m; void dfs(int x){ dfn[x] = ++tot;id[tot] = x; for(int i=E.head[x];i;i=E.nxt[i]){ int y = E.ver[i]; if(dfn[y])continue; dfs(y);T.link(x,y); //2 anc[y] = x; } } int find(int x){ if(x == fa[x])return x; int ff = fa[x];fa[x] = find(fa[x]); if(dfn[semi[mm[ff]]] < dfn[semi[mm[x]]])mm[x] = mm[ff]; return fa[x]; } int LCA(int x,int y){ if(dep[x] > dep[y])swap(x,y); for(int i=18;i>=0;i--)if(dep[x] < dep[y] && dep[f[y][i]] >= dep[x])y=f[y][i]; if(x == y)return x; for(int i=18;i>=0;i--)if(f[x][i] != f[y][i])x=f[x][i],y=f[y][i]; return f[x][0]; } int getAns(int x){ ans[x] = 1; for(int i=D.head[x];i;i=D.nxt[i]){ int y = D.ver[i]; getAns(y),ans[x] += ans[y]; } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ semi[i] = mm[i] = fa[i] = i; } for(int i=1,u,v;i<=m;i++){ scanf("%d%d",&u,&v); E.link(u,v);G.link(v,u); } dfs(1);anc[1] = 0; for(int i=n;i>=2;i--){ int x = id[i],res = n; if(!x)continue; for(int i=G.head[x];i;i=G.nxt[i]){ int y = G.ver[i]; if(!dfn[y])continue; if(dfn[y] < dfn[x])res = min(res,dfn[y]); else{ //1. find(y);res = min(res,dfn[semi[mm[y]]]); } } semi[x] = id[res];fa[x] = anc[x]; T.link(semi[x],x); } for(int x=1;x<=n;x++) for(int i=T.head[x];i;i=T.nxt[i]){ int y = T.ver[i]; TR.link(y,x);deg[y]++; } queue<int> q; for(int i=1;i<=n;i++)if(deg[i]==0)q.push(i); while(!q.empty()){ int x = q.front();q.pop(); top[++cnt] = x; for(int i=T.head[x];i;i=T.nxt[i]){ int y = T.ver[i]; if((--deg[y]) == 0)q.push(y); } } for(int i=1;i<=cnt;i++){ int x = top[i],bb = -1; for(int j=TR.head[x];j;j=TR.nxt[j]){ int y = TR.ver[j]; bb = bb==-1?y:LCA(y,bb); } f[x][0] = bb;D.link(bb,x);dep[x] = dep[bb]+1; for(int j=1;j<=18;j++)f[x][j] = f[f[x][j-1]][j-1]; } getAns(1); for(int i=1;i<=n;i++)printf("%d ",ans[i]); return 0; }

有向图

#include <bits/stdc++.h> using namespace std; const int N = 3e5+10; struct Map{ int head[N],ver[N<<1],nxt[N<<1],cnt; void reset(){cnt = 0;memset(head,0,sizeof head);} void link(int x,int y){ver[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;} }E,G,T,D; //E原图，G反图，T为DAG int dfn[N],id[N],fa[N],f[N][20],semi[N],mm[N],tot,anc[N],ans[N],top[N],cnt,n,m,idom[N]; void dfs(int x){ dfn[x] = ++tot;id[tot] = x; for(int i=E.head[x];i;i=E.nxt[i]){ int y = E.ver[i]; if(dfn[y])continue; dfs(y); anc[y] = x; } } int find(int x){ if(x == fa[x])return x; int ff = fa[x];fa[x] = find(fa[x]); if(dfn[semi[mm[ff]]] < dfn[semi[mm[x]]])mm[x] = mm[ff]; return fa[x]; } int getAns(int x){ ans[x] = 1; for(int i=D.head[x];i;i=D.nxt[i]){ int y = D.ver[i]; getAns(y),ans[x] += ans[y]; } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ semi[i] = mm[i] = fa[i] = i; } for(int i=1,u,v;i<=m;i++){ scanf("%d%d",&u,&v); E.link(u,v);G.link(v,u); } dfs(1);anc[1] = 0; for(int i=n;i>=2;i--){//dfs序倒着来 int x = id[i],res = n; if(!x)continue; for(int i=G.head[x];i;i=G.nxt[i]){ int y = G.ver[i]; if(!dfn[y])continue; if(dfn[y] < dfn[x])res = min(res,dfn[y]); else{ find(y); res = min(res,dfn[semi[mm[y]]]); } } semi[x] = id[res];fa[x] = anc[x]; T.link(semi[x],x); x = anc[x]; for(int j=T.head[x];j;j=T.nxt[j]){ int y = T.ver[j]; find(y); if(semi[mm[y]] == x)idom[y] = x; else idom[y] = mm[y]; } } for(int i=2,now;i<=tot;i++){ now = id[i]; if(idom[now] != semi[now])idom[now] = idom[idom[now]]; } for(int i=2;i<=n;i++)if(idom[i])D.link(idom[i],i); getAns(1); for(int i=1;i<=n;i++)printf("%d ",ans[i]); return 0; }

五. 技巧

调试

#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0) void err() { cout << "\033[39;0m" << endl; } template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }

快读

inline 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<<1) + (x<<3) + (ch^48);ch=getchar();} return x * f; }

快写

void put(int x){ int num = 0; char c[15]; while(x) c[++num] = (x % 10) + 48, x /= 10; while(num) putchar(c[num--]); putchar('\n'); }

枚举子集

S是一个二进制数，表示一个集合，可以用S0=S（初始），S0=(S0-1)&S（下一个）这种方法枚举遍S的所有子集。

注意到这种枚举方法是二进制数值上从大到小枚举子集的。用归纳法证明合理性，假设枚举到某个S0，大于它的所有S子集都枚举过了，下一个枚举S1=(S0-1)&S，需要证明S1是S0紧挨着的下一个子集，才能保证枚举不漏，也就是要证明区间(S1,S0)里不存在S的其他子集。

设S0以k（k=0,1,2…）个0结尾，S0=xxxx10...0，则S0-1=xxxx01...1，S1=(S0-1)&S，易见S1是以xxxx0开头的最大子集，而S0是以xxxx1开头的最小子集，如果存在某子集$S1<Sx<S0$，Sx要么以xxxx0开头，要么以xxxx1开头，无论哪种情况，都会出现矛盾。

复杂度$O(3^n)$

$3^15=14348907,3^14=4782969$

for (int S=1; S<(1<<n); ++S){ for (int S0=S; S0; S0=(S0-1)&S) //do something.

如果不包含自身

for (int S=1; S<(1<<n); ++S){ for (int S0=(S-1)&S; S0; S0=(S0-1)&S) //do something. }

大数

#include <bits/stdc++.h> using namespace std; typedef long long ll; struct BigInteger{ //BASE为vector数组中一位中最大存储的数字，前面都是以10计算的 //WIDTH为宽度 static const int BASE = 100000000; static const int WIDTH = 8; vector<int> s; //正数为1，负数为-1 int flag = 1; //构造函数 BigInteger(ll num = 0){*this = num;} BigInteger(string str){*this = str;} BigInteger(const BigInteger& t){ this->flag = t.flag; this->s = t.s; } //赋值函数 BigInteger operator = (ll num){ s.clear(); do { s.push_back(num % BASE); num /= BASE; }while(num > 0); return *this; } BigInteger operator = (string &str){ s.clear(); int x,len = (str.length()-1)/WIDTH + 1; for(int i=0;i<len;i++){ int end = str.length() - i*WIDTH; int start = max(0,end - WIDTH); sscanf(str.substr(start,end-start).c_str(),"%d",&x); s.push_back(x); } return *this; } //基本比较函数 A < B bool cmp( vector<int> &A, vector<int> & B){ if(A.size() != B.size())return A.size() < B.size(); for(int i=A.size()-1;i>=0;i--){ if(A[i] != B[i]){ return A[i] < B[i]; } } return false; } //比较函数如果小于则返回真 bool operator < ( BigInteger & b){ return cmp(s,b.s); } bool operator > ( BigInteger& b){ return b < *this; } bool operator <= ( BigInteger &b){ return !(b < *this); } bool operator >= ( BigInteger &b){ return !(*this < b); } bool operator == ( BigInteger &b){ return !(b < *this) && (*this < b); } //基本四则运算 vector<int> add(vector<int> &A, vector<int> &B); vector<int> sub(vector<int> &A, vector<int> &B); vector<int> mul(vector<int> &A, int b); vector<int> mul(vector<int> &A, vector<int> &B); vector<int> div(vector<int> &A, int b); vector<int> div(vector<int> A, vector<int> B); //重载运算符 BigInteger operator + (BigInteger &b); BigInteger operator - (BigInteger &b); BigInteger operator * (BigInteger &b); BigInteger operator * (int& b); BigInteger operator / (BigInteger & b); BigInteger operator / (int b); }; //重载<< ostream& operator << (ostream &out,const BigInteger& x) { if(x.flag == -1)out << '-'; out << x.s.back(); for(int i = x.s.size() - 2; i >= 0;i--){ char buf[20]; sprintf(buf,"%08d",x.s[i]);//08d此处的8应该与WIDTH一致 for(int j=0;j<strlen(buf);j++)out<<buf[j]; } return out; } //重载输入 istream& operator >> (istream & in,BigInteger & x){ string s; if(!(in>>s))return in; x = s; return in; } vector<int> BigInteger::add( vector<int> &A, vector<int> &B){ if(A.size() < B.size())return add(B,A); int t = 0; vector<int> C; for(int i=0;i<A.size();i++){ if(i<B.size())t += B[i]; t += A[i]; C.push_back(t%BASE); t /= BASE; } if(t)C.push_back(t); while(C.size() > 1 && C.back() == 0)C.pop_back(); return C; } vector<int> BigInteger::sub( vector<int> &A, vector<int> &B){ vector<int> C; for(int i=0,t=0;i<A.size();i++){ t = A[i] - t; if(i<B.size())t -= B[i]; C.push_back((t+BASE)%BASE); if(t < 0)t = 1; else t = 0; } while(C.size() > 1 && C.back() == 0)C.pop_back(); return C; } vector<int> BigInteger::mul(vector<int> &A,int b){ vector<int> C; int t = 0; for(int i = 0;i < A.size() || t; i++){ if(i < A.size()) t += A[i] * b; C.push_back(t%BASE); t /= BASE; } return C; } //大数乘大数乘法需要将BASE设置为10，WIDTH设置为1 vector<int> BigInteger::mul( vector<int> &A, vector<int> &B) { int la = A.size(),lb = B.size(); vector<int> C(la+lb+10,0); for(int i=0;i<la;i++){ for(int j=0;j<lb;j++){ C[i+j] += A[i] * B[j]; } } for(int i=0;i<C.size();i++){ if(C[i] >= BASE){ C[i + 1] += C[i] / BASE; C[i] %= BASE; } } while(C.size() > 1 && C.back() == 0)C.pop_back(); return C; } //大数除以整数 vector<int> BigInteger::div(vector<int> & A,int b){ vector<int> C; int r = 0; for(int i = A.size() - 1;i >= 0;i--){ r = r * 10 + A[i]; C.push_back(r/b); r %= b; } reverse(C.begin(),C.end()); while(C.size() > 1 && C.back() == 0)C.pop_back(); return C; } //大数除以大数 vector<int> BigInteger::div(vector<int> A,vector<int> B){ int la = A.size(),lb = B.size(); int dv = la - lb; // 相差位数 vector<int> C(dv+1,0); //将除数扩大，使得除数和被除数位数相等 reverse(B.begin(),B.end()); for(int i=0;i<dv;i++)B.push_back(0); reverse(B.begin(),B.end()); lb = la; for(int j=0;j<=dv;j++){ while(!cmp(A,B)){ A = sub(A,B); C[dv-j]++; } B.erase(B.begin()); } while(C.size()>1 && C.back() == 0)C.pop_back(); return C; } BigInteger BigInteger::operator + ( BigInteger & b){ BigInteger c; c.s.clear(); c.s = add(s,b.s); return c; }BigInteger BigInteger::operator - ( BigInteger & b) { BigInteger c; c.s.clear(); if(*this < b){ c.flag = -1; c.s = sub(b.s,s); } else{ c.flag = 1; c.s = sub(s,b.s); } return c; } BigInteger BigInteger::operator *(BigInteger & b){ BigInteger c; c.s = mul(s,b.s); return c; } BigInteger BigInteger::operator *(int& b){ BigInteger c; c.s = mul(s,b); return c; } BigInteger BigInteger::operator /(BigInteger & b){ BigInteger c; if(*this < b){ c.s.push_back(0); } else{ c.flag = 1; c.s = div(s,b.s); } return c; } BigInteger BigInteger::operator /(int b){ BigInteger c; BigInteger t = b; if(*this < t){ c.s.push_back(0); } else{ c.flag = 1; c.s = div(s,b); } return c; } int main(){ BigInteger A,B; cin>>A>>B; cout<<A+B<<endl; cout<<A-B<<endl; cout<<A*B<<endl; cout<<A/B<<endl; return 0; }

提交前必看！

有没有爆int，有没有爆longlong？
有没有把数组错开成插入？
有没有把调试信息删除干净？

Template For ACM

一. 字符串

标准库

sscanf

sprintf

strcmp

strcpy

strncpy

strcat

strstr

strchr

strrchr

KMP

EXKMP

Manacher

AC自动机

后缀数组

1. 倍增

2. DC3

3. 求\(height\) 以及 \(lcp\)

后缀自动机

回文自动机

二. 数论

筛质数

质因子分解

正因数集合

Miller Rabin Prollard Rho

高斯消元

矩阵快速幂

欧拉函数

逆元

组合数学相关

三. 数据结构

并查集

带删除并查集

可持久化并查集

带权删除并查集

树链剖分

左偏树

树哈希

线段树合并

分块

莫队

莫队优化

带修莫队

树上莫队

分块套路

主席树

树套树

树状数组套主席树

线段树套线段树

四. 图论

最短路

1. Dijkstra

2. SPFA

3. Floyd

Johnson

最小生成树

1. Kruskal

2. Prim

最小斯坦纳树

树的直径

树上启发式合并

点分治

最近公共祖先

1. 倍增

3. Tarjan

无向图连通性

求割边

割点

边双连通分量 (e-DCC)

点双连通分量(v-DCC) 求法

有向图连通性

欧拉路

二分图

1. 二分图判定

2. 二分图最大匹配

3. 二分图带权最大匹配

虚树

网络流