#include<iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<ctime>
#include<bitset>
#include<iterator>
#define bug cout<<"-----------"<<endl;
#define ll  long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define fi first
#define se second
using namespace std;
const int N=1e5+5,M=1e9+7;
const ull base=13331;
const double Pi=acos(-1.0);
const int inf=0x3f3f3f3f;
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*10+ch-'0';ch=getchar();}
    return x*f;
}
int main(){
	ios::sync_with_stdio(false);
}

import java.util.*;
import java.math.*;
import java.io.*;
import java.text.*;

public class Main{
	final static int N=100005;
	public static void main(String[] args){
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);

		Task solver = new Task();
		solver.solve(1, in, out);

		out.close();
	}
	static class Task{
		public void solve(int testNumber, InputReader in, PrintWriter out) {



		}
	}
	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
			
		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}
	}
}

基本算法

排序

逆序对

cf-1753E

有一长度为n的数列a，a有m个逆序对，对一逆序对<u,v>，定义swap(a[u],a[v])为一次交换，问能否将m个逆序对排序，使得按排序后的顺序进行m次交换后，数列a按非降序排序，如果有，请输出逆序对的顺序，如果有多个可能的答案，请输出其中一种

对于x，假设小于x的数全部

int a[N];
struct node{
	int x,id;
}b[N];
bool cmp(node n,node m){
	if(n.x==m.x)return n.id<m.id;
	return n.x<m.x;
}
int main(){
    ios::sync_with_stdio(false);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>b[i].x;a[i]=b[i].x;
    	b[i].id=i;
    }
    std::vector<pair<int,int> > ans;
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++){
    	int id=b[i].id;
    	for(int j=n;j>id;j--){
    		if(a[j]<b[i].x)ans.pb(mp(id,j));
    	}
    }
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++){
    	cout<<ans[i].first<<' '<<ans[i].second<<endl;
    }
}

倍增

int p=1;
int sum=0;
while(p){
    if(a[sum+p]<=k){
        sum+=p;
        p*=2;
    }
    else p/=2;
}
cout<<sum<<endl;

ST算法

int n;
int f[N][40];
int a[N];
void ST_prework(){
	for(int i=1;i<=n;i++)
		f[i][0]=a[i];
	int t=log(n)/log(2)+1;
	for(int j=1;j<t;j++){
		int l=(1<<(j-1));
		for(int i=1;i<=n-2*l+1;i++)
			f[i][j]=max(f[i][j-1],f[i+l][j-1]);
	}
}
int ST_query(int l,int r){
	int k=log(r-l+1)/log(2);
	return max(f[l][k],f[r-(1<<k)+1][k]);
}

字符串

周期引理（Periodicity Lemma）

假设一个字符串$S$有循环节$p$和$q$并且满足$p+q\leq|S|+gcd(p,q)$，那么$gcd(q,q)$也是一个循环节。

对于两个循环节分别为$p,q$的且长度相同并大于$p+q-gcd(p,q)$的字符串$s,t$，只需比较前$p+q-gcd(p,q)$个字符即可判断两者字典序大小。

因为若前$p+q-gcd(p,q)$项匹配，则整个字符串一定都是匹配的，即不会出现前$p+q-gcd(p,q)$项匹配，但后面不匹配的现象。

KMP

如果len能被len-Next[len]整除，则该字符串按a[1…len-Next[len]]循环。

int Next[N];          ///Next[i]表示的是前i的字符组成的这个子串最长的相同前缀后缀的长度
void cacl_Next(char *a){
    Next[1]=0;int n=strlen(a+1);
    for(int i=2,j=0;i<=n;i++){
        while(j>0&&a[i]!=a[j+1])j=Next[j];
        if(a[i]==a[j+1])j++;
        Next[i]=j;
    }
}
int f[N];
int kmp(char *a,char *b){
    cacl_Next(b);int lena=strlen(a+1);
    int ans=0,lenb=strlen(b+1);
    for(int i=1,j=0;i<=lena;i++){
        while(j>0&&(j==lena||a[i]!=b[j+1]))j=Next[j];
        if(a[i]==b[j+1])j++;
        f[i]=j;if(f[i]==lenb)ans++;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    char a[N],b[N];
    cin>>(a+1);
    cin>>(b+1);
    cout<<kmp(a,b)<<endl;
}

exKMP

int Next[N],extends[N];
void cacl_Next(char *a){
	int i=1,po=2,len=strlen(a+1);
	Next[1]=len;
	while(a[i]==a[i+1]&&i+1<=len)i++;
	Next[2]=i-1;
	for(i=3;i<=len;i++){
		if(Next[i-po+1]+i<Next[po]+po)Next[i]=Next[i-po+1];	//第一种情况，可以直接得到next[i]的值  
		else{	//第二种情况，要继续匹配才能得到next[i]的值
			int j=Next[po]+po-i+1;if(j<1)j=1;	//如果i>po+next[po],则要从头开始匹配  
			while(i+j-1<=len&&a[j]==a[j+i-1])j++;
			Next[i]=j-1;
			po=i;
		}
	}
}
void exkmp(char *a,char *b){
	int i=1,po=1,lena=strlen(a+1),lenb=strlen(b+1);
	cacl_Next(b);
	while(a[i]==b[i]&&i<=min(lena,lenb))i++;
	extends[1]=i-1;
	for(i=2;i<=lena;i++){
		if(Next[i-po+1]+i<extends[po]+po)extends[i]=Next[i-po+1];	//第一种情况，可以直接得到extends[i]的值  
		else{	//第二种情况，要继续匹配才能得到edtends[i]的值
			int j=extends[po]+po-i+1;if(j<1)j=1;	//如果i>po+extends[po],则要从头开始匹配  
			while(i+j-1<=lena&&j<=lenb&&b[j]==a[j+i-1])j++;
			extends[i]=j-1;
			po=i;
		}
	}
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    char a[N],b[N];
    cin>>(a+1)>>(b+1);
    exkmp(a,b);
    for(int i=1;i<=strlen(b+1);i++){
    	cout<<Next[i];
    	if(i==strlen(b+1))cout<<endl;
    	else cout<<' ';
    }
    for(int i=1;i<=strlen(a+1);i++){
    	cout<<extends[i];
    	if(i==strlen(a+1))cout<<endl;
    	else cout<<' ';
    }
}

manacher

int pal[N*2],cnt[N],len=1;
//pal[i]表示更改后的字符串，以i为中心的最大回文串的半径
char s[N*2];
void manacher(char *a){
	int tot=0;s[tot]='$',s[++tot]='#';
	int lena=strlen(a+1);
	for(int i=1;i<=lena;i++){
		s[++tot]=a[i],s[++tot]='#';
	}
	int mid=0,r=0;
	for(int i=1;i<=tot;i++){
		pal[i]=r>i?min(pal[2*mid-i],r-i):1;
		//当 r>i 当然是要选一个小的来赋值，这样就可以防止超出r了
        //当 r<=i时，此处的长度为1，直接进入暴力枚举它的长度
		while(s[i+pal[i]]==s[i-pal[i]])pal[i]++;
		//暴力枚举后边的是不是回文串，以使它的长度增加。
		if(i+pal[i]>r)r=i+pal[i],mid=i;
		//最右端回文串的长度超出r后就要进行r和mid的更新了
		if(len<pal[i]-1)len=pal[i]-1;
	}
    for(int i=2;i<=lena*2;i++) //差分记录
    {
        if(pal[i]>2)
        cnt[i/2]++,cnt[(i/2)+(pal[i]-1)/2]--;
    }
    //cnt[i-1]表示a串中以第i位为右端点的回文子串的个数
    cnt[0]=1;//所有单个字符都是回文串
    for(int i=1;i<lena;i++) cnt[i]+=cnt[i-1]; 
}
char a[N];
int main() {
	scanf("%s",a+1);
	manacher(a);
	printf("%d\n",len);
}

后缀自动机

博客

endpos(v)包含于endpos(link(v))

由link可以遍历一个字串的有相同后缀的所有字串

由Next可以从0开始找到所有字串

int len[N*2],link[N*2],Next[N*2][26],sz,last;
void sam_init(){
	len[0]=0,link[0]=-1;
	sz=1,last=0;
}
void sam_extend(int c){
	int cur=sz++;
	len[cur]=len[last]+1;
	int p=last;last=cur;
	while(p!=-1&&!Next[p][c])Next[p][c]=cur,p=link[p];
	if(p==-1)link[cur]=0;
	else{
		int q=Next[p][c];
		if(len[q]==len[p]+1)link[cur]=q;
		else{
			int clone=sz++;
			link[clone]=link[q];
			len[clone]=len[p]+1;
			memcpy(Next[clone],Next[q],sizeof(Next[q]));
			while(p!=-1&&Next[p][c]==q)Next[p][c]=clone,p=link[p];
			link[q]=link[cur]=clone;
		}
	}
}
///求字串出现的次数
char s[N];
int head[N*2],Ne[N*2],ver[N*2],tot=0;
ll cnt[N*2];
void add(int x,int y){
	ver[++tot]=y;
	Ne[tot]=head[x],head[x]=tot;
}
void dfs(int x){
	for(int i=head[x];i;i=Ne[i]){
		dfs(ver[i]);
		cnt[x]+=cnt[ver[i]];
	}
}
int main(){
	scanf("%s",s);sam_init();
	int n=strlen(s);
	for(int i=0;i<n;i++){
		sam_extend(s[i]-'a');
	}
    for(int i=1;i<sz;i++){
		add(link[i],i);
	}
	dfs(0);
}

搜素

拓扑排序

int head[N],Next[2*N],ver[2*N],tot=0;
int in[N];
void add(int x,int y){
	ver[++tot]=y;
	Next[tot]=head[x];
	head[x]=tot;
	in[y]++;
}
int a[N];
int cnt=0;
int n,m;
void topsort(){
	queue<int> Q;
	for(int i=1;i<=n;i++){
		if(in[i]==0)Q.push(i);
	}
	while(!Q.empty()){
		int x=Q.front();
		Q.pop();
		a[++cnt]=x;
		for(int i=head[x];i;i=Next[i]){
			int y=ver[i];
			if(--in[y]==0){
				Q.push(y);
			}
		}
	}
}

剪枝

POJ-1011

int a[105],v[105],n,len,cnt;
bool dfs(int stick,int cab,int last){
	if(stick>cnt)return true;
	if(cab==len)return dfs(stick+1,0,1);
	int fail=0;
	for(int i=last;i<=n;i++){
		if(v[i])continue;
		if(cab+a[i]>len)continue;
		if(fail==a[i])continue;
		v[i]=1;
		if(dfs(stick,cab+a[i],i+1))return true;
		fail=a[i];
		v[i]=0;
		if(cab==0||cab+a[i]==len)return false;
	}
	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	while(cin>>n){
		if(n==0)break;
		int sum=0,val=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			sum+=a[i];
			val=max(val,a[i]);
		}
		sort(a+1,a+n+1);
		reverse(a+1,a+n+1);
		for(len=val;len<=sum;len++){
			if(sum%len)continue;
			cnt=sum/len;
			memset(v,0,sizeof(v));
			if(dfs(1,0,1))break;
		}
		cout<<len<<endl;
	}
}

迭代加深

int n;
int a[105],v[1050];
int m;
bool dfs(int k,int vv){
	if(vv==n)return true;
	if(vv>n)return false;
	if(k>m)return false;
	for(int i=k;i>=1;i--){
		for(int j=i;j>=1;j--){
			if(v[a[i]+a[j]]||a[i]+a[j]>n)continue;
			if(a[i]+a[j]<=a[k])break;
			a[k+1]=a[i]+a[j];
			v[a[i]+a[j]]=1;
			if(dfs(k+1,a[i]+a[j]))return true;
			a[k+1]=0;
			v[a[i]+a[j]]=0;
		}
	}
	return false;
}
int main()
{
	//ios::sync_with_stdio(false);
	while(~scanf("%d",&n)&&n){
		if(n==1){
			cout<<1<<endl;
			continue;
		}
		if(n==2){
			cout<<"1 2"<<endl;
			continue;
		}
		for(m=2;m<=10;m++){
			memset(a,0,sizeof(a));
			memset(v,0,sizeof(v));
			v[1]=1;
			a[1]=1;a[2]=2;
			if(dfs(2,1))break;
		}
		for(int i=1;i<=m;i++){
			cout<<a[i]<<' ';
		}
		cout<<n<<endl;
	}
}

双向搜索（折半搜索）

CH-2401

int n,W,t;
int a[50];
int a1[30],a2[30];
ll num[N];
int tot=0;
void dfs1(int x,ll w){
	if(w>W)return;
	if(x>t){
		num[++tot]=w;
		return;
	}
	dfs1(x+1,w+(ll)a1[x]);
	dfs1(x+1,w);
}
ll ans=0;
void dfs2(int x,ll w){
	if(w>W)return;
	if(x>n-t){
		int p=lower_bound(num+1,num+tot+1,W-w)-num;
		if(num[p]==W-w)ans=max(ans,num[p]+w);
		else ans=max(ans,num[p-1]+w);
		return;
	}
	dfs2(x+1,w+(ll)a2[x]);
	dfs2(x+1,w);
}
int main()
{
	ios::sync_with_stdio(false);	
	cin>>W>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	reverse(a+1,a+n+1);
	t=n/2+2;
	for(int i=1;i<=t;i++)a1[i]=a[i];
	for(int i=1;i<=n-t;i++)a2[i]=a[t+i];
	dfs1(1,(ll)0);
	sort(num+1,num+tot+1);
	tot=unique(num+1,num+tot+1)-num-1;
	dfs2(1,(ll)0);
	cout<<ans<<endl;
}

