acm算法模板1.docx
- 文档编号:1999597
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:137
- 大小:52.12KB
acm算法模板1.docx
《acm算法模板1.docx》由会员分享,可在线阅读,更多相关《acm算法模板1.docx(137页珍藏版)》请在冰点文库上搜索。
acm算法模板1
算法模板1
基础算法2
进制转换2
最长XX序列3
并查集4
食物链4
银河英雄传说5
高精度6
一、正整数6
二、实数10
数论17
欧拉函数17
稳定婚姻17
Pick'sTheore18
图论19
Dij堆优化19
一、STL19
二、数组20
BELLMAN-FOLD22
SPFA23
LCA(不完整)25
一、tongji106825
二、pku133026
最小树形图27
利用Floyed算法求最小环29
欧拉回路31
字符串处理32
KMP32
GreatestCommonIncreasingSubsequence(TJU2707)33
字母树Trie34
AC自动机35
后缀数组38
Pku3415堆栈扫描38
Pku2758动态更新41
Bupt1302hard二分求解45
RMQ49
平衡树50
TREAP50
魔兽争霸50
郁闷的出纳员52
树状数组54
线段树55
pku3368,线段树的一个常用的用法,记录左右区间以及中间的合并55
pku3468,记录delta变量57
zju1610统计区间信息58
pku1151面积扫描59
pku1177,周长扫描61
树套树63
矩形切割65
网络流66
最大流66
Pku228966
分数划分69
求最小割73
最优比率生成树76
最大密度子图78
最大权闭合图81
费用流84
pku368084
Pku251686
基础算法
进制转换
ints[100];
intmain()
{
inti,n,r;
while(cin>>n>>r)
{
i=0;
cout< while(n! =0) { i++; s[i]=n%r; n=n/r; if(s[i]<0) { s[i]=s[i]-r; n++; } } for(;i>=1;i--) if(s[i]>=10)cout< cout<<"(base"< } return0;} 最长XX序列 结论: 上升序列的最小个数==不降序列的最长长度 structnode{ intl,w; }; nodea[20002]; intb[20002]; boolcmp(constnode&a,constnode&b){returna.l intdp(intn) { inti,l,r,m,len; memset(b,0,sizeof(b)); b[0]=1<<30; b[1]=a[1].w; len=1; for(i=2;i<=n;++i) { l=0,r=len; while(l<=r) { m=(l+r)>>1; if(b[m]>=a[i].w)l=m+1; elser=m-1; } b[l]=a[i].w; if(l>len)len++; } returnlen; } intmain() { inti,n,t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].w); sort(a+1,a+1+n,cmp); printf("%d\n",dp(n)); } return0; } 并查集 食物链 Constintmaxn=50010; introot[maxn],d[maxn]; voidcalc(inti,intf) { if(root[i]==f)return; calc(root[i],f); d[i]=(d[i]+d[root[i]])%3; root[i]=f; } intfind(inti) { intf; f=i; while(root[f]! =f)f=root[f]; calc(i,f); returnf; } intmain() { inti,n,k,dxy,x,y,fx,fy,num; num=0; scanf("%d%d",&n,&k); for(i=1;i<=n;i++)root[i]=i; memset(d,0,sizeof(d)); while(k--) { scanf("%d%d%d",&dxy,&x,&y); dxy--; if((x==y&&dxy==1)||x<1||x>n||y<1||y>n) { num++; continue; } fx=find(x);fy=find(y); if(fx==fy) { if((d[y]-d[x]+3)%3! =dxy)num++; } else { root[fy]=fx; d[fy]=(d[x]+dxy-d[y]+3)%3; } } printf("%d\n",num); return0; } 银河英雄传说 constintmaxn=30001; introot[maxn],ahead[maxn],num[maxn]; intf; inlineintcalc(inti){ if(root[i]! =f)ahead[i]+=calc(root[i]); root[i]=f; returnahead[i]; } intfind(inti){ f=i; while(root[f]! =f)f=root[f]; calc(i); returnf; } intmain() { inti,n,x,y,fx,fy; charc; while(scanf("%d",&n)&&n) { for(i=1;i { root[i]=i; num[i]=1; } memset(ahead,0,sizeof(ahead)); for(i=1;i<=n;i++) { scanf("%c%d%d",&c,&x,&y); fx=find(x);fy=find(y); if(c=='M'){ root[fx]=fy; ahead[fx]+=num[fy]; num[fy]+=num[fx]; } else{ if(fx! =fy)printf("-1\n"); elseprintf("%d\n",abs(ahead[x]-ahead[y])-1); } } } return0; } 高精度 一、正整数 //只能表示正整数;只能大减小,大除小; typedeflonglongintlongint; constintbase=1000000000; constintmaxn=500; structbigint{ intlen; intdata[maxn]; bigint(): len(0){} bigint(constbigint&x): len(x.len){memcpy(data,x.data,len*sizeof(int));} bigint(intx): len(0){for(;x>0;x/=base)data[len++]=x%base;} bigint&operator=(constbigint&x){ len=x.len; memcpy(data,x.data,len*sizeof*data); return*this; } int&operator[](inti){returndata[i];} intoperator[](inti)const{returni data[i]: 0;} }; intcompare(constbigint&a,constbigint&b){ inti; if(a.len! =b.len)returna.len>b.len? 1: -1; for(i=a.len-1;i>=0&&a[i]==b[i];i--); if(i<0)return0; returna[i]>b[i]? 1: -1; } booloperator==(constbigint&a,constbigint&b){returncompare(a,b)==0;} booloperator! =(constbigint&a,constbigint&b){returncompare(a,b)! =0;} bigintoperator+(constbigint&a,constbigint&b){ bigintc; inti; intx=0; for(i=0;i if(i if(i c[i]=x%base; x/=base; } c.len=i; returnc; } bigintoperator-(constbigint&a,constbigint&b){ bigintc; intx=0; c.len=a.len; inti; for(i=0;i c[i]=a[i]-x; if(i if(c[i]<0)x=1,c[i]+=base;elsex=0; } while(c.len>0&&c[c.len-1]==0)c.len--; returnc; } bigintoperator*(constbigint&a,constintb) { inti; if(b==0)return0; bigintc; longintx=0; for(i=0;i { if(i c[i]=x%base; x/=base; } c.len=i; returnc; } bigintoperator*(constbigint&a,constbigint&b){ inti; if(b.len==0)return0; bigintc; for(i=0;i longintx=0; for(intj=0;j if(j if(i+j if(i+j>=c.len)c[c.len++]=x%base;elsec[i+j]=x%base; x/=base; } } returnc; } bigintoperator/(constbigint&a,constintb){ bigintc; inti; longintx=0; for(i=a.len-1;i>=0;i--){ x=x*base+a[i]; c[i]=x/b; x%=b; } c.len=a.len; while(c.len>0&&c[c.len-1]==0)c.len--; returnc; } bigintoperator/(constbigint&a,constbigint&b){ inti; bigintc,x=0; intl,r,mid; for(i=a.len-1;i>=0;i--){ x=x*base+a[i]; l=0; r=base-1; while(l<=r){ mid=(l+r)>>1; if(compare(b*mid,x)<=0)l=mid+1;elser=mid-1; } c[i]=r; x=x-b*r; } c.len=a.len; while(c.len>0&&c[c.len-1]==0)c.len--; returnc; } bigintoperator%(constbigint&a,constbigint&b){ bigintc,x; c=a/b; x=a-b*c; returnx; } istream&operator>>(istream&input,bigint&x){ charc; for(x=0;input>>c;){ x=x*10+(c-'0'); if(input.peek()<='')break; } returninput; } ostream&operator<<(ostream&output,constbigint&x){ inti,j; output<<(x.len==0? 0: x[x.len-1]); for(i=x.len-2;i>=0;i--) for(j=base/10;j>0;j/=10)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- acm 算法 模板