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.
#include
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; } templatevoid err(const T& arg,const Ts&… args) { cout << arg << " "; err(args…); } const int N = 1000000 + 50; struct Node{ int op, x, y; }o[N]; vector g[N];
int n, m;
int fa[N2], dep[N2], sz[N*2], to[N], tot;
int res[N];
int find(int x){
if(x == fa[x]) return x;
return find(fa[x]);
}
void dfs(int u){
for(auto id : g[u]){
int op = o[id].op, x = o[id].x, y = o[id].y;
if(op == 1){
if(to[x] == -1 || to[y] == -1){
dfs(id);
continue;
}
int rx = find(to[x]), ry = find(to[y]);
if(rx == ry){ dfs(id); continue;}
else if(dep[rx] == dep[ry]){
fa[ry] = rx; sz[rx] += sz[ry]; dep[rx] ++;
dfs(id);
fa[ry] = ry; sz[rx] -= sz[ry]; dep[rx] --;
} else {
if(dep[rx] < dep[ry]) swap(rx, ry);
fa[ry] = rx; sz[rx] += sz[ry];
dfs(id);
fa[ry] = ry; sz[rx] -= sz[ry];
}
} else if(op == 2){
if(to[x] == -1) { dfs(id); continue; }
int rx = find(to[x]);
int t = to[x];
to[x] = -1;
sz[rx] --;
dfs(id);
to[x] = t;
sz[rx] ++;
} else if(op == 3){
if(to[x] == - 1 || to[y] == -1) {dfs(id); continue; }
int t = to[x];
int rx = find(to[x]), ry = find(to[y]);
sz[rx]--;
to[x] = ++tot;
sz[to[x]] = 1;
fa[to[x]] = ry;
sz[ry] ++;
dfs(id);
sz[ry] --;
sz[rx] ++;
to[x] = t;
} else {
if(op == 4){
if(to[x] == -1 || to[y] == -1){
res[id] = 0;
} else {
res[id] = find(to[x]) == find(to[y]);
}
} else if(op == 5){
if(to[x] == -1) res[id] = 0;
else {
res[id] = sz[find(to[x])];
}
}
dfs(id);
}
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i=1;i<=m;i++){
int op, k, x, y = 0;scanf("%d%d%d", &op, &k, &x);
g[k].push_back(i);
if(op != 2 && op != 5) scanf("%d", &y);
o[i] = {op, x, y};
}
for(int i=1;i<=n;i++) to[i] = i, fa[i] = i, sz[i] = 1;
tot = n;
dfs(0);
for(int i=1;i<=m;i++){
if(o[i].op == 4) puts(res[i] ? "Yes" : "No");
else if(o[i].op == 5){
printf("%d\n", res[i]);
}
}
return 0;
}
树链剖分
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;
}最近公共祖先
1. 倍增
onst int SZ = 50010;
int f[SZ][20],d[SZ],dist[SZ];//开足空间
int ver[2*SZ],nxt[2*SZ],edge[2*SZ],head[2*SZ];
int T,n,m,tot,t;
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 bfs(){ // dfs或者bfs都可以，d[1]一定要为1
q.push(1);d[1] = 1;
while(q.size()){
int x = q.front();q.pop();
for(int i=head[x];i;i=nxt[i]){
int y = ver[i];
if(d[y])continue;
d[y] = d[x] + 1;
dist[y] = dist[x] + edge[i];
f[y][0] = x;
for(int j=1;j<=t;j++)
f[y][j] = f[f[y][j-1]][j-1];
q.push(y);
}
}
}
int lca(int x,int y){
if(d[x] > d[y])swap(x,y);//x在y上面
for(int i=t;i>=0;i--){
if(d[f[y][i]] >= d[x]) y = f[y][i];//不断往上面调整
}
if(x == y)return x;
for(int i=t;i>=0;i--){
if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
}
return f[x][0];
}3. Tarjan
线性离线，不太常用，但离线，结合并查集的思想值得借鉴
#include <bits/stdc++.h>
using namespace std;
const int N = 50010;
int ver[2*N],nxt[2*N],edge[2*N],head[N];
int fa[N],d[N],v[N],lca[N],ans[N];
vector<int> query[N],query_id[N];
int T,n,m,tot,t;
void add(int x,int y,int z){
ver[++tot] = y;edge[tot] = z;nxt[tot] = head[x];head[x] = tot;
}
void add_query(int x,int y,int id){
query[x].push_back(y);query_id[x].push_back(id);
query[y].push_back(x);query_id[y].push_back(id);
}
int find(int x){
return x==fa[x]?x:fa[x] = find(fa[x]);
}
void tarjan(int x){
v[x] = 1;
for(int i=head[x];i;i=nxt[i]){
int y = ver[i];
if(v[y])continue;
d[y] = d[x] + edge[i];
tarjan(y);
fa[y] = x;
}
for(int i=0;i<query[x].size();i++){
int y = query[x][i],id = query_id[x][i];
if(v[y] == 2){
int lca = find(y);
ans[id] = min(ans[id],d[x] + d[y] - 2*d[lca]);
}
}
v[x] = 2;
}
int main(){
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++){
head[i] = 0;fa[i] = i;v[i] = 0;
query[i].clear();query_id[i].clear();
}
tot = 0;
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++){
int x,y;
scanf("%d%d",&x,&y);
if(x == y)ans[i] = 0;
else{
add_query(x,y,i);
ans[i] = 1 << 30;
}
}
tarjan(1);
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
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？
- 有没有把数组错开成插入？
- 有没有把调试信息删除干净？
手机扫一扫
移动阅读更方便
你可能感兴趣的文章