数论

积性函数

定义：

数论函数：定义域为正整数的函数

积性函数：满足若a⊥b，那么$ f(ab)=f(a)f(b) $的数论函数

完全积性函数：对于任何$a,b$，满足$f(ab)=f(a)f(b)$

常见的积性函数：

单位函数：$e(n)=[n=1]$

欧拉函数：$\varphi (n)=\sum_{i=1}^{n}[gcd(i,n)=1]=n\prod_{i=1}^{k}(1-\frac{1}{p_{i}})$

幂函数：$Id_{a}(n)=n^{a}$

除数函数：$\sigma (n)=\sum_{d|n}^{n}d$

莫比乌斯函数：$\mu (n)=[max(c_{1},c_{2}...c_{k})\leq 1](-1)^{k}$

$ Dirichlet $卷积

$h(n)=(f*g)(n)=\sum_{i|n}f(i)g(\frac{n}{i})$

对于任意的$f\neq 0$，存在$g*f=e$

$g(n)=\frac{1}{f(1)}([n=1]-\sum_{i|n,i\neq1}g(\frac{n}{i}) )$

性质：

卷积乘满足交换律，结合律，分配律

两个积性函数的卷积是积性函数

一个积性函数的逆也是积性函数

$e=\mu*1$

$Id=\varphi*1$

---

反演：

已知$ g(n)=\sum_{i|n}f(i) $，求$ f(n) $：$f(n)=\sum_{i|n}g(i)\mu(\frac{n}{i}) $

已知$ g(n)=\sum_{n|d}f(d) $，求 $ f(n) $ ：$f(n)=\sum_{n|d}g(d)\mu(\frac{d}{n}) $

---

经典的套路

1.枚举gcd的取值

2.交换倍数和约数

3.用莫比乌斯函数求和替换$[a=1]$这类表达式

4.改写求和指标

5.整除分块，遇到$n(mod)i$ 时转化为 $n-(n/i)*i$

6.已知$f(n)$，求$g=f*1$

对$n$质因子分解，$n=\prod_{i=1}^{cnt}p_{i}^{c_{i}}$，则：

$g(n)=\prod_{i=1}^{cnt}\sum_{j=0}^{c_{i}}f(p_{i}^{j})$

7.现在有积性函数$f(n)$，设$n<m$，则：

$\sum_{i=1}^{n}\sum_{j=1}^{m}f(gcd(i,j))$

$=\sum_{i=1}^{d}f(d)\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(i,j)=1]$

$=\sum_{i=1}^{d}f(d)\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}\sum_{p|i,p|j}\mu (p)$

$=\sum_{i=1}^{d}f(d)\sum_{p=1}^{\frac{n}{d}}\mu (p)\left \lfloor \frac{n}{pd} \right \rfloor\left \lfloor \frac{m}{pd} \right \rfloor$

$=\sum_{D=1}^{n}\sum_{d|D}f(d)\mu (\frac{D}{d})\left \lfloor \frac{n}{D} \right \rfloor\left \lfloor \frac{m}{D} \right \rfloor$

---

杜教筛

给定 $f(n)$，求 $s(n)=\sum_{i=1}^{n}f(i)$

考虑构造积性函数$h,g$，满足 $h=f*g$且 $h$ 的前缀和易求

$\sum_{i=1}^{n}h(i)=\sum_{i=1}^{n}\sum_{d|i}f(d)g(\frac{i}{d})$

$=\sum_{i=1}^{n}g(i)\sum_{j=1}^{\frac{n}{i}}f(j)$

$=\sum_{i=1}^{n}g(i)s(\frac{n}{i})$

$=g(1)s(n)+\sum_{i=2}^{n}g(i)s(\frac{n}{i})$

$\therefore g(1)s(n)=\sum_{i=1}^{n}h(i)-\sum_{i=2}^{n}g(i)s(\frac{n}{i})$

可以证明，复杂度为$O(n^\frac{2}{3})$

---

关于杜教筛一些简单的套路

$s(n)=\sum_{i=1}^{n} \varphi (i)\Rightarrow \frac{n*(n+1)}{2}-\sum_{d=2}^{n}s(\frac{n}{d})$

$s(n)=\sum_{i=1}^{n} \mu (i)\Rightarrow 1-\sum_{d=2}^{n}s(\frac{n}{d})$

$s(n)=\sum_{i=1}^{n} i \varphi (i)\Rightarrow \frac{n*(n+1)(2n+1)}{6}-\sum_{d=2}^{n}s(\frac{n}{d})d$

(考虑构造 $h=\sum_{d|n}( d \varphi (d) )\frac{n}{d}=n\sum_{d|n}\varphi (d)=n^{2}$)

---

代码的实现

