NOIP代码

OI&ACM, 模板
  1. 1 读入优化
  2. 2 快速幂
  3. 3 筛法 O(n)
  4. 4 ged&&exgcd O(logn)
  5. 5 kmp O(n)
  6. 6 背包问题
  7. 7 离散化
  8. 8 并查集
  9. 9 最短路
  10. 10 最小生成树
  11. 11 线段树 O(nlogn)
  12. 12 树状数组 O(nlogn)
  13. 13 tarjan O(n+m)
  14. 14 Lca
  15. 15 矩阵乘法
  16. 16 匈牙利算法
  17. 17 Dinic

1 读入优化

1
2
3
4
5
6
7
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;
}

2 快速幂

1
2
3
4
5
6
7
int power(int a,int b,int P)
{
	int re=1;
	for(;b;b>>=1,a=(long long)a*a%P)
		if(b&1) re=(long long)re*a%P;
	return re;
}

3 筛法 O(n)

  • prime 素数
  • phi φ 不大于x且与x互质的数的个数
  • d x的正约数的个数
  • e x的最小质因数的个数 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    const int N = 100 + 1;
    int prime[N], e[N], d[N], tot, phi[N];
    bool not_p[N];
    inline void pre()
    {
    	not_p[1] = 1;
    	d[1] = 1;
    	for(int i = 2; i < N; ++i)
    	{
    		if(!not_p[i]) {
    			prime[++tot] = i;
    			e[i] = 1; d[i] = 2; phi[i] = i - 1;
    		}
    		for(int j = 1; j <= tot; ++j)
    		{
    			int k = prime[j] * i;
    			if(k > N) break;
    			not_p[k] = 1;
    			if(i % prime[j]) {
    				d[k] = d[i] * d[prime[j]];
    				e[k] = 1;
    				phi[k] = phi[i] * phi[prime[j]];
    			}
    			else{
    				d[k] = d[i] / (e[i] + 1) * (e[i] + 2);
    				e[k] = e[i] + 1;
    				phi[k] = phi[i] * prime[j];
    				break;
    			}
    		}
    	}
    }
    //单独求欧拉函数 
    LL Phi(LL x)
    {
    	LL i,re=x;
    	for(i=2;i*i<=x;i++)
    	  if(x%i==0)
    		{
    			re/=i;
    			re*=i-1;
    			while(x%i==0)
    				x/=i;
    		}
    	if(x!=1)
    		re/=x,re*=(x-1);
    	return re;
    }

4 ged&&exgcd O(logn)

函数求出ax+by=gcd(a,b)的其中一组解
ax+by=c的解就是x×c/d,y×c/d（当然如果c%d!=0的话，无整数解）
∴p×a+q×b=c的其他整数解满足：
xx = x+b/d×t
yy = y-a/d×t (t∈Z)

  • gcd
1
2
3
4
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
  • exgcd 
    1
    2
    3
    4
    5
    int exgcd(int a,int b,int &d,int &x,int &y)
    {
        if(!b) { d=a; x=1; y=0; }
        else { exgcd(b,a%b,d,y,x); y-=x*(a/b); }
    }

5 kmp O(n)

M 短串，长度为m
T 长串，长度为n 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int KMP()
{
    for(int i=0,j=0;i<n;i++,j++)
	{
        while(j!=-1&&W[j]!=T[i]) j=next[j];
        if(j==m-1) return i-m+2;
    }
}
void getNext()
{
	next[0]=-1;
    for(int i=1;i<m;i++)
	  for(int j=next[i];j>=0;j=next[j])
        if(W[j]==W[i])
		{
            next[i+1]=j+1;break;
        }
}

