距离NOIP还有25天
可以去放弃一些巨难得题目去搞一些模板了
-------在校老师的原话
一·快排
虽然可以手打，最好用STL，里面有很多优化，会快很多
1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 struct node
5 {
6 int x,y;
7 }a[maxn];
8 bool cmp(node a,node b)
9 {
10 return a.x<b.x;
11 }
12 int main()
13 {
14 sort(a+1,a+1+n,cmp);
15 return 0;
16 }
View Code
二·冰茶姬
一个很好用，很好压行的神奇初级（虽然难题是真的不会）黑科技。
1 int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
View Code
三·快速幂||取模运算（就是快速幂里要取模）
1 int KSM(int a,int b,int c)
2 {
3 int ans=1;a%=c;
4 while(b>0)
5 {
6 if(b%2==1)ans=ans*a%c;
7 b/=2;a=a*a%c;
8 }
9 return ans;
10 }
View Code
四·线性筛素数
这题有很多方法，比如瞎搞，因为大于10的素数一定都在6的倍数的两边，至于证明什么的可以去找数竞。
或者可以用埃筛（几乎是线性），或者用欧筛
- 以6的倍数来搞事的判断方法：
-
1 bool prime(int n) 2 { 3 if(n==1)return false; 4 if(n==2||n==3)return true; 5 if(n%6!=1&&n%6!=5)return false; 6 for(int i=5;i*i<=n;i+=6) 7 if(n%i==0||n%(i+2)==0)retrun false; 8 return true; 9 }View Code埃筛
-
1 void make_prime() 2 { 3 memset(prime,true,sizeof(prime)); 4 prime[0]=prime[1]=false; 5 int t=sqrt(MAXN); 6 for(register int i=2;i<=t;i++)if(prime[i]) 7 for(register int j=2*i;j<MAXN,j+=i) 8 prime[j]=false; 9 }View Code欧筛
-
1 void make_prime() 2 { 3 memset(prime,true,sizeof(prime)); 4 prime[0] = prime[1] = false; 5 for( int i = 2; i <= MAXN; i++) { 6 if( prime[i] ) Prime[ num ++ ] = i; 7 for(int j = 0;j<num && i*Prime[j] < MAXN; j++) { 8 prime[ i*Prime[j] ] = false; 9 if( !( i%Prime[j] ) ) break; 10 } 11 } 12 return; 13 }View Code还有一些其他搞事的办法，但埃筛，一般就够用了
五·最小生成树
人生信条能打kruskal永远不打prim!!!!!!
1 void kruskal()
2 {
3 int f1,f2,k,i;
4 k=0;
5 for(i=1;i<=n;i++)
6 prt[i]=i;
7 for(i=1;i<=m;i++)
8 {
9 f1=find(a[i].x);
10 f2=find(a[i].y);
11 if(f1!=f2)
12 {
13 ans=ans+a[i].z;
14 prt[f1]=f2;
15 k++;
16 if(k==n-1)
17 break;
18 }
19 }
20 if(k<n-1)
21 {
22 cout<<"orz"<<endl;
23 bj=0;
24 return ;
25 }
26 }
View Code
六·单源最短路弱化版（SPFA）
能打SPFA不打dijkstra!!!!!!!!
1 inline void spfa(int k)
2 {
3 queue< int >q;
4 dis[k] = 0; q.push(k); vis[k] = 0;
5 while(!q.empty()) {
6 x = q.front(); q.pop(); vis[x] = 0;
7 for(int i = head[x]; i != 0; i = way[i].next ) {
8 if(dis[x] + way[i].w < dis[way[i].to]) {
9 dis[way[i].to] = dis[x] + way[i].w;
10 if(vis[way[i].to] == 0) {
11 q.push(way[i].to);
12 vis[way[i].to] = 1;
13 }
14 }
15 }
16 }
17 }
View Code
七·树状数组
1 int lowbit(int x)
2 {
3 return x&(-x);
4 }
5 int add(int x,int y)
6 {
7 while(x<=n)
8 {
9 c[x]+=y;
10 x+=lowbit(x);
11 }
12 }
13 int sum(int x)
14 {
15 int res=0;
16 while(x>0)
17 {
18 res+=c[x];
19 x-=lowbit(x);
20 }
21 return res;
22 }
View Code
八·乘法逆元
线性的，还有什么费马小，感觉没什么用，就没打
1 int CFNY(int n)
2 {
3 inv[1]=1;
4 cout<<1<<endl;
5 for(int i=2;i<=n;i++)
6 {
7 inv[i]=(long long )(p-p/i)*inv[p%i]%p;
8 cout<<inv[i]<<endl;
9 }
10 }
View Code
九·康托展开
绝对没人会在NOIP考这个东西，要是他考了，以后就可以说 这很NOIP。。。。
1 ll kangtuo(ll x[])
2 {
3 ll p=0;
4 for(ll i=1;i<=n;i++)
5 {
6 ll t=0;
7 for(ll j=i+1;j<=n;j++)
8 {
9 if(x[i]>x[j])
10 {
11 t++;
12 }
13 }
14 p+=t*fc[n-i];
15 }
16 return p+1;
17 }
View Code
十·最近公共祖先（LCA）
1 void dfs(int x,int father)//x为当前节点，father为其父节点
2 {
3 deep[x]=deep[father]+1;//当前点的深度为其父节点深度加1
4 parents[x][0]=father;//当前点的2^0祖先(也就是上1级祖先)就是其父节点
5 for(int i=1;(1<<i)<=deep[x];i++)
6 {
7 parents[x][i]=parents[parents[x][i-1]][i-1];
8 //这里应该是整个预处理阶段中最有灵魂的部分了
9 //x的2^i级祖先就是x的2^(i-1)级祖先的2^(i-1)级的祖先 。
10 //2^i==2^(i-1)+2^(i-1),这个式子好像没什么可说的
11 }
12 for(int i=head[x];i;i=way[i].next)
13 {
14 int to=way[i].to;
15 if(to!=father)
16 dfs(to,x);
17 }
18 }
19
20 int lca(int a,int b)//a,b为两个要查询的点
21 {
22 if(deep[a]>deep[b])//我时刻保证a的深度比b的小
23 {
24 swap(a,b); //如果反了就换一下
25 }
26 for(int i=20;i>=0;i--)
27 {
28 if(deep[a]<=deep[b]-(1<<i))
29 b=parents[b][i];//将a和b跳的同一高度
30 }
31 if(a==b)//如果b在跳上来时和a一样了，那说明a就是a和b的LCA，直接返回就行了
32 return a;
33 for(int i=20;i>=0;i--)
34 {
35 if(parents[a][i]==parents[b][i])
36 continue;
37 else
38 {
39 a=parents[a][i];
40 b=parents[b][i];//将a和b一起往上跳
41 }
42 }
43 return parents[a][0];//找出最后的答案
44 }
View Code
十一·卢卡斯
只存在于组合数里的东西
1 long long CC(long long n,long long m){
2 if(m>n)
3 return 0;
4 return ((c[n]*KSM(c[m],p-2,p))%p*KSM(c[n-m],p-2,p)%p);
5 }
6 long long Lucas(long long n,long long m){
7 if(!m)
8 return 1;
9 return CC(n%p,m%p)*Lucas(n/p,m/p)%p;
10 }
View Code
十二·二分图匹配
1 int dfs(int t)
2 {
3 for (int i=1; i<=n2; ++i)
4 if (a[t][i] == 1 && check[i] == 0)
5 {
6 check[i] = 1;
7 if (p[i] == 0 || dfs(p[i]) == 1)
8 {
9 p[i] = t;
10 return 1;
11 }
12 }
13 return 0;
14 }
View Code
十三·强连通分量（tarjan）
1 void tarjan(int s)
2 {
3 dfn[s]=low[s]=++tim;
4 in[s]=1,stack[++top]=s;
5 for(int i=head[s];i;i=edge[i].next)
6 {
7 int v=edge[i].to;
8 if(!dfn[v])
9 {
10 tarjan(v);
11 low[s]=min(low[v],low[s]);
12 }
13 else if(in[v]&&low[s]>dfn[v])low[s]=dfn[v];
14 }
15 if(dfn[s]==low[s])
16 {
17 int p;
18 belong[s]=++cnt;
19 do
20 {
21 p=stack[top--];
22 in[p]=0;
23 belong[p]=cnt;
24 }while(p!=s);
25 }
26 }
View Code
十四·割点（还是那个有名的tarjan）
1 int tarjan(int x,int y)
2 {
3 low[x]=dfn[x]=++tim;
4 int child=0;
5 for(int i=head[x];i;i=way[i].next)
6 {
7 int v=way[i].to ;
8 if(!dfn[v])
9 {
10 tarjan(v,y);
11 low[x]=min(low[x],low[v]);
12 if(dfn[x]<=low[v]&&x!=y)
13 {
14 cut[x]=1;
15 }
16 if(x==y)
17 {
18 child++;
19 }
20 }
21 low[x]=min(low[x],dfn[v]);
22 if(child>=2&&x==y)
23 {
24 cut[x]=1;
25 }
26 }
27 }
View Code
十五·对拍之造数据（maker）Windows下
eg. 2个正整数x0,y0
1 #include<bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5 freopen("data.in","w",stdout);
6 srand(time(NULL));
7 int n=rand();
8 int m=rand();//可以在这里加模数来控制范围
9 cout<<n<<" "<<m<<endl;
10 }
View Code
十六·对拍之检查（check）Windows下
这个在用之前一定要先把所有的程序先跑一下，然后一定要在同一各根目录下，不然有可能会用一些很神奇的东西把源程序给覆盖掉
1 #include<bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5 while(1)
6 {
7 system("maker");
8 system("true");
9 system("false");
10 if(system("fc false.out true.out")
11 {
12 cout<<"WA"<<endl;
13 break;
14 }
15 cout<<"AC"<<endl;
16 }
17 return 0;
18 }
View Code
十七·缩点（还是那个tarjan）
1 void tarjan(int x)
2 {
3 low[x]=dfn[x]=++tim;
4 stac[++top]=x;
5 vis[x]=1;
6 for(int i=head[x];i;i=edge[i].next)
7 {
8 int v=edge[i].to;
9 if(!dfn[v])
10 {
11 tarjan(v);
12 low[x]=min(low[x],low[v]);
13 }
14 else if(vis[v])
15 {
16 low[x]=min(low[x],dfn[v]);
17 }
18 }
19 if(dfn[x]==low[x])
20 {
21 int y;
22 while(y=stac[top--])
23 {
24 sd[y]=x;
25 vis[y]=0;
26 if(x==y)
27 break;
28 p[x]+=p[y];
29 }
30 }
31 }
View Code
十八·网络最大流（很NOIP的一个东西）
1 int bfs()
2 {
3 memset(deep,0x3f,sizeof(deep));
4 memset(in,0,sizeof(in));
5 deep[s]=0;
6 queue<int >q;
7 q.push(s);
8 while(!q.empty())
9 {
10 int x=q.front();
11 q.pop();
12 in[x]=0;
13 for(int i=head[x];i;i=way[i].next)
14 {
15 int v=way[i].to;
16 if(deep[v]>deep[x]+1&&way[i].value)
17 {
18 deep[v]=deep[x]+1;
19 if(in[v]==0)
20 {
21 q.push(v);
22 in[v]=1;
23 }
24 }
25 }
26 }
27 if(deep[t]!=0x3f3f3f3f)
28 return 1;
29 return 0;
30 }
31 int dfs(int x,int y)
32 {
33 ans=0;
34 if(x==t)
35 return y;
36 for(int i=head[x];i;i=way[i].next)
37 {
38 int v=way[i].to;
39 if(way[i].value&&deep[v]==deep[x]+1)
40 {
41 if(ans=dfs(v,min(y,way[i].value)))
42 {
43 way[i].value-=ans;
44 way[i^1].value+=ans;
45 return ans;
46 }
47 }
48 }
49 return 0;
50 }
51 int dinic()
52 {
53 low=0;
54 while(bfs())
55 {
56 while(low=dfs(s,inf))
57 maxnn+=low;
58 }
59 return maxnn;
60 }
View Code
十九·最小费用最大流
1 int spfa()
2 {
3 memset(dis,0x3f,sizeof(dis));
4 memset(pre,0,sizeof(pre));
5 memset(in,0,sizeof(in));
6 queue<int >q;
7 q.push(s);
8 in[s]=1;
9 dis[s]=0;
10 while(!q.empty())
11 {
12 int x=q.front();
13 q.pop();
14 in[x]=0;
15 for(int i=head[x];i;i=way[i].next)
16 {
17 int v=way[i].to;
18 int w=way[i].cost;
19 if(way[i].value>0&&dis[v]>dis[x]+w)
20 {
21 dis[v]=dis[x]+w;
22 pre[v].from=x;
23 pre[v].edge=i;
24 if(in[v]==0)
25 {
26 q.push(v);
27 in[v]=1;
28 }
29 }
30 }
31 }
32 return dis[t]!=0x3f3f3f3f;
33 }
34 int ek()
35 {
36 ans=0;
37 cost=0;
38 int mi;
39 int i;
40 while(spfa())
41 {
42 mi=inf;
43 for(i=t;i!=s;i=pre[i].from)
44 {
45 mi=min(mi,way[pre[i].edge].value);
46 }
47 for(i=t;i!=s;i=pre[i].from)
48 {
49 way[pre[i].edge].value-=mi;
50 way[pre[i].edge^1].value+=mi;
51 }
52 ans+=mi;
53 cost+=mi*dis[t];
54 }
55 return ans;
56 }
View Code
二十·