#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
using namespace std::tr1;
typedef long long LL;
const int N=3e6+5,M=3e6;
int prime[N];
LL phi[N];
bool vis[N];
int mu[N];
unordered_map<int,int>smu;
unordered_map<int,LL>sphi;
int Smu(int x){
    if(x<=M)return mu[x];
    if(smu[x])return smu[x];
    int ret=1;
    for(int l=2,r=0;r!=x;l=r+1){
        r=x/(x/l);
        ret-=1ll*(r-l+1)*Smu(x/l);
    }
    return smu[x]=ret;
}
LL Sphi(int x){
    if(x<=M)return phi[x];
    if(sphi[x])return sphi[x];
    LL ret=1ll*x*(1ll*x+1)/2;
    for(int l=2,r=0;r!=x;l=r+1){
        r=x/(x/l);
        ret-=1ll*(r-l+1)*Sphi(x/l);
    }
    return sphi[x]=ret;
}
void init()
{
    phi[1]=mu[1]=1;
    for(int i=2;i<=M;i++){
        if(!vis[i])prime[++prime[0]]=i,mu[i]=-1,phi[i]=i-1;
        for(int j=1;j<=prime[0]&&i*prime[j]<=M;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=2;i<=M;i++)phi[i]+=phi[i-1],mu[i]+=mu[i-1];
}
int main(){
    init();
    int T;cin>>T;
    while(T--){
        int n;scanf("%d",&n);
        cout<<Sphi(n)<<' '<<Smu(n)<<'\n';
    }
    return 0;
}

min25筛

设$f(i)$是一个积性函数，满足$f(p),p \in prime$可以用多项式表示，同时$f(p^k)$可以快速计算出来

考虑如何求解$\sum _{i=1}^nf(i)(1<n<10^{11})$

---

另一个新的问题：对于积性函数$f(i)$，求$\sum_{i=1}^n[i \in prime] f(i)$

为了方便理解,问题变为求$\sum_{i=1}^n[i \in prime] i^k$

定义$prime_i$为第$i$个质数，$minp(i)$为$i$的最小质因子，令$minp(1)=inf$

对于$\sqrt n$范围内的前$i$个质数的$k$次方前缀和$sum_i=\sum _{j=1}^i prime_j^k$可以线性筛解决

设$g(n,i)=\sum_{j=1}^n[j \in prime $ $or$ $ minp(j)>prime_i]j^k$

直观地来看，$g(n,i)$就是在 $n$ 范围内的埃式筛算法进行第$i$轮后尚未被筛去的数的 $k$ 次方和

显然，$g(n,0)=\sum_{i=2}^ni^k$

思考从$g(n,i-1)$到$g(n,i)$的转移

• $prime_i^2>n$，在埃氏筛的第 $i$ 轮没有数字被筛掉，$g(n,i)=g(n,i-1)$

• $prime_i^2 \leq n$，考虑$prime_i$在$g(n,i-1)$中的贡献，$g(n,i)=g(n,i-1)-prime_i^k(g(\left \lfloor \frac{n}{prime_i}\right \rfloor,i-1)-sum_{i-1})$

令$cnt$为$\sqrt n$范围内的质数个数，有

$\sum_{i=1}^n[i \in prime] i^k=sum_{cnt}+g(n,cnt)$

时间复杂度 $O(\frac{n^{3/4}}{logn})$

---

现在问题回归到求解$\sum _{i=1}^nf(i)$

定义$s(n,i)=\sum_{j=1}^n[minp(j) \geq prime_i] f(j)$

那么，$\sum _{i=1}^nf(i)=s(n,1)+f(1)$

问题最终化为如何求解$s(n,i)$

因为$\sum_{i=1}^n[i \in prime] f(i)$已经可以快速计算，那么不难得到答案中质数的贡献$\sum_{j=1}^n[j \in prime] f(j)-\sum_{j=1}^{i-1}f(prime_j)$

考虑合数的贡献，枚举每个合数的最小质因子以及最小质因子的次幂，由$f$为积性函数得

$\sum_{j=1}^{prime_j^2 \leq n}\sum_{k=1}^{prime_j^{k+1} \leq n} ( s( \left \lfloor \frac{n}{prime_j^k}\right \rfloor,j+1)f(prime_j^k)+f(prime_j^{k+1}))$

---

min_25筛求出$n$以内的质数和与质数个数

---

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int M=1e6+5,mod=1e9+7,inv2=500000004;
int prime[M],tot,vis[M],sqr,sum[M],id1[M],id2[M],m,g[M],h[M];
ll n,w[M];
void init(int siz)
{
    for(int i=2;i<=siz;i++)
    {
        if(!vis[i])prime[++tot]=i,sum[tot]=(sum[tot-1]+i)%mod;
        for(int j=1;j<=tot&&i*prime[j]<=siz;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int getid(ll x){return (x<=sqr)?id1[x]:id2[n/x];}
ll s(ll x,int y)
{
    if(x<=1||prime[y]>x)return 0;
    int pos=getid(x);
    ll res=(g[pos]-sum[y-1]-h[pos]+y-1+mod)%mod;
    if(y==1)res+=2;
    for(int i=y;i<=tot&&(ll)prime[i]*prime[i]<=x;i++)
    {
        ll p1=prime[i];
        ll p2=p1*p1;
        for(int e=1;p2<=x;e++,p1=p2,p2*=prime[i])
            res=(res+s(x/p1,i+1)*(prime[i]^e)%mod+(prime[i]^(e+1))%mod)%mod;
    }
    return res;
}
int main()
{
    scanf("%lld",&n);
    sqr=sqrt(n);
    init(sqr);
    for(ll l=1,r=0;l<=n;l=r+1)
    {
        w[++m]=n/l;
        r=n/w[m];
        if(w[m]<=sqr)id1[w[m]]=m;
        else id2[n/w[m]]=m;
        g[m]=((2+w[m])%mod)*((w[m]-1)%mod)%mod*inv2%mod;
        h[m]=(w[m]-1)%mod;
    }
    for(int j=1;j<=tot;j++)
        for(int i=1;i<=m&&(ll)prime[j]*prime[j]<=w[i];i++)
        {
            int k=getid(w[i]/prime[j]);
            g[i]=(g[i]-(ll)prime[j]*((g[k]-sum[j-1]+mod)%mod)+mod)%mod;
            h[i]=(h[i]-h[k]+j-1+mod)%mod;
        }
    printf("%lld\n",(s(n,1)+1)%mod);
    return 0;
}

线性基

异或空间下的线性基

线性基是一个数的集合，并且每个序列都拥有至少一个线性基，取线性基中若干个数异或起来可以得到原序列中的任何一个数

---

线性基的性质

1.原序列里面的任意一个数都可以由线性基里面的一些数异或得到

2.线性基里面的任意一些数异或起来都不能得到0

3.线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的

---

构造线性基

typedef long long int lli;
lli d[64];
void add(lli x)
{
    for(int i=63;i>=0;i--)if((x>>i)&1)
        if(d[i])x^=d[i];
        else{d[i]=x;break;}
}

对基底进一步处理

int tot;
void work()
{
    for(int i=63;i>=0;i--)
    {
        for(int j=i-1;j>=0;j--)if((d[i]>>j)&1)d[i]^=d[j];
        if(d[i])tot++;
    }
}

---

区间异或求最值问题

求最大值：贪心，初始答案为0，从线性基的最高位开始，假如当前的答案异或线性基的这个元素可以变得更大，那么就异或它

求最小值：最小值一定是最小的一个基底，因为如果让它去异或其它的
基底，一定会让它变得更大，所以它自己就是最小的

求第k大的值：

处理完线性基后，首先要计算，$n$个元素的线性基有$tot$个，$tot<n$时将$k$变为$k-1$ ，因为此时线性基中只能求不为0的解，而实际n个可以异或得到0

将$k$先转成二进制，假如$k$的第$i$位为$1$，$ans$就异或上线性基中第$i$个元素

#include <bits/stdc++.h>
using namespace std;
#define mset(var,val) memset(var,val,sizeof(var))
typedef long long int lli;
int n,tot,cas;
lli d[64];
void add(lli x)
{
    for(int i=63;i>=0;i--)if((x>>i)&1)
        if(d[i])x^=d[i];
        else{d[i]=x;break;}
}
void work()
{
    for(int i=63;i>=0;i--)
    {
        for(int j=i-1;j>=0;j--)if((d[i]>>j)&1)d[i]^=d[j];
        if(d[i])tot++;
    }
}
int main(int argc, char const *argv[])
{
    int t;scanf("%d",&t);
    while(t--)
    {
        tot=0;mset(d,0);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            lli x;scanf("%lld",&x);
            add(x);
        }
        work();
        printf("Case #%d:\n",++cas);
        int m;scanf("%d",&m);
        while(m--)
        {
            unsigned long long k;
            cin>>k;
            if(tot<n)k--;
            if(k>=(1llu<<tot)){printf("-1\n");continue;}
            lli ans=0;
            for(int i=0;i<=63;i++)if(d[i])
            {
                if(k%2==1)ans^=d[i];
                k/=2;
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}

C(n,m)

ll fac[N],r[N],g[N];
void init(){
    fac[0]=fac[1]=1;r[1]=g[0]=g[1]=1;
    for(int i=2;i<N;i++){
        fac[i]=(ll)fac[i-1]*i%M;
    	r[i]=(ll)(M-M/i)*r[M%i]%M;
		g[i]=(ll)g[i-1]*r[i]%M;
    }
}
inline int nCm(int n, int m) {
	if(m<0||m>n)return 0;
	return (ll)fac[n]*g[m]%M*g[n-m]%M;
}

生成函数

多项式乘除法

HDU-6795 2020杭电多校第三场1005

struct Generating_function{
	ll ki[4][7];int n=3,m=6;
	void init(){
		memset(ki,0,sizeof(ki));
		ki[0][0]=1;
	}
	void mult(ll a,ll b){
		for(int i=n;i>=1;i--){
			for(int j=m;j>=1;j--){
				ki[i][j]=(ki[i][j]+a*ki[i-1][j-1]%M)%M;
				if(j>1)ki[i][j]=(ki[i][j]+b*ki[i-1][j-2]%M)%M;
			}
		}
	}
	void div(ll a,ll b){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				ki[i][j]=(ki[i][j]-a*ki[i-1][j-1]%M+M)%M;
				if(j>1)ki[i][j]=(ki[i][j]-b*ki[i-1][j-2]%M+M)%M;
			}
		}
	}
	ll get(){
		return (ki[3][5]+ki[3][6])%M;
	}
}solve;
int fa[N];ll a[N],b[N];
int get(int x){
	if(x==fa[x])return x;
	return fa[x]=get(fa[x]);
}
int main(){
    ios::sync_with_stdio(false);
    int t;cin>>t;
    while(t--){
    	int n;cin>>n;solve.init();
    	for(int i=1;i<=n;i++){
    		int x;cin>>x;
    		fa[i]=i,a[i]=b[i]=0;
    		if(x==1)a[i]=1;
    		else b[i]=1;
    		solve.mult(a[i],b[i]);
    	}
    	cout<<solve.get()<<endl;
    	int q=n-1;
    	while(q--){
    		int u,v;cin>>u>>v;
    		u=get(u),v=get(v);
    		ll u1=a[u],u2=b[u];
    		ll v1=a[v],v2=b[v];
    		solve.div(u1,u2);
    		solve.div(v1,v2);
    		fa[u]=v;
    		int x=get(u);
    		a[x]=u1+v1;
    		b[x]=u2+v2;
    		solve.mult(a[x],b[x]);
    		cout<<solve.get()<<endl;
    	}
    }
}

欧拉函数

phi(x)还等于a+1~a+x中与x互质的数的个数，其中gcd(a,x)=1且a<x

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

质数

欧拉筛

ll phi[N+10];
bool vis[N+10];
ll prime[N+10];
ll miu[N+10];
ll tot;
void init(){
    miu[1]=1;
    tot = 0;
    for(ll i = 2; i <=N; i ++)
    {
        if(!vis[i])
        {
            prime[tot ++] = i;
            phi[i] = i - 1;
            miu[i]=-1;
        }
        for(ll j = 0; j < tot; j ++)
        {
            if(i * prime[j] >= N) break;
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0)
            {
                miu[i*prime[j]]=0;
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else
            {
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
                miu[i*prime[j]]=-1*miu[i];
            }
        }
    }
}

求1到x内与k互质的数的个数

ll a[N];
int tot=0;
ll ans;
ll sol(ll x){
    if(x<0)return 0;
    ll sum=0;
    for(int i=1;i<(1<<tot);i++){
        ll cnt=0;
        ll mul=1;
        for(int j=1;j<=tot;j++){
            if(i&(1<<(j-1))){
                cnt++;
                mul*=a[j];
            }
        }
        if(cnt&1)sum+=x/mul;
        else sum-=x/mul;
    }
    return x-sum;
}
int main(){
    ll k,x;
    cin>>k>>x;
    ll h=k;
    for(ll i=2;i*i<=h;i++){
        if(h%i==0){
            a[++tot]=i;
            while(h%i==0)h/=i;
        }
    }
    if(h>1)a[++tot]=h;
    cout<<sol(x)<<endl;
}

沃利斯积分和沃利斯公式

$$\int^1_0(x-x^2)^n{\rm d}x=\frac{{(n!)}^2}{(2n+1)!}\\ \int^{\frac{\pi}{2}}_0\sin^mxdx=\frac{(m-1)!!}{m!!}(m为奇数整数)\\ \int^{\frac{\pi}{2}}_0\sin^mxdx=\frac{(m-1)!!}{m!!}\frac{\pi}{2}(m为偶数整数)$$

动态规划

斜率优化

ll a[N],s[N],f[N],dp[N],c;
double slop(int j,int k){
	return (dp[j]-dp[k]+f[j]*f[j]-f[k]*f[k]+2*c*f[j]-2*c*f[k])/(2.0*(f[j]-f[k]));
}
int st[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;ll L;cin>>n>>L;c=L+1;
    for(int i=1;i<=n;i++)cin>>a[i];
    s[0]=0;for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
	for(int i=1;i<=n;i++)f[i]=s[i]+i;
	int l=1,r=1;st[1]=0;
	for(int i=1;i<=n;i++){
		while(l<r&&slop(st[l+1],st[l])<=f[i])l++;
		int t=st[l];
		dp[i]=dp[t]+(f[i]-f[t]-c)*(f[i]-f[t]-c);
		while(l<r&&slop(st[r],st[r-1])>slop(i,st[r]))r--;
		st[++r]=i;
	}
	cout<<dp[n]<<endl;
}

数据结构

栈

单调栈

int p;
memset(s,0,sizeof(s));
a[n+1]=p=0;
ll ans=0;
for(int i=1;i<=n+1;i++)
{
    if(a[i]>s[p]){
        s[++p]=a[i];
        w[p]=1;
    }
    else{
        int width=0;
        while(a[i]<s[p]){
            width+=w[p];
            ans=max(ans,(ll)width*s[p]);
            p--;
        }
        w[++p]=width+1;
        s[p]=a[i];
    }
}

单调队列护区间最大值

int a[N],st[N];
int l=m+1,r=m;st[r]=1;
for(int i=1;i<=n;i++){
    while(l<=r&&a[st[l]]<=a[i])l++;
    st[--l]=i;
    if(st[r]<i-k+1)r--;
    if(i>=k)ans+=a[st[r]];
}

Trie(字典树)

int trie[N][26],tot=1;
bool end[N];
void insert(char *str)
{
    int len=strlen(str),p=1;
    for(int k=0;k<len;k++){
        int ch=str[k]-'a';
        if(trie[p][ch]==0)trie[p][ch]=++tot;
        p=trie[p][ch];
    }
    end[p]=true;
}
bool search(char *str)
{
    int len=strlen(str),p=1;
    for(int k=0;k<len;k++){
        int ch=str[k]-'a';
        if(trie[p][ch]==0)return false;
        p=trie[p][ch];
    }
    return end[p];
}

前缀统计

//CH1601
int trie[N][26],tot=1;
int End[N];
void insert(char *str)
{
	int len=strlen(str),p=1;
	for(int k=0;k<len;k++){
		int ch=str[k]-'a';
		if(trie[p][ch]==0)trie[p][ch]=++tot;
		p=trie[p][ch];
	}
	End[p]++;
}
int search(char *str)
{
	int ans=0;
	int len=strlen(str),p=1;
	for(int k=0;k<len;k++){
		int ch=str[k]-'a';
		p=trie[p][ch];
		if(p==0)return ans;
		ans+=End[p];
	}
	return ans;
}
char c[N];
int main()
{
	int n,m;
	n=read(),m=read();
	while(n--){
		scanf("%s",c);
		insert(c);
	}
	while(m--){
		scanf("%s",c);
		printf("%d\n",search(c));
	}
}

XOR

int tire[N*30][2],tot=0;
void insert(int x,int d){
	int p=0;
	for(int i=d;i>=0;i--){
		int h=(x>>i)&1;
		if(tire[p][h]==0){
			tire[p][h]=++tot;
			tire[tot][1]=tire[tot][0]=0;
		}
		p=tire[p][h];
	}
}
int query(int x,int d){
	int p=0,ans=0;
	for(int i=d;i>=0;i--){
		int h=(x>>i)&1;
		if(tire[p][h])p=tire[p][h];   ///求最小异或
		else{
			p=tire[p][h^1];
			ans+=(1<<i);
		}
	}
	return ans;
}
void resetTire(){
	tire[0][1]=tire[0][0]=0,tot=0;
}

CH1602

int trie[N][2],tot=1;
void insert(int x){
	int p=1;
	for(int i=30;i>=0;i--){
		int h=(x>>i);
		if(trie[p][h&1]==0)trie[p][h&1]=++tot;
		p=trie[p][h&1];
	}
}
int search(int x){
	int p=1,ans=0;
	for(int i=30;i>=0;i--){
		int h=(x>>i);
		if(trie[p][(h&1)^1]){    ///求最大值
			ans+=(1<<i);
			p=trie[p][(h&1)^1];
		}
		else p=trie[p][h&1];
	}
	return ans;
}
int a[100005];
int main()
{
	int n;
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	insert(a[1]);
	int ans=0;
	for(int i=2;i<=n;i++){
		ans=max(ans,search(a[i]));
		insert(a[i]);
	}
	printf("%d\n",ans);
}

POJ-3764

int trie[1000005][2],tot=1;
void insert(int x){
	int p=1;
	for(int i=30;i>=0;i--){
		int h=(x>>i);
		if(trie[p][h&1]==0)trie[p][h&1]=++tot;
		p=trie[p][h&1];
	}
}
int search(int x){
	int p=1;
	int ans=0;
	for(int i=30;i>=0;i--){
		int h=(x>>i);
		if(trie[p][(h&1)^1]){
			ans+=(1<<i);
			p=trie[p][(h&1)^1];
		}
		else p=trie[p][h&1];
	}
	return ans;
}
int head[2*N],Next[2*N],ver[2*N],edge[2*N];
void add(int x,int y,int v){
	ver[++tot]=y;
	edge[tot]=v;
	Next[tot]=head[x];
	head[x]=tot;
}
int d[N];
void dfs(int x,int fa){
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i],v=edge[i];
		if(y==fa)continue;
		d[y]=d[x]^v;
		dfs(y,x);
	}
}
int main()
{
	int n;
	while(~scanf("%d",&n)){
		tot=0;
		memset(head,0,sizeof(head));
		for(int i=1;i<n;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			add(u,v,w);
			add(v,u,w);
		}
		memset(d,0,sizeof(d));
		memset(trie,0,sizeof(trie));
		dfs(0,-1);
		int ans=0;
		tot=1;
		insert(d[0]);
		for(int i=1;i<n;i++){
			ans=max(ans,search(d[i]));
			insert(d[i]);
		}
		printf("%d\n",ans);
	}
}

可持久化Tire

/// 这是一棵未经验证的可持久化字典树，貌似是对的
int tire[N*20][30],root[N],tot=0;
void insert(string &s,int k,int p,int q){
	if(k>=(int)s.size())return;
	if(p)for(int i=1;i<=26;i++)tire[q][i]=tire[p][i];
	tire[q][s[k]-'a'+1]=++tot;
	insert(s,k+1,tire[p][s[k]-'a'+1],tire[q][s[k]-'a'+1]);
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		string s;cin>>s;root[i]=++tot;
		insert(s,0,root[i-1],root[i]);
	}
	for(int i=1;i<=30;i++){
		for(int j=1;j<=26;j++){
			cout<<tire[i][j]<<' ';
		}
		cout<<endl;
	}
}

求最大异或和

BZOJ - 3261

int tire[N*24][2],latest[N*24];
int s[N],root[N],n,m,tot=0;
void insert(int i,int k,int p,int q){
	if(k<0){latest[q]=i;return;}
	int c=s[i]>>k&1;
	if(p)tire[q][c^1]=tire[p][c^1];
	tire[q][c]=++tot;
	insert(i,k-1,tire[p][c],tire[q][c]);
	latest[q]=max(latest[tire[q][0]],latest[tire[q][1]]);
}
int ask(int now,int val,int k,int limit){
	if(k<0)return val^s[latest[now]];
	int c=(val>>k)&1;
	if(latest[tire[now][c^1]]>=limit)
		return ask(tire[now][c^1],val,k-1,limit);
	else return ask(tire[now][c],val,k-1,limit);
}
int main(){
	cin>>n>>m;latest[0]=-1;root[0]=++tot;
	insert(0,23,0,root[0]);
	for(int i=1;i<=n;i++){
		int x=read();s[i]=s[i-1]^x;root[i]=++tot;
		insert(i,23,root[i-1],root[i]);
	}
	for(int i=1;i<=m;i++){
		char c[3];scanf("%s",c);
		if(c[0]=='A'){
			int x=read();root[++n]=++tot;s[n]=s[n-1]^x;
			insert(n,23,root[n-1],root[n]);
		}
		else {
			int l=read(),r=read(),x=read();
			printf("%d\n",ask(root[r-1],s[n]^x,23,l-1));
		}
	}
}

二叉堆

///大根堆
int heap[N],tot=0;
void up(int p){
    while(p>1){
        if(heap[p]>heap[p>>1]){
            swap(heap[p],heap[p>>1]);
            p>>=1;
        }
        else break;
    }
}
void Insert(int val){
    heap[++tot]=val;
    up(tot);
}
int GetTop(){
    return heap[1];
}
void down(int p){
    int s=(p<<1);
    while(s<=tot){
        if(s+1<=tot&&heap[s]<heap[s+1])s++;
        if(heap[s]>heap[p]){
            swap(heap[s],heap[p]);
            p=s;s=(p>>1);
        }
        else break;
    }
}
void Extract(){
    heap[1]=heap[tot--];
    down(1);
}
void Remove(int k){
    heap[k]=heap[tot--];
    up(k),down(k);
}

并查集

边带权

//CH4101/NOI2002
int fa[N];
int d[N],size[N]; //d[x]为x到fa[x]的距离，size[x]为以x为根节点的树的大小，初始全为1
int get(int x){
    if(x==fa[x])return x;
    int root=get(fa[x]);
    d[x]+=d[fa[x]];
    return fa[x]=root;
}
void merge(int x,int y){
    x=get(x),y=get(y);
    fa[x]=y;
    d[x]=size[y];
    size[y]+=size[x];
}

int n,m;
struct node{
    int l,r,ans;
}query[N];
int a[N],fa[N],d[N];
void read_discrete(){
    cin>>n>>m;
    int t=0;
    for(int i=1;i<=m;i++){
        cin>>query[i].l>>query[i].r;
        string s;
        cin>>s;
        query[i].ans=((s[0]=='o')?1:0);
        a[++t]=query[i].l;
        a[++t]=query[i].r;
    }
    sort(a+1,a+t+1);
    n=unique(a+1,a+t+1)-a-1;
}
int get(int x){
    if(x==fa[x])return x;
    int root=get(fa[x]);
    d[x]^=d[fa[x]];
    return fa[x]=root;
}
int main()
{
    ios::sync_with_stdio(false);
    read_discrete();
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x=lower_bound(a+1,a+n+1,query[i].l-1)-a;
        int y=lower_bound(a+1,a+n+1,query[i].r)-a;
        int p=get(x),q=get(y);
        if(p==q){
            if((d[x]^d[y])==query[i].ans)continue;
            cout<<i-1<<endl;
            return 0;
        }
        fa[p]=q;
        d[p]=d[x]^d[y]^query[i].ans;
    }
    cout<<m<<endl;
}