6 背包问题

  • 01背包 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for(int i=1;i<=n;i++)
      for(int v=0;v<=m;v++)
      {
      	if(v-w[i]>=0) f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
      	else f[i][v]=f[i-1][v];
      }
      
    for(int i=1;i<=n;i++)
      for(int v=m;v>=w[i];v--)
        f[v]=max(f[v],f[v-w[i]]+c[i]);

  • 完全背包 优化：拆成w[i]*2^k , c[i]*2^k 的若干件（其中w[i]*2^k<V） 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for(int i=1;i<=n;i++)
      for(int v=0;v<=m;v++)
      {
      	if(v-w[i]>=0) f[i][v]=max(f[i-1][v],f[i][v-w[i]]+c[i]);
      	else f[i][v]=f[i-1][v];
      } 
      
    for(int i=1;i<=n;i++)
      for(int v=w[i];v<=m;v++)
        f[v]=max(f[v],f[v-w[i]]+c[i]);

  • 多重背包
    优化：拆成1,2,4,..., 2^(k-1) , n[i]-2^k+1 （其中k为满足n[i]-x^k+1>0的最大整数) 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    for(int i=1;i<=n;i++)
      for(int v=0;v<=m;v++)
        for(int k=0;k<=num[i];k++)
        {
        	f[i][v]=max(f[i][v],f[i-1][v]);
      	    if(v-k*w[i]>=0) f[i][v]=max(f[i][v],f[i-1][v-k*w[i]]+k*c[i]);
        }
        
    for(int i=1;i<=n;i++)
      for(int v=m;v>=0;v--)
        for(int k=0;k<=num[i];k++)
    	{
    		if(v-k*w[i]<0) break;
    		f[v]=max(f[v],f[v-k*w[i]]+k*c[i]);
    	}

7 离散化

1
2
3
4
5
6
7
8
int main()
{
    map<int,int>m;
    for(int i=1;i<=n;i++) scanf("%d",b[i]);
    sort(b+1,b+n+1);
	b[0]=unique(b+1,b+n+1)-(b+1);
	for(int j=1;j<=b[0];j++)  m[b[j]]=j;
}

8 并查集

1
2
3
4
5
6
7
8
int father(int x)
{
    return fa[x]==x?x:fa[x]=father(fa[x]);
}
int unionn(int x,int y)
{
	fa[father(x)]=father(y);
}

9 最短路

  • SPFA O(kE) 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    memset(ds,0x7f,sizeof(ds));
    ds[S]=0; vis[S]=1; q.push(S);
    while(!q.empty())
    {
    	int x=q.front(); q.pop(); vis[x]=0;
    	for(int i=0;i<to[x].size();i++)
    	{
    		int y=to[x][i],c=cost[x][i];
    		if(ds[y]>ds[x]+c)
    		{
    			ds[y]=ds[x]+c;
    			if(!vis[y])
    			{
    				vis[y]=1; q.push(y);
    			}
    		}
    	}
    }

  • Dijkstra O(n*logn) 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    #include<cstring>
    #include<cstdio>
    #include<queue>
    using namespace std;
    const int N=10005;
    const int M=100005;
    const int inf=0x7fffffff;
    int st[N],next[2*M],ed[2*M],cost[2*M],tot,ds[N],n,m;
    inline void add(int x,int y,int z)
    {
    	next[++tot]=st[x],st[x]=tot,ed[tot]=y,cost[tot]=z;
    }
    struct node{
    	int x,d;
    	inline node(int a,int b):x(a),d(b){}
    	inline bool operator<(const node&t) const{return d>t.d;}
    };
    priority_queue<node> q;
    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); add(y,x,z);
    	}
    	int S=1,T=n;
    	for(int i=1;i<=n;i++) ds[i]=inf;
    	q.push(node(S,0));
    	while(!q.empty()){
    		node x=q.top(); q.pop();
    		if(ds[x.x]<inf) continue;
    		ds[x.x]=x.d;
    		for(int now=st[x.x];now;now=next[now]) 
    			q.push(node(ed[now],x.d+cost[now]));
    	}
    	printf("%d\n",ds[T]);
    }

10 最小生成树

  • Kruskal O(E*logE)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,x,y,z,f1,f2,tot,k,fa[1001];
