距离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
二十·