扩展域

int n,m;
struct node{
    int l,r,ans;
}query[N];
int fa[N*2];
int a[N];
void read_discrete(){
    cin>>n>>m;
    int t=0;
    for(int i=1;i<=m;i++){
        cin>>query[i].l>>query[i].r;
        string s;
        cin>>s;
        query[i].ans=((s[0]=='o')?1:0);
        a[++t]=query[i].l;
        a[++t]=query[i].r;
    }
    sort(a+1,a+t+1);
    n=unique(a+1,a+t+1)-a-1;
}
int get(int x){
    if(x==fa[x])return x;
    return fa[x]=get(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    read_discrete();
    for(int i=1;i<=2*n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x=lower_bound(a+1,a+n+1,query[i].l-1)-a;
        int y=lower_bound(a+1,a+n+1,query[i].r)-a;
        int x_odd=x,x_even=x+n;
        int y_odd=y,y_even=y+n;
        if(query[i].ans==0){
            if(get(x_odd)==get(y_even)){
                cout<<i-1<<endl;
                return 0;
            }
            fa[get(x_odd)]=get(y_odd);
            fa[get(x_even)]=get(y_even);
        }
        else{
            if(get(x_even)==get(y_even)){
                cout<<i-1<<endl;
                return 0;
            }
            fa[get(x_odd)]=get(y_even);
            fa[get(x_even)]=get(y_odd);
        }
    }
    cout<<m<<endl;
}

线段树

static class SegmentTree {
	public int l[]=new int[N*4];
	public int r[]=new int[N*4];
	public long lazy[]=new long[N*4];
	public long val[]=new long[N*4];
	public long a[];
	public SegmentTree(int L,int R,long[] h){
		a=h;build(1,L,R);
	}
	public void spread(int p){
		if(lazy[p]!=0){
			val[p<<1]+=lazy[p]*(r[p<<1]-l[p<<1]+1);
			val[p<<1|1]+=lazy[p]*(r[p<<1|1]-l[p<<1|1]+1);
			lazy[p<<1]+=lazy[p];
			lazy[p<<1|1]+=lazy[p];
			lazy[p]=0;
		}
	}
	public void build(int p,int L,int R){
		l[p]=L;r[p]=R;
		if(L==R){val[p]=a[L];return;}
		int mid=(L+R)>>1;
		build(p<<1,L,mid);
		build(p<<1|1,mid+1,R);
		val[p]=val[p<<1]+val[p<<1|1];
	}
	public void change(int p,int x,long d){     	///单点修改
		if(l[p]==r[p]){val[p]=d;return;}
		int mid=(l[p]+r[p])>>1;
		if(x<=mid)change(p<<1,x,d);
		else change(p<<1|1,x,d);
		val[p]=val[p<<1]+val[p<<1|1];
	}
	public void change(int p,int L,int R,long d){    ///区间修改
		if(L<=l[p]&&R>=r[p]){
			val[p]+=d*(r[p]-l[p]+1);
			lazy[p]+=d;
			return;
		}
		spread(p);
		int mid=(l[p]+r[p])>>1;
		if(L<=mid)change(p<<1,L,R,d);
		if(R>mid)change(p<<1|1,L,R,d);
		val[p]=val[p<<1]+val[p<<1|1];
	}
	public long ask(int p,int L,int R){
		if(L<=l[p]&&R>=r[p])return val[p];
		spread(p);		///区间查询时使用
		int mid=(l[p]+r[p])>>1;
		long val=0;
		if(L<=mid)val+=ask(p<<1,L,R);
		if(R>mid)val+=ask(p<<1|1,L,R);
		return val;
	}
}

ll a[N];
struct node{
    int l,r;
    ll val,lazy;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define val(x) tree[x].val
    #define lazy(x) tree[x].lazy
};
node tree[N*4];
void up(int p){
    val(p)=val(p<<1)+val(p<<1|1);
}
void spread(int p){
    if(lazy(p)){
        val(p<<1)+=(r(p<<1)-l(p<<1)+1)*lazy(p);
        val(p<<1|1)+=(r(p<<1|1)-l(p<<1|1)+1)*lazy(p);
        lazy(p<<1)+=lazy(p);
        lazy(p<<1|1)+=lazy(p);
        lazy(p)=0;
    }
}
void build(int p,int l,int r){
    l(p)=l,r(p)=r;
    if(l==r){val(p)=a[l];return;}
    int mid=((l+r)>>1);
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    up(p);
}
ll ask(int p,int l,int r){
    if(l<=l(p)&&r(p)<=r)return val(p);
    int mid=((l(p)+r(p))>>1);
    ll ans=0;spread(p);
    if(mid>=l)ans+=ask(p<<1,l,r);
    if(mid<r)ans+=ask(p<<1|1,l,r);
    return ans;
}
void change(int p,int l,int r,ll d){
    if(l<=l(p)&&r(p)<=r){
        lazy(p)+=d;
        val(p)+=d*(r(p)-l(p)+1);
        return;
    }
    spread(p);
    int mid=((l(p)+r(p))>>1);
    if(mid>=l)change(p<<1,l,r,d);
    if(mid<r)change(p<<1|1,l,r,d);
    up(p);
}
void change(int p,int x,int d){
    if(l(p)==r(p)&&l(p)==x){val(p)=d;return;}
    int mid=((l(p)+r(p))>>1);
    if(x<=mid)change(p<<1,x,d);
    else change(p<<1|1,x,d);
    up(p);
}

求左右两边第一个大于x的数

int a[N],n;
struct node{
	int l,r;
	int val,id;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define val(x) tree[x].val
	#define id(x) tree[x].id
}tree[N*4];
void up(int p){
	if(val(p<<1)>val(p<<1|1)){
		val(p)=val(p<<1);
		id(p)=id(p<<1);
	}
	else{
		val(p)=val(p<<1|1);
		id(p)=id(p<<1|1);
	}
}
void build(int p,int l,int r){
	l(p)=l,r(p)=r;
	if(l==r){val(p)=a[l],id(p)=l;return;}
	int mid=((l+r)>>1);
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	up(p);
}
void change(int p,int x,int d){
	if(l(p)==r(p)&&l(p)==x){val(p)=d;return;}
	int mid=((l(p)+r(p))>>1);
	if(x<=mid)change(p<<1,x,d);
	else change(p<<1|1,x,d);
	up(p);
}
int quaryl(int p,int l,int r,int val){
	if(r(p)<l||l(p)>r)return 0;
	int mid=((l(p)+r(p))>>1),ans=0;
	if(l(p)>=l&&r(p)<=r){
		if(l(p)==r(p)&&val(p)>=val)return id(p);
		if(val(p<<1|1)>=val)return quaryl(p<<1|1,l,r,val);
		if(val(p<<1)>=val)return quaryl(p<<1,l,r,val);
		return 0;
	}
	ans=max(ans,quaryl(p<<1|1,l,r,val));
	if(ans!=0)return ans;
	ans=max(ans,quaryl(p<<1,l,r,val));
	return ans;
}
int quaryr(int p,int l,int r,int val){
	if(r(p)<l||l(p)>r)return n+1;
	int mid=((l(p)+r(p))>>1),ans=n+1;
	if(l(p)>=l&&r(p)<=r){
		if(l(p)==r(p)&&val(p)>=val)return id(p);
		if(val(p<<1)>=val)return quaryr(p<<1,l,r,val);
		if(val(p<<1|1)>=val)return quaryr(p<<1|1,l,r,val);
		return n+1;
	}
	ans=min(ans,quaryr(p<<1,l,r,val));
	if(ans!=n+1)return ans;
	ans=min(ans,quaryr(p<<1|1,l,r,val));
	return ans;
}

区间开根号

//hdu-4027
ll a[N];
struct node{
	int l,r;
	ll sum;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define sum(x) tree[x].sum
}tree[N*4];
void build(int p,int l,int r){
	l(p)=l,r(p)=r;
	if(l==r){
		sum(p)=a[l];
		return;
	}
	int mid=((l+r)>>1);
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	sum(p)=sum(p<<1)+sum(p<<1|1);
}
void change(int p,int l,int r){
	if(r(p)-l(p)+1==sum(p)){
		return;
	}
	if(l<=l(p)&&r>=r(p)&&l(p)==r(p)){
		sum(p)=sqrt(sum(p));
		return;
	}
	int mid=((l(p)+r(p))>>1);
	if(l<=mid)change(p<<1,l,r);
	if(r>mid)change(p<<1|1,l,r);
	sum(p)=sum(p<<1)+sum(p<<1|1);
}
ll ask(int p,int l,int r){
	if(l<=l(p)&&r>=r(p)){
		return sum(p);
	}
	ll ans=0;
	int mid=((l(p)+r(p))>>1);
	if(l<=mid)ans+=ask(p<<1,l,r);
	if(r>mid)ans+=ask(p<<1|1,l,r);
	return ans;
}
int main(){
	int n;
	int t=0;
	while(~scanf("%d",&n)){
		t++;
		for(int i=1;i<=n;i++){
			a[i]=read();
		}
		build(1,1,n);
		int m;
		printf("Case #%d:\n",t);
		scanf("%d",&m);
		while(m--){
			int e,l,r;
			scanf("%d%d%d",&e,&l,&r);
			if(r<l){
				swap(l,r);
			}
			if(e==1){
				printf("%I64d\n",ask(1,l,r));
			}
			else {
				change(1,l,r);
			}
		}
		puts("");
	}
}

动态开点线段树

Luogu P1908

struct node{
    int lc,rc,val;
    #define lc(x) tree[x].lc
    #define rc(x) tree[x].rc
    #define val(x) tree[x].val
}tree[N];
int tot=0;
void add(int &p,int l,int r,int x,int w){
    if(!p)p=++tot;
    if(l==r){
        val(p)+=w;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)add(lc(p),l,mid,x,w);
    else add(rc(p),mid+1,r,x,w);
    val(p)=val(lc(p))+val(rc(p));
}
int ask(int p,int l,int r,int x,int y){
    if(!p)return 0;
    if(l>=x&&r<=y)return val(p);
    int mid=(l+r)>>1;
    int ans=0;
    if(x<=mid)ans+=ask(lc(p),l,mid,x,y);
    if(y>mid)ans+=ask(rc(p),mid+1,r,x,y);
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int root=0;
    ll ans=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        add(root,1,1e9,x,1);
        ans+=ask(root,1,1e9,x+1,1e9);
    }
    cout<<ans<<endl;
}

树状数组