struct node{
	int x,y,v;
}a[10001];
int cmp(const node &a,const node &b)
{
	return a.v<b.v;
}
int father(int x)
{
	return fa[x]==x?x:fa[x]=father(fa[x]);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		x=a[i].x;y=a[i].y;z=a[i].v;
		f1=father(x);f2=father(y);
		if(f1==f2) continue;
		fa[f1]=f2;tot+=z;k++;
		if(k==n-1) break;
	}
	printf("%d",tot);
}
  • Prim
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n,m,x,y,z,tot,ans,k,ds[1001],next[2001],st[1001],to[2001],cost[2001];
bool vis[1001];
void addedge(int x,int y,int z)
{
	next[++tot]=st[x];st[x]=tot;to[tot]=y;cost[tot]=z;
}
struct node
{
	int x,d;
	node(int a,int b):x(a),d(b) {}
	bool operator<(const node&t) const {return d>t.d;}
}; priority_queue<node>q;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
	    addedge(x,y,z);addedge(y,x,z); 
	}
	memset(ds,0x7f,sizeof(ds));
	ds[1]=0;q.push(node(1,0));vis[0]=1;
	for(int i=1;i<=n;i++)
	{
		node a(0,0);
		while(vis[a.x]&&!q.empty())
          a=q.top(),q.pop();
		if(vis[a.x]) break;
		ans+=a.d;vis[a.x]=1;k++;
		for(int j=st[a.x];j;j=next[j])
		{
			y=to[j];z=cost[j];
			if(!vis[y]&&z<ds[y])
		      ds[y]=z,q.push(node(y,z));
		}  
	}
	if(k!=n) printf("-1");
	else printf("%d",ans);
}

11 线段树 O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=100;
struct node
{
   int lc,rc,l,r,sum;
}t[2*N];	
int root,tot;
int a[N];
void build(int x,int l,int r)
{
	t[x].l=l; t[x].r=r;
	if(l==r)
	{
		t[x].sum=a[l];
		return;
	}
	int mid=(l+r)/2;
	t[x].lc=++tot;	build(t[x].lc,l,mid);
	t[x].rc=++tot;	build(t[x].rc,mid+1,r);
	t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum;
}
int query(int x,int l,int r)
{
	if(l<=t[x].l&&t[x].r<=r) return t[x].sum;
	int mid=(t[x].l+t[x].r)/2;
	int ans=0;
	if(l<=mid) ans+=query(t[x].lc,l,r);
	if(mid<r)  ans+=query(t[x].rc,l,r);
	return ans;
}
void change(int x,int v,int d)
{
	if(t[x].l==t[x].r)
	{
		t[x].sum=d;
		return;
	}
	int mid=(t[x].l+t[x].r)/2;
	if(v<=mid) change(t[x].lc,v,d);
	if(mid<v)  change(t[x].rc,v,d);
	t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum;
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	root=++tot;
	build(root,1,n);
	for(int i=1,k,x,y;i<=m;i++)
	{
		scanf("%d%d%d",&k,&x,&y);
		if(k==1) printf("%d\n",query(root,x,y));
		if(k==2) change(root,x,y); 
	} 
}

12 树状数组 O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
using namespace std;
int a[10001],c[10001];
int n;
int lowbit(int x)
{
	return x&(-x);
}
void build()
{
	for(int i=1;i<=n;i++)
	{
		c[i]=a[i];
		for(int j=i-1;j>i-lowbit(i);j-=lowbit(j))
		  c[i]+=c[j];
	}
}
int sum(int x)                    //求x之前的和 
{
	int sum=0;
	for(;x;x-=lowbit(x))  sum+=c[x];
	return sum;
}
void change(int x,int y)          //把a[x]加y 
{
	for(;x<=n;x+=lowbit(x))	c[x]+=y;
}

