NOIP代码

  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

NOIP之前背代码

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;
}