int tree[N];
inline int lowbit(int x){
    return x&(-x);
}
int sum(int x){
    int ans=0;
    for(int i=x;i>=1;i-=lowbit(i))ans=ans+tree[i];
    return ans;
}
void add(int x,int y){
    for(int i=x;i<=N;i+=lowbit(i))
        tree[i]=tree[i]+y;
}

static class Tree {
    public int tree[]=new int[N];
    public int lowbit(int x){
        return x&(-x);
    }
    public int ask(int x){
        int ans=0;
        for(int i=x;i>=1;i-=lowbit(i))
            ans+=tree[i];
        return ans;
    }
    public void add(int x,int val){
        for(int i=x;i<=N;i+=lowbit(i))
            tree[i]+=val;
    }
}

树链剖分

int head[N],Next[2*N],ver[2*N],tot=0;
void add(int x,int y){
	ver[++tot]=y;
	Next[tot]=head[x],head[x]=tot;
}
ll a[N];
struct SegmentTree{
	int l,r;
	ll val,lazy,maxx;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define val(x) tree[x].val
	#define lazy(x) tree[x].lazy
	#define maxx(x) tree[x].maxx
}tree[N*4];
void up(int p){
	val(p)=val(p<<1)+val(p<<1|1);
	maxx(p)=max(maxx(p<<1),maxx(p<<1|1));
}
void spread(int p){
	if(lazy(p)){
		val(p<<1)+=(r(p<<1)-l(p<<1)+1)*lazy(p);
		val(p<<1|1)+=(r(p<<1|1)-l(p<<1|1)+1)*lazy(p);
		lazy(p<<1)+=lazy(p);
		lazy(p<<1|1)+=lazy(p);
		lazy(p)=0;
	}
}
void build(int p,int l,int r){
	l(p)=l,r(p)=r;
	if(l==r){val(p)=maxx(p)=a[l];return;}
	int mid=((l+r)>>1);
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	up(p);
}
ll ask_sum(int p,int l,int r){
	if(l<=l(p)&&r(p)<=r)return val(p);
	int mid=((l(p)+r(p))>>1);
	ll ans=0;spread(p);
	if(mid>=l)ans+=ask_sum(p<<1,l,r);
	if(mid<r)ans+=ask_sum(p<<1|1,l,r);
	return ans;
}
ll ask_max(int p,int l,int r){
	if(l<=l(p)&&r(p)<=r)return maxx(p);
	int mid=((l(p)+r(p))>>1);
	ll ans=-inf;spread(p);
	if(mid>=l)ans=max(ans,ask_max(p<<1,l,r));
	if(mid<r)ans=max(ans,ask_max(p<<1|1,l,r));
	return ans;
}
void change(int p,int l,int r,ll d){
	if(l<=l(p)&&r(p)<=r){
		lazy(p)+=d;maxx(p)+=d;
		val(p)+=d*(r(p)-l(p)+1);
		return;
	}
	spread(p);
	int mid=((l(p)+r(p))>>1);
	if(mid>=l)change(p<<1,l,r,d);
	if(mid<r)change(p<<1|1,l,r,d);
	up(p);
}
void change(int p,int x,int d){
	if(l(p)==r(p)&&l(p)==x){val(p)=d;return;}
	int mid=((l(p)+r(p))>>1);
	if(x<=mid)change(p<<1,x,d);
	else change(p<<1|1,x,d);
	up(p);
}
int f[N],dep[N],size[N],son[N],rk[N],id[N],top[N],cnt=0;
void dfs1(int x,int fa,int deep){
	f[x]=fa,dep[x]=deep,size[x]=1;
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i];
		if(y==fa)continue;
		dfs1(y,x,deep+1);
		size[x]+=size[y];
		if(size[y]>size[son[x]])son[x]=y;
	}
}
void dfs2(int x,int t){
	top[x]=t,id[x]=++cnt,rk[cnt]=x;
	if(son[x])dfs2(son[x],t);
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i];
		if(y!=son[x]&&y!=f[x])dfs2(y,y);
	}
}
void add(int x,int y,ll d){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		change(1,id[top[x]],id[x],d);
		x=f[top[x]];
	}
	if(id[x]>id[y])swap(x,y);
	change(1,id[x],id[y],d);
}
ll quary_sum(int x,int y){
	ll ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans+=ask_sum(1,id[top[x]],id[x]);
		x=f[top[x]];
	}
	if(id[x]>id[y])swap(x,y);
	ans+=ask_sum(1,id[x],id[y]);
	return ans;
}
ll quary_max(int x,int y){
	ll ans=-inf;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=max(ans,ask_max(1,id[top[x]],id[x]));
		x=f[top[x]];
	}
	if(id[x]>id[y])swap(x,y);
	ans=max(ans,ask_max(1,id[x],id[y]));
	return ans;
}
ll b[N];
int main(){
	ios::sync_with_stdio(false);
	int n,m,r;cin>>n>>m>>r;
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n-1;i++){
		int x,y;cin>>x>>y;
		add(x,y),add(y,x);
	}
	dfs1(r,0,1);
	dfs2(r,r);
	for(int i=1;i<=n;i++){
		a[id[i]]=b[i]; ///a[i]=b[rk[i]];
	}
	build(1,1,n);
	while(m--){
		int p;cin>>p;
		if(p==1){ ///表示将树从x到y结点最短路径上所有节点的值都加上z
			int x,y,z;cin>>x>>y>>z;
			add(x,y,z);
		}
		else if(p==2){	///表示求树从x到y结点最短路径上所有节点的值之和
			int x,y;cin>>x>>y;
			cout<<quary_sum(x,y)<<endl;
		}
		else if(p==3){	///表示将以x为根节点的子树内所有节点值都加上z
			int x;ll d;cin>>x>>d;
			change(1,id[x],id[x]+size[x]-1,d);
		}
		else if(p==4){	///表示求以x为根节点的子树内所有节点值之和
			int x;cin>>x;
			cout<<ask_sum(1,id[x],id[x]+size[x]-1)<<endl;
		}
		else{	///表示求树从x到y结点最短路径上所有节点的值的最大值
			int x,y;cin>>x>>y;
			cout<<quary_max(x,y)<<endl;
		}
	}
}

分块

ll a[N],L[N],R[N],sum[N],pos[N],add[N],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;
        }
        return;
    }
    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;}
    for(int i=L[q];i<=r;i++){a[i]+=d;sum[q]+=d;}
}
ll ask(int l,int r)
{
    ll ans=0;
    int p=pos[l],q=pos[r];
    if(p==q){
        for(int i=l;i<=r;i++)
            ans+=a[i];
        ans+=add[p]*(r-l+1);
        return ans;
    }
    for(int i=p+1;i<=q-1;i++)
        ans+=sum[i]+add[i]*(R[i]-L[i]+1);
    for(int i=l;i<=R[p];i++)
        ans+=a[i]+add[p];
    for(int i=L[q];i<=r;i++)
        ans+=a[i]+add[q];
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%I64d",&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(q--){
        int l,r;
        char s[10];
        scanf("%s%d%d",s,&l,&r);
        if(s[0]=='Q'){
            cout<<ask(l,r)<<endl;
        }
        else {
            ll d;
            scanf("%I64d",&d);
            change(l,r,d);
        }
    }
}

点分治

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define ll  long long
#define ull unsigned long long
using namespace std;
const int N=2e4+5,M=10007;
const ull base=13331;
const double Pi=acos(-1.0);
const ll C=299792458;
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*10+ch-'0';ch=getchar();}
    return x*f;
}
int head[N],Next[N],ver[N],edge[N],tot=0;
void add(int x,int y,int v)
{
    ver[++tot]=y;
    edge[tot]=v;
    Next[tot]=head[x];
    head[x]=tot;
}
int v[N];
ll size[N];
int pos;
int n;
int d[N];
int b[N];
int sn;
void dfs_root(int x,int fa)
{
    d[x]=0;
    b[x]=1;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(fa==y||v[y])continue;
        dfs_root(y,x);
        b[x]=b[x]+b[y];
        d[x]=max(d[x],b[y]);
    }
    d[x]=max(d[x],sn-b[x]);
    if(d[pos]>d[x]){
        pos=x;
    }
}
int num=0;
int dis[N];
void dfs_dis(int x,int d,int fa)
{
    dis[++num]=d;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(y==fa||v[y])continue;
        dfs_dis(y,d+edge[i],x);
    }
}
int calc(int x,int d)
{
    num=0;
    dfs_dis(x,d,x);
    sort(dis+1,dis+num+1);
    int l=1,r=num;
    int cnt=0;
    while(l<r){
        while(dis[l]+dis[r]>k&&l<r)r--;
        cnt+=r-l;
        l++;
    }
    return cnt;
}
ll ans=0;
void dfs(int x)
{
    pos=0;
    dfs_root(x,0);
    v[pos]=1;
    ans+=(ll)calc(pos,0);
    for(int i=head[pos];i;i=Next[i])
    {
        int y=ver[i];
        if(v[y])continue;
        ans-=(ll)calc(y,edge[i]);
        sn=b[y];
        dfs(y);
    }
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        if(n==0&&k==0)break;
        tot=0;
        memset(v,0,sizeof(v));
        memset(head,0,sizeof(head));
        for(int i=1;i<=n-1;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
        }
        sn=n;
        ans=0;
        d[0]=0x7fffffff;
        dfs(1);
        printf("%I64d\n",ans);
    }
}

离散化

一维

struct node{
    int id;
    ll v;
    friend bool operator <(node m,node n)
    {
        return m.v<n.v;
    }
};
vector<node> t;
int main()
{
    sort(t.begin(),t.end());
    int s=1;
    a[t[0].id]=1;
    for(int i=1;i<(int)t.size();i++)
    {
        if(t[i].v!=t[i-1].v)s++;
        a[t[i].id]=s;
    }
}

void discrete(){
    sort(h+1,h+n+1);
    t=unique(h+1,h+n+1)-h;
}
int id(int x){
    return lower_bound(h+1,h+t+1,x)-h;
}

二维

struct node{
    int idx,idy;
    ll v;
    friend bool operator <(node m,node n)
    {
        return m.v<n.v;
    }
};
vector<node> t;
int main()
{
    sort(t.begin(),t.end());
    int s=1;
    a[t[0].idx][t[0].idy]=1;
    for(int i=1;i<(int)t.size();i++)
    {
        if(t[i].v!=t[i-1].v)s++;
        a[t[i].idx][t[i].idy]=s;
    }
}

杨氏矩阵

n个元素没有限制的杨氏矩阵的个数公式为

f(n)=f(n-1)+(n-1)×f(n-2)

勾长公式

POJ - 2279

int n[6];
int a1[31];
int main()
{
	ios::sync_with_stdio(false);
	int k;
	while(cin>>k&&k){
		int tot=0;
		for(int i=1;i<=k;i++){
			cin>>n[i];tot+=n[i];
		}
		for(ll i=1;i<=tot;i++){
			a1[i]=i;
		}
		ll ans=1;
		for(int i=1;i<=k;i++){
			for(int j=1;j<=n[i];j++){
				int h=(ll)n[i]-j+1;
				for(int l=i+1;l<=k;l++){
					if(n[l]>=j)h++;
				}
				for(int i=1;i<=tot;i++){
					ll g=__gcd(a1[i],h);
					a1[i]/=g,h/=g;
				}
			}
		}
		for(int i=1;i<=tot;i++)ans*=a1[i];
		cout<<ans<<endl;
	}
}

图论

最短路

dijkstra

邻接矩阵$O(N^2)$

int a[55][55],f[55],d[N],v[N],n;
int dijkstra(){
    for(int i=0;i<=n;i++){
        d[i]=inf;v[i]=f[i]=0;
    }
    d[1]=0;
    for(int i=1;i<=n;i++){
        int k=0;
        for(int j=1;j<=n;j++){		/// 求当前未遍历过的最短路径的重点
            if(v[j])continue;
            if(d[j]<d[k])k=j;
        }
        v[k]=1;
        for(int j=1;j<=n;j++){		/// 从该点开始扩展最短路
            if(v[j])continue;
            if(d[k]+a[k][j]<d[j]){
                d[j]=d[k]+a[k][j];
                f[j]=k;				/// f记录每个点在其最短路上的前一个点
            }
        }
    }
    return d[n];
}

邻接表$O(NM)$

int head[N],ver[N*2],Next[2*N],tot;
ll edge[N*2];
void add(int x,int y,ll w){
	ver[++tot]=y,edge[tot]=w;
	Next[tot]=head[x],head[x]=tot;
}
struct node{
	int x;
	ll d;
	bool friend operator<(const node &m,const node &n){
		return m.d>n.d;
	}
};
ll dis[N];
int v[N];
void dijkstra(int s){
	priority_queue<node> Q;
	memset(dis,0x3f,sizeof(dis));
	memset(v,0,sizeof(v));
	Q.push({s,0});
	dis[s]=0;
	while(!Q.empty()){
        node c=Q.top();
		int x=c.x;
		Q.pop();
		if(v[x])continue;
		v[x]=1;
		for(int i=head[x];i;i=Next[i]){
			int y=ver[i];
			ll w=edge[i];
			if(dis[y]>c.d+w){
				dis[y]=c.d+w;
				Q.push({y,dis[y]});
			}
		}
	}
}

有负边的Dijkstra

此题spfa会被t

BZOJ 2200