13 tarjan O(n+m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void Tarjan(int i)
{
    int j;
    dfn[i]=low[i]=++tot;
    vis[i]=1;
    stack[++top]=i;
    for(int e=0;e<to[i].size();e++)
    {
        j=to[i][e];
        if(!dfn[j])
        {
            Tarjan(j);
            if(low[j]<low[i]) low[i]=low[j];
        }
        else if(vis[j]&&dfn[j]<low[i]) low[i]=dfn[j];   
    }
    if(dfn[i]==low[i])
    {
        do
        {
            j=stack[top--];
            fa[j]=fa[i];
            vis[j]=0;
        }while(j!=i);
    }
}

14 Lca

注意dep[1]=1; 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for(int i=1;i<=log(n)/log(2)+1;i++)
  for(int j=1;j<=n;j++)
    fa[j][i]=fa[fa[j][i-1]][i-1],
    //g[j][i]=max(g[j][i-1],g[fa[j][i-1]][i-1]);
int lca(int x,int y)
{
    //int ans=0;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=log(n)/log(2);i>=0;i--)
      if(dep[fa[x][i]]>=dep[y]) 
        //ans=max(ans,g[x][i]),
        x=fa[x][i];
    if(x==y) return x;
    for(int i=log(n)/log(2);i>=0;i--)
      if(fa[x][i]!=fa[y][i])
        //ans=max(ans,g[x][i]),ans=max(ans,g[y][i]),
        x=fa[x][i],y=fa[y][i];
    //ans=max(ans,g[x][0]);ans=max(ans,g[y][0]);
    return fa[x][0];
}

15 矩阵乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
long long multi(long long y,long long cnt) //快速乘 
{
    if (!cnt) return 0;
    if (cnt==1) return y%m;
    long long rec=multi(y,cnt/2);
    rec=(rec+rec)%m;
    if(cnt%2) rec=(rec+y)%m;
    return rec;
}
void cheng(int x)
{
	X[1][1]=0;X[1][2]=0;X[2][1]=0;X[2][2]=0;
	if(x==0)
	{
		for(int i=1;i<=2;i++)
		  for(int j=1;j<=2;j++)
		    for(int k=1;k<=2;k++)
		    X[i][j]=(X[i][j]+multi(A[i][k],N[k][j]))%m;
		swap(X,N);
	}
	else
	{
		for(int i=1;i<=2;i++)
		  for(int j=1;j<=2;j++)
		    for(int k=1;k<=2;k++)
		    X[i][j]=(X[i][j]+multi(N[i][k],N[k][j]))%m;
		swap(X,N);
	}
}
void mi(long long n)
{
	if(n==1) return;
	mi(n/2);
	cheng(1);//N*N
	if(n%2) cheng(0);//N*A
}

16 匈牙利算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int used[N];   //记录y中节点是否使用 0表示没有访问过，1为访问过
int linker[N];   //记录当前与y节点相连的x的节点  
int g[N][N];   //记录连接x和y的边，如果i和j之间有边则为1，否则为0
int vn,vm;     //二分图中x和y中点的数目  
bool dfs(int u)//从左边开始找增广路径
{
    for(int v=0;v<vN;v++)//这个顶点编号从0开始，若要从1开始需要修改
      if(g[u][v]&&!used[v])
      {
          used[v]=true;
          if(linker[v]==-1||dfs(linker[v]))
          {//找增广路，反向
              linker[v]=u;
              return true;
          }
      }
    return false;//这个不要忘了，经常忘记这句
}
int hungary()
{
    int res=0;
    int u;
    memset(linker,-1,sizeof(linker));
    for(u=0;u<uN;u++)
    {
        memset(used,0,sizeof(used));
        if(dfs(u)) res++;
    }
    return res;
}

17 Dinic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
#define LINK(x)	for(int e=head[x];e;e=E[e].next)
using namespace std;
const int N=5000;
const int M=10000;
const int inf=1e9;
struct Edge{int to,rest,next;}E[M];
queue<int> Q;
int head[N],ds[N];
int n,m,S,T,ecnt=1;
inline void AddEdge(int x,int y,int r)
{
	++ecnt;E[ecnt].to=y,E[ecnt].rest=r,E[ecnt].next=head[x];head[x]=ecnt;
	++ecnt;E[ecnt].to=x,E[ecnt].rest=0,E[ecnt].next=head[y];head[y]=ecnt;
}
inline bool BFS()
{
	//static queue<int> Q;  //static 全局变量 
	for(int i=S;i<=T;i++)  ds[i]=-1;
	Q.push(S);ds[S]=0;
	while(!Q.empty())
	{
		int x=Q.front(); Q.pop();
		LINK(x)	if(E[e].rest && ds[E[e].to]==-1)
		  ds[E[e].to]=ds[x]+1,Q.push(E[e].to);
	}
	return ds[T]>-1;
}
inline int DFS(int x,int flow)
{
	if(x==T)  return flow;
	int a=0,b;
	LINK(x)	if(E[e].rest&&ds[E[e].to]==ds[x]+1)
	{
		b=DFS(E[e].to, min(flow-a,E[e].rest));
		E[e].rest-=b, E[e^1].rest+=b;
		a+=b;
		if(a==flow)	return flow;
	}
	if(a==0)  ds[x]=-1;
	return a;
}
inline int dinic()
{
	int ans=0;
	while(BFS())  ans+=DFS(S,inf);
	return ans;
}
int main()
{
	scanf("%d%d%d",&m,&S,&T);
	for(int i=1;i<=m;i++)
	{
		int u,v,c;
		scanf("%d%d%d",&u,&v,&c);
		AddEdge(u,v,c);
	}
	printf("%d\n",dinic());
	return 0;
}