int fa[N];
int get(int x){
    if(x==fa[x])return x;
    return fa[x]=get(fa[x]);
}
int head[N],ver[N*5],edge[N*5],Next[N*5],tot=0;
void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z;
    Next[tot]=head[x],head[x]=tot;
}
int in[N],v[N];
vector<int> p[N],vec;
ll d[N];
struct node
{
    int x;
    ll d;
    friend bool operator<(node m,node n){
        return m.d>n.d;
    }   
};
queue<int> Q;
int vis[N];
void dijkstra(int s){
    priority_queue<node> q;
    memset(v,0,sizeof(v));
    for(int i=0;i<p[s].size();i++){
        q.push({p[s][i],d[p[s][i]]});
    }
    while(!q.empty()){
        int x=q.top().x;q.pop();
        if(v[x])continue;v[x]=1;
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i],w=edge[i];
            int x1=get(x),y1=get(y);
            if(x1==y1){
                if(d[y]>d[x]+w){
                    q.push({y,d[x]+w});
                }
            }
            else {
                in[y1]--;
                if(in[y1]==0)Q.push(y1);
            }
            if(d[y]>d[x]+w){
                d[y]=min(d[y],d[x]+w);
                if(vis[x])vis[y]=1;
            }
        }
    }
}
void topo(int s){
    memset(v,0,sizeof(v));
    memset(d,0x3f,sizeof(d));d[s]=0;vis[s]=1;
    for(int i=0;i<(int)vec.size();i++){
        if(!in[vec[i]])Q.push(vec[i]);
    }
    while(!Q.empty()){
        int x=Q.front();Q.pop();
        dijkstra(x);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m1,m2,s;
    cin>>n>>m1>>m2>>s;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m1;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z),add(y,x,z);
        int x1=get(x),y1=get(y);
        if(x1==y1)continue;
        fa[x1]=y1;
    }
    for(int i=1;i<=m2;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        in[get(y)]++;
    }
    for(int i=1;i<=n;i++){
        int x=get(i);
        if(!v[x])vec.push_back(x),v[x]=1;
        p[x].push_back(i);
    }
    memset(vis,0,sizeof(vis));
    topo(s);
    for(int i=1;i<=n;i++){
        if(!vis[i])cout<<"NO PATH"<<endl;
        else cout<<d[i]<<endl;
    }
}

floyd

传递闭包

POJ-1094

bool d[50][50];
int n,m;
bool cmp(char x,char y){
	return d[x-'A'+1][y-'A'+1];
}
bool check(){
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(!d[i][j]&&!d[j][i])return false;
		}
	}
	return true;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(cin>>n>>m&&(n+m)){
		char a,b,c;int k;
		memset(d,0,sizeof(d));
		for(int i=1;i<=n;i++)d[i][i]=1;
		for(k=1;k<=m;k++){
			cin>>a>>c>>b;
			if(c=='>')swap(a,b);
			int x=a-'A'+1,y=b-'A'+1;
			d[x][y]=1;
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					d[i][j]=d[i][j]||(d[i][x]&&d[y][j]);
			int flag=0;
			for(int i=1;i<=n;i++){
				for(int j=i+1;j<=n;j++){
					if(d[i][j]&&d[j][i]){flag=1;break;}
				}
			}
			if(flag){
				cout<<"Inconsistency found after "<<k<<" relations."<<endl;
				break;
			}
			if(check()){
				char ans[N];
				memset(ans,0,sizeof(ans));
				for(int i=1;i<=n;i++){
					ans[i]='A'+i-1;
				}
				sort(ans+1,ans+n+1,cmp);
				cout<<"Sorted sequence determined after "<<k<<" relations: ";
				cout<<(ans+1)<<'.'<<endl;
				break;
			}
		}
		if(k>m)cout<<"Sorted sequence cannot be determined."<<endl;
		for(k++;k<=m;k++)cin>>a>>c>>b;
	}
}

最小环

POJ-1734

int n,m;
int d[104][104],a[104][104],pos[104][104];
vector<int> path;
void get_path(int x,int y){
	if(pos[x][y]==0)return;
	get_path(x,pos[x][y]);
	path.push_back(pos[x][y]);
	get_path(pos[x][y],y);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	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;
		cin>>x>>y>>z;
		a[x][y]=a[y][x]=min(a[x][y],z);
	}
	memcpy(d,a,sizeof(a));
	int ans=inf;
	for(int k=1;k<=n;k++){
		for(int i=1;i<k;i++){
			for(int j=i+1;j<k;j++){
				if((ll)d[i][j]+a[j][k]+a[k][i]<ans){
					ans=d[i][j]+a[j][k]+a[k][i];
					path.clear();
					path.push_back(i);
					get_path(i,j);
					path.push_back(j);
					path.push_back(k);
				}
			}
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(d[i][j]>d[i][k]+d[k][j]){
					d[i][j]=d[i][k]+d[k][j];
					pos[i][j]=k;
				}
	}
	if(ans==inf)cout<<"No solution."<<endl;
	else {
		for(int i=0;i<path.size();i++){
			cout<<path[i]<<' ';
		}
		cout<<endl;
	}
}

恰好走n条路时最短路

POJ-3613

floyd + 矩阵快速幂

int h[1000],n,t,m,s,e,tot=0;
int u[200],v[200],c[200];
void discrete(){
    sort(h+1,h+tot+1);
    t=unique(h+1,h+tot+1)-(h+1);
}
int id(int x){
    return lower_bound(h+1,h+t+1,x)-h;
}
int d[205][205];
struct mat
{
    int a[205][205];
    void res(){
        for(int i=1;i<=t;i++)
            for(int j=1;j<=t;j++)
                a[i][j]=(i==j)?1:0;
    }
    void set(ll k){
        for(int i=1;i<=t;i++)
            for(int j=1;j<=t;j++)
                a[i][j]=k;
    }
};
mat floyd(mat y,mat x)
{
    mat ans;
    ans.set(inf);
    for(int i=1;i<=t;i++)
        for(int j=1;j<=t;j++){
            for(int k=1;k<=t;k++){
            	if(x.a[i][k]==inf||y.a[k][j]==inf)continue;
                ans.a[i][j]=min(ans.a[i][j],x.a[i][k]+y.a[k][j]);
            }
        }
    return ans;
}
mat mqpow(mat x,int y){
    mat h=x,ans;
    ans.set(inf);
    for(int i=1;i<=t;i++)ans.a[i][i]=0;
    while(y){
        if(y&1)ans=floyd(ans,h);
        h=floyd(h,h);
        y>>=1;
    }
    return ans;
};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m>>s>>e;
	for(int i=1;i<=m;i++){
		cin>>c[i]>>u[i]>>v[i];
		h[++tot]=u[i],h[++tot]=v[i];
	}
	discrete();
	for(int i=1;i<=t;i++)
		for(int j=1;j<=t;j++)
			d[i][j]=inf;
	for(int i=1;i<=m;i++){
		int x=id(u[i]),y=id(v[i]);
		d[x][y]=d[y][x]=c[i];
	}
	mat x;
	for(int i=1;i<=t;i++)
		for(int j=1;j<=t;j++)
			x.a[i][j]=d[i][j];
	mat ans=mqpow(x,n);
	cout<<ans.a[id(s)][id(e)]<<endl;
}

差分约束

int a[N],b[N],c[N];
int head[N],ver[N*2],edge[N*2],Next[N*2],tot=0;
void add(int x,int y,int w){
	ver[++tot]=y,edge[tot]=w;
	Next[tot]=head[x],head[x]=tot;
}
struct node{
	int x,d;
	friend bool operator<(node m,node n){
		return m.d<n.d;
	}
};
int v[N],dis[N];
void spfa(int p){
	memset(dis,0x3f,sizeof(dis));
	priority_queue<node> Q;
	Q.push({p,0});
	dis[p]=0;
	v[p]=1;
	while(!Q.empty()){
		int x=Q.top().x;
		Q.pop();
		v[x]=0;
		for(int i=head[x];i;i=Next[i]){
			int y=ver[i],w=edge[i];
			if(dis[y]>dis[x]+w){
				dis[y]=dis[x]+w;
				if(v[y]==0){
					Q.push({y,dis[y]});
					v[y]=1;
				}
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	int maxx=0;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>c[i];
		a[i]++,b[i]++;
		maxx=max(maxx,a[i]-1);
		maxx=max(maxx,b[i]);
	}
	for(int i=1;i<=n;i++){
		add(a[i]-1,b[i],-c[i]);
	}
	for(int i=1;i<=maxx;i++){
		add(i,i-1,1);
		add(i-1,i,0);
	}
	spfa(0);
	cout<<-dis[maxx]<<endl;
}
//最短路直接跑只能算出最大解
//本题算最小解需要对差分值取负

//0<=-(dis[i]-dis[i-1])<=1
//-1<=dis[i]-dis[i-1]<=0
//dis[i]<=dis[i-1]
//dis[i-1]<=dis[i]+1

//-(dis[b[i]]-dis[a[i]-1])>=c[i]
//dis[b[i]]-dis[a[i]-1]<=-c[i]
//dis[a[i]-1]-c[i]>=dis[b[i]]

最小生成树

kruskal

struct rec{ int x,y,z; } edge[N*5];
int fa[N],n,m;
bool operator <(rec a,rec b){
    return a.z<b.z;
}
int get(int x){
    if(x==fa[x])return x;
    return fa[x]=get(fa[x]);
}
int kruskal(){
    sort(edge+1,edge+m+1);int ans=0;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        int x=get(edge[i].x),y=get(edge[i].y);
        if(x==y)continue;
        ans+=edge[i].z;fa[x]=y;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>edge[i].x>>edge[i].y>>edge[i].z;
    cout<<kruskal()<<endl;
}

prim

不常用，多用于稠密图尤其是完全图，复杂度O(n^2)，可用堆优化到O(mlogn)，但是不如用kruskal。

int a[3010][3010],d[3010],n,m,ans=0;
bool v[3010];
void prime(){
    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])continue;
            if(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(){
    ios::sync_with_stdio(false);
    cin.tie();
    cin>>n>>m;
    memset(a,0x3f,sizeof(a));
    for(int i=1;i<=n;i++)a[i][i]=0;
    for(int i=1;i<=n;i++){
        int x,y,z;cin>>x>>y>>z;
        a[x][y]=a[y][x]=min(a[x][y],z);
    }
    prime();
    for(int i=2;i<=n;i++)ans+=d[i];
    cout<<ans<<endl;
}

Boruvka (Xor-MST)

Codeforces 888G

Tire + Boruvka

int tire[N*30][2],tot=0;
void insert(int x,int d){
	int p=0;
	for(int i=d;i>=0;i--){
		int h=(x>>i)&1;
		if(tire[p][h]==0){
			tire[p][h]=++tot;
			tire[tot][1]=tire[tot][0]=0;
		}
		p=tire[p][h];
	}
}
int query(int x,int d){
	int p=0,ans=0;
	for(int i=d;i>=0;i--){
		int h=(x>>i)&1;
		if(tire[p][h])p=tire[p][h];
		else{
			p=tire[p][h^1];
			ans+=(1<<i);
		}
	}
	return ans;
}
void resetTire(){
	tire[0][1]=tire[0][0]=0,tot=0;
}
ll cacl(vector<int> &vec,int d){
	if(!vec.size()||d==-1)return 0;
	vector<int> a[2];
	for(int i=0;i<vec.size();i++)
		a[(vec[i]>>d)&1].push_back(vec[i]);
	ll ans=cacl(a[0],d-1)+cacl(a[1],d-1);
	if(a[0].size()&&a[1].size()){
		int res=1<<d;resetTire();
		for(int i=0;i<a[0].size();i++)
			insert(a[0][i],d-1);
		for(int i=0;i<a[1].size();i++)
			res=min(res,query(a[1][i],d-1));
		ans+=res+(1<<d);
	}
	return ans;
}
vector<int> vec;
int main(){
	ios::sync_with_stdio(false);
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		vec.push_back(x);
	}
	cout<<cacl(vec,29)<<endl;
}

树的直径

dp

int head[N],Next[N],ver[N],edge[N],tot=0;
void add(int x,int y,int v)
{
    ver[++tot]=y;
    edge[tot]=v;
    Next[tot]=head[x];
    head[x]=tot;
}
int d[N];
int ans=0;
int v[N];
void dp(int x)
{
    v[x]=1;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(v[y])continue;
        v[y]=1;
        dp(y);
        ans=max(ans,d[x]+d[y]+edge[i]);
        d[x]=max(d[x],d[y]+edge[i]);
    }
}
int main()
{
    int u,v,w;
    while(scanf("%d%d%d",&u,&v,&w)!=EOF){
        add(u,v,w);
        add(v,u,w);
    }
    dp(1);
    cout<<ans<<endl;
}

两次bfs

int head[N],Next[N],ver[N],edge[N],tot=0;
void add(int x,int y,int v)
{
    ver[++tot]=y;
    edge[tot]=v;
    Next[tot]=head[x];
    head[x]=tot;
}
int v[N];
struct node{
    int d;
    int p;
};
int s;
int bfs(int pp)
{
    queue<node> Q;
    Q.push({0,pp});
    int ans=0;
    memset(v,0,sizeof(v));
    v[pp]=1;
    while(!Q.empty())
    {
        node c=Q.front();
        Q.pop();
        int x=c.p;
        for(int i=head[x];i;i=Next[i])
        {
            int y=ver[i];
            int w=edge[i];
            if(v[y])continue;
            v[y]=1;
            Q.push({c.d+w,y});
            if(c.d+w>ans){
                ans=c.d+w;
                s=y;
            }
        }
    }
    return ans;
}
int main()
{
    int u,v,w;
    while(scanf("%d%d%d",&u,&v,&w)!=EOF){
        add(u,v,w);
        add(v,u,w);
    }
    bfs(1);
    cout<<bfs(s)<<endl;
}

lca

倍增

int ver[2*N],Next[N*2],head[N],tot=0;
void add(int x,int y){
    ver[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
int f[N][20],d[N],t;
void bfs(){
    queue<int> Q;d[1]=1;Q.push(1);
    while(!Q.empty()){
        int x=Q.front();Q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(d[y])continue;
            d[y]=d[x]+1;
            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);
    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[y][i]!=f[x][i])y=f[y][i],x=f[x][i];
    return f[x][0];
}
void init(){
    memset(head,0,sizeof(head));
    memset(d,0,sizeof(d));
	//t=(int)(log(n)/log(2))+1;
}

//HDU-2586
int ver[2*N],Next[N*2],edge[N*2],head[N],tot=0;
void add(int x,int y,int v){
    ver[++tot]=y;
    edge[tot]=v;
    Next[tot]=head[x];
    head[x]=tot;
}
int f[N][20],d[N],dist[N],t;
void bfs(){
    queue<int> Q;d[1]=1;Q.push(1);dist[1]=0;
    while(!Q.empty()){
        int x=Q.front();Q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i],w=edge[i];
            if(d[y])continue;
            d[y]=d[x]+1;
            dist[y]=dist[x]+w;
            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);
    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[y][i]!=f[x][i])y=f[y][i],x=f[x][i];
    return f[x][0];
}
void init(){
    memset(head,0,sizeof(head));
    memset(d,0,sizeof(d));
}
int main()
{
	ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--){
        init();
		int n,m;tot=0;
		cin>>n>>m;
        t=(int)(log(n)/log(2))+1;
		for(int i=1;i<n;i++){
			int x,y,v;
			cin>>x>>y>>v;
			add(x,y,v),add(y,x,v);
		}
		bfs();
		while(m--){
			int x,y;
			cin>>x>>y;
			int root=lca(x,y);
			cout<<dist[x]+dist[y]-2*dist[root]<<endl;
		}
	}
}

tarjan

//HDU-2586
int fa[N];
int get(int x){
	if(x==fa[x])return x;
	return fa[x]=get(fa[x]);
}
int head[N],ver[N*2],edge[N*2],Next[N*2],tot=0;
void add(int x,int y,int z){
	ver[++tot]=y,edge[tot]=z;
	Next[tot]=head[x],head[x]=tot;
}
vector<int> q[N],q_id[N];
void add_query(int x,int y,int id){
	q[x].push_back(y),q_id[x].push_back(id);
	q[y].push_back(x),q_id[y].push_back(id);
}
int v[N],d[N],ans[N];
void tarjan(int x){
	v[x]=1;
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i],w=edge[i];
		if(v[y])continue;
		d[y]=d[x]+w;
		tarjan(y);
		fa[y]=x;
	}
	for(int i=0;i<q[x].size();i++){
		int y=q[x][i],id=q_id[x][i];
		if(v[y]!=2)continue;
		int lca=get(y);
		ans[id]=min(ans[id],d[x]+d[y]-2*d[lca]);
	}
	v[x]=2;
}
int main()
{
	//ios::sync_with_stdio(false);
	int t;cin>>t;
	while(t--){
		int n=read(),m=read();
		for(int i=1;i<=n;i++){
			head[i]=0;fa[i]=i;v[i]=0;d[i]=0;
			q[i].clear(),q_id[i].clear();
		}
		for(int i=1;i<n;i++){
			int x=read(),y=read(),v=read();
			add(x,y,v),add(y,x,v);
		}
		for(int i=1;i<=m;i++){
			int x=read(),y=read();
			add_query(x,y,i);
			ans[i]=0x3f3f3f3f;
		}
		tarjan(1);
		for(int i=1;i<=m;i++){
			printf("%d\n",ans[i]);
		}
	}
}

二分图

二分图的判定

int v[N];
bool dfs(int x,int color,int fa){
	v[x]=color;
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i],w=edge[i];
		if(y==fa)continue;
		if(v[y]==0){
			if(!dfs(y,3-color,x))return false;
			//不能加else return true; 不然会无法继续递归下一条边
		}
		else if(v[y]==color)return false;
	}
	return true;
}
int n,m;
bool check(){
	memset(v,0,sizeof(v));
	for(int i=1;i<=n;i++){
		if(v[i]==0){
			if(dfs(i,1,0))continue;
			else return false;
		}
	}
	return true;
}

CH4901 关押罪犯

int head[N],Next[N*2],ver[N*2],edge[N*2],tot=0;
void add(int x,int y,int w){
	ver[++tot]=y,edge[tot]=w;
	Next[tot]=head[x],head[x]=tot;
}
int mid;
int v[N];
bool dfs(int x,int color,int fa){
	v[x]=color;
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i],w=edge[i];
		if(y==fa)continue;
		if(w<=mid)continue;
		if(v[y]==0){
			if(!dfs(y,3-color,x))return false;
		}
		else if(v[y]==color)return false;
	}
	return true;
}
int n,m;
bool check(){
	memset(v,0,sizeof(v));
	for(int i=1;i<=n;i++){
		if(v[i]==0){
			if(dfs(i,1,0))continue;
			else return false;
		}
	}
	return true;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,w;
		cin>>x>>y>>w;
		add(x,y,w),add(y,x,w);
	}
	int l=0,r=1e9;
	while(l<r){
		mid=(r-l)/2+l;
		if(check())r=mid;
		else l=mid+1;
	}
	cout<<l<<endl;
}

二分图最大匹配

匈牙利算法（增广路算法）

int head[N],Next[N],ver[N],edge[N],tot;
void add(int x,int y,int w){
	ver[++tot]=y,edge[tot]=w;
	Next[tot]=head[x],head[x]=tot;
}
namespace MaxMatch{
    int vis[N],match[N],n;
    bool dfs(int x){
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(vis[y])continue;
            vis[y]=1;
            if(!match[y]||dfs(match[y])){
                match[y]=x;return true;
            }
        }
        return false;
    }
    int maxmatch(){
        int ans=0;
        for(int i=1;i<=n;i++){
            memset(vis,0,sizeof(vis));
            if(dfs(i))ans++;
        }
        return ans;
    }
}

一般图最大匹配(带花树算法)

int FlowerTree_n;//点数n，边数m
int head[N],ver[2*N],Next[N*2],tot=0;
int fa[N];//fa[i] 记录i点属于哪一个点为根的花
int pre[N];//pre[i] i的前驱节点
queue<int> Q;//int Q[N * N * 2], h, t;//bfs队列 头尾
int Match[N];//Match[i]标记匹配的对象
int tim;//lca时间戳
int Type[N];//Type[i]标记i点的类型 奇节点：1 偶节点：2 没有标记过时为0
int dfn[N];//每个节点的lca时间戳
void add(int x,int y){  /// 加无向边
    ver[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
    ver[++tot]=x;
    Next[tot]=head[y];
    head[y]=tot;
}
int get(int x){
    if(fa[x]==x)return x;
    return fa[x]=get(fa[x]);
}
int lca(int x,int y){
    ++tim;
    x=get(x),y=get(y);
    while(dfn[x]!=tim){
        dfn[x]=tim;
        x=get(pre[Match[x]]);
        if(y)swap(x,y);
    }
    return x;
}
void blossom(int x,int y,int p){
    while(get(x)!=p){
        pre[x]=y;
        y=Match[x];
        if(Type[y]==2){
            Type[y]=1;
            Q.push(y);
        }
        fa[x]=p,fa[y]=p;
        x=pre[y];
    }
}// 开花,奇环缩成一个点 并将原来偶点的点变为奇点 并加入队列中
bool Aug(int st){
    memset(Type,0,sizeof(Type));
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=FlowerTree_n;i++)fa[i]=i;
    while(!Q.empty())Q.pop();
    Q.push(st);Type[st]=1;
    while(!Q.empty()){
        int x=Q.front();Q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            //如果遇到了偶节点 就忽略不管
            if(get(x)==get(y)||Type[y]==2)continue;
            // 如果这个点没有被匹配过 说明找到了一条增广路
            // 因为队列里存的都是奇点 所以找到的那个没有匹配过的点肯定是偶点
            if(!Type[y]){
                Type[y]=2;pre[y]=x;
                if(!Match[y]){
                    // 找到now之前的那个节点u 将原先匹配过的u匹配现在的节点
                    // 让原来匹配的那个节点重新找别人匹配
                    for(int now=y,u;now;now=u){
                        u=Match[pre[now]];
                        Match[now]=pre[now];
                        Match[pre[now]]=now;
                    }
                    return true;
                }
                Type[Match[y]]=1;//如果有匹配 则y是偶点 将y匹配的对象放入队列中
                Q.push(Match[y]);
            }else if(Type[y]==1){
                int p=lca(x,y);
                blossom(x,y,p);
                blossom(y,x,p);// 如果找到的点是奇点 即 找到环了,就进行开花操作
            }
        }
    }
    return false;
}
void init(){
    memset(head,0,sizeof(head));
    memset(Match,0,sizeof(Match));
    memset(dfn,0,sizeof(dfn));
    tim=0;tot=0;
}
int maxMatch(){
    int res=0;
    for (int i=1;i<=FlowerTree_n;i++) {
        if(!Match[i]){
            res+=Aug(i);
        }
    }
    return res;
}

Tarjan

Tarjan求割边

牛客小白月赛12 I

int head[N],ver[N*6],Next[N*6],tot=0;
void add(int x,int y){
    ver[++tot]=y;
    Next[tot]=head[x],head[x]=tot;
}
int dfn[N],low[N],cnt=0;
int ans=0;
void tarjan(int x,int fa){
    dfn[x]=low[x]=++cnt;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        if(y==fa)continue;
        if(!dfn[y]){
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x])ans++;
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    tarjan(1,0);
    printf("%d\n",m-ans);
}

Tarjan求割点

Luogu P3388

int head[N],ver[N*6],Next[N*6],tot=0;
void add(int x,int y){
    ver[++tot]=y;
    Next[tot]=head[x],head[x]=tot;
}
int dfn[N],low[N],cnt=0;
int v[N];
void tarjan(int x,int fa){
    dfn[x]=low[x]=++cnt;
    int cnt=0;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        if(y==fa)continue;
        if(!dfn[y]){
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]&&x!=fa)v[x]=1;
            if(x==fa)cnt++;
        }
        else low[x]=min(low[x],dfn[y]);
    }
    if(fa==x&&cnt>=2)v[x]=1;
}
int main(){
    int n,m;
   	scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;i++){
    	if(!dfn[i])tarjan(i,i);
    }
    int ans=0;
    for(int i=1;i<=n;i++)if(v[i])ans++;
    printf("%d\n",ans);
    for(int i=1;i<=n;i++){
    	if(v[i])printf("%d ",i);
    }
}

网络流

最大流

Edmonds-Karp

O(nm^2)

1e2 ~ 1e3

POJ - 1273 Drainage Ditches

int head[N],ver[N*2],edge[N*2],Next[N*2],tot=1;
void add(int x,int y,int w){
    ver[++tot]=y,edge[tot]=w;
    Next[tot]=head[x],head[x]=tot;
}
/*void add(int x,int y,int w){
	ver[++tot]=y,edge[tot]=w;
	Next[tot]=head[x],head[x]=tot;
	ver[++tot]=x,edge[tot]=0;
	Next[tot]=head[y],head[y]=tot;
}*/
int n,m,maxflow,v[N],incf[N],pre[N];
bool bfs(int s,int t){
	memset(v,0,sizeof(v));
	queue<int> Q;
	Q.push(s),v[s]=1;
	incf[s]=inf;
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		//cout<<x<<endl;
		for(int i=head[x];i;i=Next[i]){
			int y=ver[i];
			if(!edge[i]||v[y])continue;
			incf[y]=min(incf[x],edge[i]);
			pre[y]=i,v[y]=1,Q.push(y);
			if(y==t)return true;
		}
	}
	return false;
}
void update(int s,int t){
	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 Edmonds(int s,int t){
	memset(incf,0,sizeof(incf));
	while(bfs(s,t))update(s,t);
	return maxflow;
}
void resetMaxflow(){
    memset(head,0,sizeof(head));
    tot=1,maxflow=0;
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>m>>n){
        resetMaxflow();
        for(int i=1;i<=m;i++){
            int x,y,z;
            cin>>x>>y>>z;
            add(x,y,z),add(y,x,0);
        }
        cout<<Edmonds(1,n)<<endl;
    }
}

Dinic

O(nm^2)

1e3 ~ 1e4

P3376 【模板】网络最大流

int head[N],ver[N*2],edge[N*2],Next[N*2],tot=1;
void add(int x,int y,int w){
    ver[++tot]=y,edge[tot]=w;
    Next[tot]=head[x],head[x]=tot;
}
int n,m,s,t,maxflow,d[N];
bool bfs(){
    queue<int> Q;
    memset(d,0,sizeof(d));
    Q.push(s),d[s]=1;
    while(!Q.empty()){
        int x=Q.front();Q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(!edge[i]||d[y])continue;
            Q.push(y),d[y]=d[x]+1;
            if(y==t)return true;
        }
    }
    return false;
}
int dinic(int x,int flow){
    if(x==t)return flow;
    int rest=flow,k;
    for(int i=head[x];i&&rest;i=Next[i]){
        int y=ver[i];
        if(!edge[i]||d[y]!=d[x]+1)continue;
        k=dinic(y,min(rest,edge[i]));
        if(!k)d[y]=0;
        edge[i]-=k,edge[i^1]+=k;
        rest-=k;
    }
    return flow-rest;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z),add(y,x,0);
    }
    int flow=0;
    while(bfs())
        while(flow=dinic(s,inf))
            maxflow+=flow;
    cout<<maxflow<<endl;
}

计算几何

空间中求一点到所有点的距离最短

int n;
struct Point{double p[5];}a[N];
double dis(Point A,Point B){
	return sqrt((A.p[1]-B.p[1])*(A.p[1]-B.p[1])+(A.p[2]-B.p[2])*(A.p[2]-B.p[2])+(A.p[3]-B.p[3])*(A.p[3]-B.p[3]));
}
double cacl(Point A){
	double ans=0.0;
	for(int i=1;i<=n;i++){
		ans=max(ans,dis(A,a[i]));
	}
	return ans;
}
Point solve(Point now,int cnt){
	if(cnt>3)return now;
	double l=-100000,r=100000;
	Point ans,A,B;
	A=B=ans=now;
	while(r-l>0.0001){
		double mid1=(l+r)/2;
		double mid2=(mid1+r)/2;
		A.p[cnt]=mid1;
		Point ans1=solve(A,cnt+1);
		B.p[cnt]=mid2;
		Point ans2=solve(B,cnt+1);
		if(cacl(ans1)>cacl(ans2))l=mid1,ans=ans1;
		else r=mid2,ans=ans2;
	}
	return ans;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    	scanf("%lf%lf%lf",&a[i].p[1],&a[i].p[2],&a[i].p[3]);
    }
    Point ans=solve(ans,1);
   	printf("%.15lf\n", cacl(ans));
}

杂项

线性筛

ll phi[N+10];
bool vis[N+10];
ll prime[N+10];
ll miu[N+10];
ll tot;
void init(){
    miu[1]=1;
    tot = 0;
    for(ll i = 2; i <=N; i ++)
    {
        if(!vis[i])
        {
            prime[tot ++] = i;
            phi[i] = i - 1;
            miu[i]=-1;
        }
        for(ll j = 0; j < tot; j ++)
        {
            if(i * prime[j] >= N) break;
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0)
            {
                miu[i*prime[j]]=0;
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else
            {
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
                miu[i*prime[j]]=-1*miu[i];
            }
        }
    }
}

矩阵快速幂

struct mat
{
    ll a[105][105];
    int n,m;
    void res(){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                a[i][j]=(i==j)?1:0;
    }
    void set(ll k){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                a[i][j]=k;
    }
};
mat mul(mat x,mat y)    //矩阵A*B=mul(A,B)，矩阵B*A=mul(B,A)
{
    mat ans;
    ans.n=x.n,ans.m=y.m;
    ans.set(0);
    for(int i=1;i<=ans.n;i++)
        for(int j=1;j<=ans.m;j++)
            for(int k=1;k<=x.m;k++)
            {
                ans.a[i][j]+=x.a[i][k]*y.a[k][j]%M;
                ans.a[i][j]%=M;
            }
    return ans;
}
mat mqpow(mat x,ll y){
    mat h=x,ans=x;
    ans.res();
    /*for(int i=1;i<=ans.n;i++)
    {
        ans.a[11-i][1]=i-1;
    }*/                       ////可以规定第一列的元素，否则ans就直接等于x
    while(y){
        if(y&1)ans=mul(ans,h);
        h=mul(h,h);
        y>>=1;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    ll n,m;
    cin>>n>>m;
    if(n<m){
        cout<<1<<endl;
        return 0;
    }
    mat c;
    c.m=m,c.n=m;
    c.a[1][1]=1;c.a[1][m]=1;
    for(int i=1;i<m;i++)
    {
        c.a[i+1][i]=1;
    }
    mat ans=mqpow(c,n);
    cout<<ans.a[1][1]%M<<endl;
}

struct mat{
    int a[5][5];
    void res(){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                a[i][j]=(i==j)?1:0;
    }
    void set(ll k){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                a[i][j]=k;
    }
};
mat mul(mat x,mat y){
    mat ans;
    ans.set(0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++){
                ans.a[i][j]+=x.a[i][k]*y.a[k][j]%M;
                ans.a[i][j]%=M;
            }
    return ans;
}
mat mqpow(mat x,int y){
    mat h=x,ans;
    ans.set(0);
    ans.a[4][1]=2;
    ans.a[3][1]=4;
    ans.a[2][1]=6;
    ans.a[1][1]=9;
    while(y){
        if(y&1)ans=mul(ans,h);
        h=mul(h,h);
        y>>=1;
    }
    return ans;
}
int main(){
    //ios::sync_with_stdio(false);
    int L;
    mat p;
    n=4;
    p.set(0);
    p.a[1][1]=p.a[1][3]=p.a[1][4]=1;
    p.a[2][1]=p.a[3][2]=p.a[4][3]=1;
    while(~scanf("%d%d",&L,&M)){
        if(L<=4){
            if(L==0)printf("0\n");
            if(L==1)printf("%d\n",2%M);
            if(L==2)printf("%d\n",4%M);
            if(L==3)printf("%d\n",6%M);
            if(L==4)printf("%d\n",9%M);
        }
        else{
            mat ans=mqpow(p,L-4);
            printf("%d\n",ans.a[1][1]%M);
        }
    }
}

扩栈

int size = 256 << 20; // 256MB
char *p = (char*)malloc(size) + size;
__asm__("movl %0, %%esp\n" :: "r"(p));

高精度

package ustc.lichunchun.bigdataapi;
 
import java.math.BigInteger;
 
public class BigIntegerDemo1 {
 
	public static void main(String[] args) {
		BigInteger bi1 = new BigInteger("123456789") ;	// 声明BigInteger对象
		BigInteger bi2 = new BigInteger("987654321") ;	// 声明BigInteger对象
		System.out.println("加法操作：" + bi2.add(bi1)) ;	// 加法操作
		System.out.println("减法操作：" + bi2.subtract(bi1)) ;	// 减法操作
		System.out.println("乘法操作：" + bi2.multiply(bi1)) ;	// 乘法操作
		System.out.println("除法操作：" + bi2.divide(bi1)) ;	// 除法操作
		System.out.println("最大数：" + bi2.max(bi1)) ;	 // 求出最大数
		System.out.println("最小数：" + bi2.min(bi1)) ;	 // 求出最小数
		BigInteger result[] = bi2.divideAndRemainder(bi1) ;	// 求出余数的除法操作
		System.out.println("商是：" + result[0] + 
			"；余数是：" + result[1]) ;
	}
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;/*精度位数,自行调整*/
//1.如果需要控制输出位数的话，在str()里面把len调成需要的位数
//2.很大的位数是会re的，所以如果是幂运算的话，如 计算x^p的位数n, n=p*log(10)x+1;(注意要加一）
//3.还可以加上qmul，取模的过程也就是str()，c_str()再搞一次
class bign
{
    //io*2 bign*5*2 bool*6
    friend istream& operator>>(istream&,bign&);
    friend ostream& operator<<(ostream&,const bign&);
    friend bign operator+(const bign&,const bign&);
    friend bign operator+(const bign&,int&);
    friend bign operator*(const bign&,const bign&);
    friend bign operator*(const bign&,int&);
    friend bign operator-(const bign&,const bign&);
    friend bign operator-(const bign&,int&);
    friend bign operator/(const bign&,const bign&);
    friend bign operator/(const bign&,int&);
    friend bign operator%(const bign&,const bign&);
    friend bign operator%(const bign&,int&);
    friend bool operator<(const bign&,const bign&);
    friend bool operator>(const bign&,const bign&);
    friend bool operator<=(const bign&,const bign&);
    friend bool operator>=(const bign&,const bign&);
    friend bool operator==(const bign&,const bign&);
    friend bool operator!=(const bign&,const bign&);

private://如果想访问len,改成public
    int len,s[maxn];
public:
    bign()
    {
        memset(s,0,sizeof(s));
        len=1;
    }
    bign operator=(const char* num)
    {
        int i=0,ol;
        ol=len=strlen(num);
        while(num[i++]=='0'&&len>1)
            len--;
        memset(s,0,sizeof(s));
        for(i=0; i<len; i++)
            s[i]=num[ol-i-1]-'0';
        return *this;
    }
    bign operator=(int num)
    {
        char s[maxn];
        sprintf(s,"%d",num);
        *this=s;
        return *this;
    }
    bign(int num)
    {
        *this=num;
    }
    bign(const char* num)
    {
        *this=num;
    }
    string str() const
    {
        string res="";
        for(int i=0; i<len; i++)
            res=char(s[i]+'0')+res;
        if(res=="")
            res="0";
        return res;
    }
};
bool operator<(const bign& a,const bign& b)
{
    int i;
    if(a.len!=b.len)
        return a.len<b.len;
    for(i=a.len-1; i>=0; i--)
        if(a.s[i]!=b.s[i])
            return a.s[i]<b.s[i];
    return false;
}
bool operator>(const bign& a,const bign& b)
{
    return b<a;
}
bool operator<=(const bign& a,const bign& b)
{
    return !(a>b);
}
bool operator>=(const bign& a,const bign& b)
{
    return !(a<b);
}
bool operator!=(const bign& a,const bign& b)
{
    return a<b||a>b;
}
bool operator==(const bign& a,const bign& b)
{
    return !(a<b||a>b);
}
bign operator+(const bign& a,const bign& b)
{
    int up=max(a.len,b.len);
    bign sum;
    sum.len=0;
    for(int i=0,t=0;t||i<up; i++)
    {
        if(i<a.len)
            t+=a.s[i];
        if(i<b.len)
            t+=b.s[i];
        sum.s[sum.len++]=t%10;
        t/=10;
    }
    return sum;
}
bign operator+(const bign& a,int& b)
{
    bign c=b;
    return a+c;
}
bign operator*(const bign& a,const bign& b)
{
    bign res;
    for(int i=0; i<a.len; i++)
    {
        for(int j=0; j<b.len; j++)
        {
            res.s[i+j]+=(a.s[i]*b.s[j]);
            res.s[i+j+1]+=res.s[i+j]/10;
            res.s[i+j]%=10;
        }
    }
    res.len=a.len+b.len;
    while(res.s[res.len-1]==0&&res.len>1)
        res.len--;
    if(res.s[res.len])
        res.len++;
    return res;
}
bign operator*(const bign& a,int& b)
{
    bign c=b;
    return a*c;
}
//只支持大数减小数
bign operator-(const bign& a,const bign& b)
{
    bign res;
    int len=a.len;
    for(int i=0; i<len; i++)
    {
        res.s[i]+=a.s[i]-b.s[i];
        if(res.s[i]<0)
        {
            res.s[i]+=10;
            res.s[i+1]--;
        }
    }
    while(res.s[len-1]==0&&len>1)
        len--;
    res.len=len;
    return res;
}
bign operator-(const bign& a,int& b)
{
    bign c=b;
    return a-c;
}
bign operator/(const bign& a,const bign& b)
{
    int i,len=a.len;
    bign res,f;
    for(i=len-1; i>=0; i--)
    {
        f=f*10;
        f.s[0]=a.s[i];
        while(f>=b)
        {
            f=f-b;
            res.s[i]++;
        }
    }
    while(res.s[len-1]==0&&len>1)
        len--;
    res.len=len;
    return res;
}
bign operator/(const bign& a,int& b)
{
    bign c=b;
    return a/c;
}
bign operator%(const bign& a,const bign& b)
{
    int len=a.len;
    bign f;
    for(int i=len-1; i>=0; i--)
    {
        f=f*10;
        f.s[0]=a.s[i];
        while(f>=b)
            f=f-b;
    }
    return f;
}
bign operator%(const bign& a,int& b)
{
    bign c=b;
    return a%c;
}
bign& operator+=(bign& a,const bign& b)
{
    a=a+b;
    return a;
}
bign& operator-=(bign& a,const bign& b)
{
    a=a-b;
    return a;
}
bign& operator*=(bign& a,const bign& b)
{
    a=a*b;
    return a;
}
bign& operator/=(bign& a,const bign& b)
{
    a=a/b;
    return a;
}
bign& operator++(bign& a)
{
    a=a+1;
    return a;
}
bign& operator++(bign& a,int)
{
    bign t=a;
    a=a+1;
    return t;
}
bign& operator--(bign& a)
{
    a=a-1;
    return a;
}
bign& operator--(bign& a,int)
{
    bign t=a;
    a=a-1;
    return t;
}
istream& operator>>(istream &in,bign& x)
{
    string s;
    in>>s;
    x=s.c_str();
    return in;
}
ostream& operator<<(ostream &out,const bign& x)
{
    out<<x.str();
    return out;
}
int main()
{
    bign a;
    bign b;
    cin >> a>>b;
    cout << a*b;
    return 0;
}