上海大学ACM模板

《上海大学ACM模板》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

字符串处理21、KMP算法22、扩展KMP53、Manacher最长回文子串64、AC自动机75、后缀数组96、后缀自动机137、字符串HASH15数学171、素数172、素数筛选和合数分解193、扩展日几里得算法（求ax+by=gcd的解以及逆元素）204、求逆元205梯级性方程绢206、随雨素数测次而关薪芬葡记；茴七二二二二二二二二二二二二二二二二二二217、欧拉函数248、高斯消元（浮点数）259、FFT2610、高斯消元法求方程组的解2911、整数拆分3412、求A^B的约数之和对MOD取模3613、莫比乌斯反演3714Baby-StepGiant-Step3915、自适应simpson积务40相关公式40数据结构421、划分树422、RMQ433、树链剖分454、伸展树（splaytree）505、动态留556、主席留607、Treap70图论751、最短路752、最小生成树793、次小生成树804、有向图的强连通分量815、图的割点、桥和双连通分支的基本概念846、割点与桥857、边双连通分支888、点双连通分支909、最小树形图9310、二分图匹配9511、生成树计数9811、二分图多重匹配10112、KM算法（二分图最大权匹配）10213、最大流10314、最小费用最大流10915、2-SAT11016、曼哈顿最小生成树11417、一般图匹配带花树11718、LCA12019、欧拉路126

1计算几何1331、sx1332、凸包1383、平面最近点对(HDU1007)1395、半平由交1466、亍点求圆心坐标(三角形外心)1498、Pick公式150动态规划1501、最长上升子序列O(nlogn)150搜索1511、DancingLinks151其他1561、高精度1562、完全高精度1583、strtok和sscanf结合输入1634、解决爆栈，手动加栈1635、STL1636、输入输出外挂1657、莫队算法1668、VIM配置172字符串处理1、KMP算法/**next[]的含义:x[i-next(i]...i-l]=x[0...next[i]-1]*next[i]为满足・・i-l]=x[0.・・z-l]的最大z值(就是x的自身匹配)*/voidJanp_pre(charx[],intm,intnext[])int1,j;j=next[0]=-l;i=0;while(i

2*返回x在丫中出现的次数，可以重叠*/intnext[10010];intKMP_Count(charx[],intm,chary[],intn){//x是模式串，y是主串inti,j;intans=0;//preKMP(x,m,next);kmp_pre(x,m,next);i=j=0;while(i=m)ans++;j=next[j];returnans;经典题目：POJ3167/**POJ3167CowPatterns*模式串可以浮动的模式匹配问题*给出模式串的相对大小，需要找出模式串匹配次数和位置*比如说模式串：1,4,4,2,3,1而主串：5,6,2,10,10,7,3,2,9*那么2,10,10,7,3,2就是匹配的**统计比当前数小，和于当前数相等的，然后进行皿*/#include#include#include#include〈algorithm)#includeusingnamespacestd;constintMAXN=100010;constintMAXM=25010;inta[MAXN];intb[MAXN];intn,m,s;intas[MAXN][30];intbs[MAXM][30];voidinit(){for(inti=0;i

3for(intj=l;j<=25;j++)bs[i][j]=bs[i-l][j];}bs[i][b[i]]++;}}intnext[MAXM];voidkmp_pre()(int1,j;j=next[0]=-l;i=0;while(i0)tll+=bs[i][k]-bs[i-j-1][k];elsetll+=bs[i][k];)if(i-j>0)tl2=bs[i][b[i]]-bs[i-j-l][b[i]];elsetl2=bs[i][b[i]];for(intk=l;kans;voidkmp()(ans•clear();inti,j;kmp__pre();i=j=O;while(i0)tll+=as[i][k]-as[i-j-1][k];elsetll+=as[i][k];)if(i-j>0)tl2=as(i][a[i]]-as[i-j-l][a[i]];elsetl2=as[i][a[i]];for(intk=l;k.=m)(ans.push_back(i-m+1);j=next[j];))elsej=next[j];}

4)intmain()while(scanf(n%d%d%dn,&n,&m,&s)==3)(for(inti=0;i

5nrans.size());for(inti=0;i

6”，ans[i]);}return0;2、扩展KMP/**扩展KMP算法*///next[i]:x[i...m-1]与x[0...m-1]的最长公共前缀//extend[i]:y[i.・・n-l]与x[0...m-1]的最长公共前缀voidpre_EKMP(charx[],intm,intnext[])next[0]=m;intj=0;while(j+l

73、Manacher最长回文子串/**求最长回文子串*7constintMAXN=110010;charMa[MAXN*2];intMp[MAXN*2];voidManacher(chars[]zintlen)(int1=0;Ma[l++]=»$'；Ma[l++]=";for(inti=0;ii?min(Mp[2*id-i],mx-i):1;while(Ma[i+Mp[i]]==Ma[i-Mp[i]])Mp[i]++;if(i+Mp[i]>mx)(mx=i+Mp[i];id=i;)*abaaba*i:012345678910111213*Ma[i]:$#a#b#a#a$b#a#*Mp[i]:11214127214121*/chars[MAXN];intmain()while(scanf(H%sMfs)==1)(intlen=strlen(s);Manacher(s,len);intans=0;for(inti=0;i<2*len+2;i++)ans=max(ans,Mp[i]-1);printf(n%d

8n,ans);}return0;)4、AC自动机H=======_5s//HDU2222//求Fl标串中出现了几个模式串

9#include#include〈algorithm〉#include#include#includeusingnamespacestd;structTrie(intnext[500010][26],fail[500010],end[500010];introotrL;intnewnode()(for(inti=0;i<26;i++)next[L][i]=-1;end[L++]=0;returnL-l;}voidinit()(L=0；root=newnode();}voidinsert(charbuf[])(intlen=strlen(buf);intnow=root;for(inti=0;iQ;fail[root]=root;for(inti=0;i<26;i++)if(next[root][i]==-1)next[root][i]=root;else{fail[next[root][i]]=root;Q.push(next[root][i]);)while(!Q.empty())(intnow=Q.front();Q.popO;for(inti=0;i<26;i++)if(next[now][i]==-1)next[now][i]=next[fail[now]][i];else(fail[next[now][i]]=next[fail[now]][i];Q.push(next[now][i]);intquery(charbuf[])(intlen=strlen(buf);intnow=root;intres=0;for(inti=0;i

10for(inti=0;i

11");)})；charbuf[1000010];Trieac;intmain()(intT;intn;scanf(M%d"z&T);while(T-)(scanf(,&n);ac.init();for(inti=0;i

12M,ac.query(buf));}return0;)5、后缀数组5.1DA算法/**suffixarray*倍增算法O(n*logn)*待排序数组长度为n,放在。〜n-l中，在最后面补一个0*da(strrn+lrsa,rank,height,,);//注意是n+1;*例如：*n=8;*num[]={1,1,2,1,1,1,1,2,$};注意num最后一位为0,其他大于0*rank[]={4,6,8,1,2,3,5,7,0};rank[0〜n-1]为有效值，rank【n]必定为。无效值*sa[]={8,3,4,5,0,6,1,7,2};旭[1〜n]为有效值，2[0]必定为n是无效值♦height[]={0,0,3,2,3,1,2,0,1};height[2〜n]为有效值constintMAXN=20010;inttl[MAXN],t2[MAXN],c[MAXN];//求SA数组需要的中间变量，不需要赋值//待排序的字符串放在s数组中，从s[0]到s[n-1],长度为n,且最大值小于m,//除s[n-l]外的所有s[i]都大于0,r[n-l]=0//函数结束以后结果放在,数组中boolcmp(int*r,inta,intb,int1){returnr[a]==r[b]&&r[a+1]==r[b+1];}voidda(intstr[],intsa[]zintrank[],intheight[],intnrintm){n++;inti,j,p,*x=tl,*y=t2;

13//第一轮基数排序，如果s的最大值很大，可改为快速排序for(i=0;i=0;i-)sa[-c[x[i]]]=i;for(j=1;j<=n;j<<=1){P=0;〃直接利用空数组排序第二关键字for(i=n-j;i=j)y[p++]=sa[i]-j;//这样数组y保存的就是按照第二关键字排序的结果//基数排序第一关键字for(i=0;i=0;i—)sa[—c[x[y[i]]]]=y[i];//根据,和x数组计算新的x数组swap(x,y);p=1;x[sa(0]]=0;for(i=1;i=n)break;m=p;//下次基数排序的最大值}intk=0;n--;for(i=0;i<=n;i++)rank[sa[i]]=i;for(i=0;ib)swap(a,b);returnheight[askRMQ(a+1,b)];)charstr[MAXN];intr[MAXN];intsa[MAXN];intmain()(while(scanf(M%sn,str)==1){intlen=strlen(str);intn=2*len+1;for(inti=0;i

14r[n]=0;da(r,sa,rank,height,n,128);for(inti=l;i<=n;i++)RMQ[i]=height[i];initRMQ(n);intans=0,st;inttmp;for(inti=0;ians){ans=2*tmp;st=i-tmp;}tmp=lcp(i,n-i-1);〃奇数对称if(2*tmp-l>ans)

15ans=2*tmp-l;st=i-tmp+l;)}str[st+ans]=0;printf('*%s

16n,str+st);)return0;5.2DC3算法da口和str□数组要开大三倍，相关数组也是三倍/**后缀数组*DC3算法，复杂度O(n)*所有的相关数组都要开三倍constintMAXN=2010;#defineF(x)((x)/3+((x)%3==l?0:tb))#defineG(x)((x)=0;i——)b[~wss[wv[i]]]=a[i];)voiddc3(int*r,int*safintn,intm)(inti,jf*rn=r+n;int*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;r[n]=r[n+1]=0;for(i=0;i

17//str和sa也要三倍voidda(intstr[],intsa[]zintrank[],intheight[],intnrintm){for(inti=n;ilen+l);np->pos=len;SAM_last=np;for(;p&&!p->next[x];p=p->fa)p->next[x]=np;if(!p){np->fa=SAM_root;return;)SAM_Node*q=p->next[x];if(q->len==p->len+1)np->fa=q;return;)SAM__Node*nq=newSAM_Node(q);nq->len=p->len+1;q->fa=nq;np->fa=nq;for(;p&&p->next[x]==q;p=p->fa)p->next[x]=nq;

18)voidSAM_build(char*s)SAM_init();intlen=strlen(s);for(inti=0;ilenif(!SAM_last->next[s[i]-*0*]||!(SAM_last->next[s[i]-i+1))SAM_add(s[i]一1O',i+1);elseSAM_last=SAM_last->next[s[i]-101]；7、字符串HASHHDU4622求区间不相同子串个数constintHASH=10007;constintMAXN=2010;structHASHMAP《inthead[HASH],next[MAXN],size;unsignedlonglongstate[MAXN];intf[MAXN];voidinit()(size=0;memset(head,-1,sizeof(head));}intinsert(unsignedlonglongval,int_id)(inth=val%HASH;for(inti=head[h];i!=-1;i=next[i])if(val==state[i])|inttmp=f[i];f[i]=_id;returntmp;)f[size]=_id;state[size]=val;next[size]=head(h];head[h]=size++;return0;)}H;constintSEED=13331;unsignedlonglongP[MAXN];unsignedlonglongS[MAXN];charstr[MAXN];intans[MAXN][MAXN];

19intmain()(//freopen("in.txt","r",stdin);//freopen(Mout.txtM,nwM,s-dout);P[0]=1;for(inti=1;i=0;i)for(intj=i;j<=n;j++)ans[i][j]+=ans[i+1][j]+ans[i][j-1]-ans[i+1][j-1];intm,u,v;scanf("%dM,&m);while(m——)scanf("%d*d”，&u,&v);printf(n%d

20n,ans[u][v]);return0;

21数学1、素数1.1素数筛选(判断MAXN/i)continue;//1%'1L[fiji*i溢II；(或酉i,j用longlong)//直接从i*i开始就可以，小于i倍的已经筛选过了，注意是j+=ifor(intj=i*i;j#include#include#includeusingnamespacestd;constintMAXN=100010;intprime[MAXN+1];voidgetPrime()(memset(prime,0,sizeof(prime));

22for(inti=2;i<=MAXN;i++)(if(!prime[i])prime[++prime[0]]=i;for(intj=l;j<=prime[0]&&prime[j]<=MAXN/i;j++)prime[prime[j]*i]=1;if(i%prime[j]==0)break;))boolnotprime[1000010];intprime2[1000010];voidgetPrime2(intL,intR){memset(notprime,false,sizeof(notprime));if(L<2)L=2;for(inti=l;i<=prime[0]&&(longlong)prime[i]*prime[i]<=R;i++)(ints=L/prime[i]+(L%prime[i]>0);if(s==l)s=2;for(intj=s;(longlong)j*prime[i]<=R;j++)if((longlong)j*prime[i]>=L)notprime[j*prime[i]-L]=true;prime2[0]=0;for(inti=0;i<=R-L;i++)if(!notprime[i])prime2[++prime2[0]]=i+L;}intmain()getPrime();intL,U;while(scanf("%d%dn,&L,&U)==2)(getPrime2(L,U);if(prime2[0]<2)printf("Therearenoadjacentprimes.

23n);else(intxl=0,x2=100000000zyl=0ry2=0;for(inti=l;iy2-yl){yl=prime2[i];y2=prime2[i+1];})printf("%d,%dareclosest,%d,%daremostdistant.

24",xl,x2ryl,y2);))}2、素数筛选和合数分解//素数筛选和合数分解constintMAXN=10000;intprime[MAXN+1];voidgetPrime(){memset(prime,0,sizeof(prime));for(inti=2;i<=MAXN;i++){if(!prime[i])prime[++prime[0]]=i;for(intj=l;j<=prime[0]&&prime[j]<=MAXN/i;j++)(prime[prime[j]*i]=1;if(i%prime[j]==0)break;}))longlongfactor[100][2];intfatCnt;

25intgetFactors(longlongx)(fatCnt=0;longlongtmp=x;for(inti=l;prime[i]<=tmp/prime[i];i++){factor[fatCnt][l]=0;if(tmp%prime[i]==0){factor[fatCnt][0]=prime[i];while(tmp%prime[i]==0)[factor[fatCnt][1]++;tmp/=prime[i];}fatCnt++;})if(tmp!=l)factor[fatCnt][0]=tmp;

26factor[fatCnt++][1]=1;)returnfatCnt;}//★★**★★**★★**********★****★***★**★★**★★**★★3、扩展欧几里得算法(求ax+by=gcd的解以及逆元素)〃返回d=gcd(a,b);和对应于等式ax+by=d中的x,ylong&y)longlongextend_gcd(longlonga,longlongb,longlong&x,long(if(a==0&&b==0)returnT;//无坡大公约数if(b==0){x=l;y=0;returna;}longlongd=extend_gcd(b,a%b,y,x);y-=a/b*x;returnd;)I/*★***★**********************//ax=1(modn)longlongmod_reverse(longlonga,longlongn)(longlongx,y;longlongd=extend_gcd(a,n,x,y);if(d==l)return(x%n+n)%n;elsereturn-1;4、求逆元4.1扩展欧几里德法(见上面)4.2简洁写法注意：这中只能求a

27if(a==0&&b==0)return-1;if(b==0){x=1;y=0;returna;}longlongd=extend_gcd(b,a%bfy,x);y-=a/b*x;returnd;}intm[10],a[10];//模数为m,余数为a,X%m=aboolsolve(int&m0zint&a0,intm,inta)(longlongy,x;intg=extend_gcd(mO,m,x,y);if(abs(a-aO)%g)returnfalse;x*=(a-aO)/g;x%=m/g;aO=(x*m0+aO);mO*=m/g;aO%=mO;if(aO<0)aO+=mO;returntrue;)/**无解返回false,有解返回true;*解的形式最后为aO+mO*t(0<=a0

28while(b){if(b&1)(ret+=tmp;if(ret>c)ret-=c;〃直接取模慢很多}tmp<<=1;if(tmp>c)tmp-=c;b>>=1;)returnret;)//计算ret=(aAn)%modlonglongpow_mod(longlonga,longlongn,longlongmod){longlongret=1;longlongtemp=a%mod;while(n)(if(n&1)ret=mult_mod(ret,temp,mod);temp=mult_mod(temp,temp,mod);n>>=1;}returnret;)//通过aA(n-l)=l(担2_n)来判断n是不是素数//n-1=x*2At中间使用二次判断//是合数返回true,不一定是合数返回falseboolcheck(longlonga,longlongnzlonglongx,longlongt){longlongret=pow_mod(a,x,n);longlonglast=ret;for(inti=1;i<=t;i++)(ret=mult_mod(ret,ret,n);if(ret==1&&last!=1&&last!=n-1)returntrue;//合数last=ret;)if(ret!=1)returntrue;elsereturnfalse;}//Miller_Rabin算法//是素数返回true,(可能是伪素数)II不是素数返回falseboolMiller_Rabin(longlongn){if(n<2)returnfalse;if(n==2)returntrue;if((n&l)==0)returnfalse;//偶数longlongx=n-1;longlongt=0;while((x&l)==0){x>>=1;t++;)srand(time(NULL));/*****************for(inti=0;i=0)returna;elsereturn-a;}//找出一个因子

29longlongpollard_rho(longlongx,longlongc){longlongi=1,k=2;srand(time(NULL));longlongxO=rand()%(x-1)+1;longlongy=xO;while(1)(i++；xO=(mult_mod(x0fxO,x)+c)%x;longlongd=gcd(y-xO,x);if(d!=1&&d!=x)returnd;if(y==xO)returnx;if(i==k){y=xO;k+=k;}}}//对n进行素因子分解，存入factor.k设置为107左右即可voidfindfac(longlongn,intk){if(n==1)return;if(Miller_Rabin(n))(factor[tol++]=n;return;}longlongp=n;intc=k;while(p>=n)p=pollard_rho(p,c-);//值变化，防止死循环kfindfac(p,k);findfac(n/p,k);)//POJ1811//给出一个N(2<=N<274),如果是素数，输出“Prime”，否则输出最小的素因子intmain()(intT;longlongn;scanf&T);while(T-)(scanf("%I64dM,&n);if(Miller_Rabin(n))printf("Prime

30M);else{tol=0;findfac(n,107);longlongans=factor[0];for(inti=1;i

31Mrans);)}return0;)7、欧拉函数6.1分解质因素求欧拉函数getFactors(n);intret=n;for(inti=0;i

32)if(n>1)ans-=ans/n;returnans;)6.1线性筛(同时得到欧拉函数和素数表)constintMAXN=10000000;boolcheck[MAXN+10];intphi[MAXN+10];intprime[MAXN+10];inttot;//索数的个数voidphi_and_prime_table(intN)(memset(check,false,sizeof(check));phi[l]=1;tot=0;for(inti=2;i<=N;i++)(if(!check[i]){prime[tot++]=i;phi[i]=i-1;)for(intj=0;jN)break;check[i*prime[j]]=true;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;)else{phi[i*prime[j]]=phi[i]*(prime[j]-1);}}8、高斯消元（浮点数）#defineepsle-9constintMAXN=220;

33存的就是结果doublea[MAXN][MAXN]rx[MAXN];〃方程的左边的矩阵和等式右边的值，求解之后intequ,var;〃方程数和未知数个数/*★返回0表示无解，1表示有解intGauss(){inti,jzk,col,max_r;for(k=0,col=0;k£abs(a[max_r][col]))max_r=i;if(fabs(a[max_r][col])usingnamespacestd;constdoublePI=acos(-1.0);//复数结构体structComplex{doublex,y;//实部和虚部x+yiComplex(double_x=0.0,double_y=0.0)y=_y;)Complexoperator-(constComplex&b)const

34returnComplex(x-b.x,y-b.y);)Complexoperator+(constComplex&b)const{returnComplex(x+b.xry+b.y);)Complexoperator*(constComplex&b)constreturnComplex(x*b.x-y*b.yzx*b.y+y*b.x);))；/**进行FFT和IFFT前的反转变换。*位置i和(i二进制反转后位置)互换*len必须去2的事*/voidchange(Complexy[],intlen){inti,j,k；for(i=lrj=len/2;i=k)(j-=k;k/=2;}if(j

35fft(xl,len,1);fft(x2zlen,1);for(inti=0;i0)len——;for(inti=len;i>=0;i——)printf("%c",sum[i]+10,);printf(M

36M);)return0;}//HDU4609〃给出n条线段长度，问任取3根，组成三角形的概率。〃n<=10八5用FFT求可以组成三角形的取法有几种constintMAXN=400040;Complexxl[MAXN];inta[MAXN/4];longlongnum[MAXN];//100000*100000会超intlonglongsum[MAXN];intmain()intT;intn;scanf(n%d",&T);while(T-)(scanf(*'%d",&n);memset(num,0,sizeof(num));for(inti=0;i

37//减掉一个取本身，另外一个取其它ent-=(n-1);ent-=(longlong)(n-l-i)*(n-i-2)/2;}longlongtot=(longlong)n*(n-1)*(n-2)/6;printf("%.71f

38M,(double)ent/tot);)return0;10、高斯消元法求方程组的解10.1一类开关问题，对2取模的01方程组POJ1681需要枚举自由变元，找解中1个数最少的〃对2取模的01方程组constintMAXN=300;//有equ个方程,var个变元。增广矩阵行数为equ,歹U数为var+1,分另I」为0到varintequ,var;inta[MAXN][MAXN];〃增广矩阵intx[MAXN];//解集intfree_x[MAXN];[元(多解枚举自由变元可以使用)intfree_num;//白由变元的个数//返I可值为-1表示无解，为。是唯•解，否则返回自由变元个数intGauss()(intmax_r,col,k;free_num=0;for(k=0,col=0;kabs(a[max_r][col]))max_r=i;)if(a[max_r][col]==0)k——;free_x[free_num++]=col;//这个是自由变元continue;)if(max_r!=k)(for(intj=col;j=0;i)(x[i]=a[i][var];for(intj=i+l;j0)a[(i-l)*n+j][t]=1;if(i0)a[i*n+j-l][t]=1;if(j

39w);return;

40}elseif(t==0)(intans=0;for(inti=0;i

41nzans);return;)else(//枚举自由变元intans=0x3f3f3f3f;inttot=(l<=0;j){intidx;for(idx=j;idx

42”,ans);))charstr[30][30];intmain()intT;scanf(M%dn,&T);while(T一一)(scanf(w%d'\&n);init();for(inti=0;i

43)10.2解同余方程组POJ2947WidgetFactory//求解对MOD取模的方程组constintMOD=7;constintMAXN=400;inta[MAXN][MAXN];//增广矩阵intx[MAXN];//最后得到的解集inlineintged(inta,intb)(while(b!=0)(intt=b;b=a%b;a=t;}returna;)inlineint1cm(inta,intb)returna/ged(a,b)*b;)longlonginv(longlonga,longlongm){if(a==1)return1;returninv(m%a,m)*(m-m/a)%m;intGauss(intequ,intvar){intmax_r,col,k;for(k=0,col=0;kabs(a[max_r][col]))max_r=i;if(a[max_r][col]==0)continue;)if(max_r!=k)for(intj=col;j=0;i)(

44inttemp=a[i][var];for(intj=i+l;j

45”，x[n-1]);)elseif(ans==-1)printf("Inconsistentdata.

46n);elseprintf("Multiplesolutions.

47n);return0;)11、整数拆分HDU4651constintMOD=le9+7;intdp[100010];voidinit(){memset(dp,0,sizeof(dp));dp[0]=1;for(inti=1;i<=100000;i++)for(intj=1,r=1;i-(3*j*j-j)/2>=0;j++,r*=-1)(dp[i]+=dp[i-(3*j*j-j)/2]*r;dp[i]%=MOD;dp[i]=(dp[i]+MOD)%MOD;if(i-(3*j*j+j)/2>=0)dp[i]+=dp[i-(3*j*j+j)/2]*r;dp[i]%=MOD;dp[i]=(dp[i]+MOD)%MOD;))))intmain()(

48intT;intn;init();scanf(n%d'\&T);while(T-){scanf(M%dwz&n);printf(**%d

49wzdp[n]);)return0;)HDU4658数n(<=10A5)的划分，相同的数重复不能超过k个。constintMOD=le9+7;intdp[100010];voidinit(){memset(dp,0,sizeof(dp));dp[0]=1;for(inti=1;i<=100000;i++)for(intj=1,r=1;i-(3*j*j-j)/2>=0;j++,r*=-1)(dp[i]+=dp[i-(3*j*j-j)/2]*r;dp[i]%=MOD;dp[i]=(dp[i]+MOD)%MOD;if(i-(3*j*j+j)/2>=0)dp[i]+=dp[i-(3*j*j+j)/2]*r;dp[i]%=MOD;dp[i]=(dp[i]+MOD)%MOD;)}))intsolve(intn,intk)(intans=dp[n];for(intj=1,r=-1;n-k*(3*j*j-j)/2>=0;j++,r*=-1){ans+=dp[n-k*(3*j*j-j)/2]*r;ans%=MOD;ans=(ans+MOD)%MOD;if(n-k*(3*j*j+j)/2>=0)(ans+=dp[n-k*(3*j*j+j)/2]*r;ans%=MOD;ans=(ans+MOD)%MOD;))returnans;)intmain(){initO;intT;intn,k;scanfd&T);while(T-)(scanf(**%d%dM，&n,&k);printf("%d

50"，solve(n,k));)

51return0;12、求AAB的约数之和对MOD取模参考POJ1845里面有一种求l+p+pA2+p"3+...pAn的方法。需要素数筛选和合数分解的程序，需要先调用getPrime()；longlongpow_m(longlonga,longlongn){longlongret=1;longlongtmp=a%M0D;while(n)(if(n&l)ret=(ret*tmp)%MOD;tmp=tmp*tmp%MOD;n>>=1;}returnret;)//计算l+p+pA2+...+pAnlonglongsum(longlongpzlonglongn)(if(p==0)return0;if(n==0)return1;if(n&1)(return((l+pow__m(p,n/2+1))%MOD*sum(p,n/2)%MOD)%MOD;}elsereturn((l+pow_m(p,n/2+1))%MOD*sum(p,n/2-1)+pow_m(p,n/2)%MOD)%MOD;}//返回AAB的约数之和%MODlonglongsolve(longlongA,longlongB)(getFactors(A);longlongans=1;for(inti=0;i

52线性筛法求解积性函数(莫比乌斯函数)constintMAXN=1000000;boolcheck[MAXN+10];intprime[MAXN+10];intmu[MAXN+10];voidMobius(){memset(check,false,sizeof(check));mu[1]=1;inttot=0;for(inti=2;i<=MAXN;i++)if(!check[i])prime[tot++]=i;mu[i]=-1;)for(intj=0;jMAXN)break;check[i*prime[j]]=true;if(i%prime[j]==0)mu[i*prime[j]]=0;break;else

53mu[i*prime[j]]=-mu[i];))})例题:BZOJ2301对于给出的n个询问，每次求有多少个数对(x,y),满足a〈xWb,cWyWd,且gcd(x,y)=k,gcd(x,y)函数为x和y的最大公约数。1MAXN)break;check[i*prime[j]]=true;if(i%prime[j]==0)mu[i*prime[j]]=0;break;}elsemu[i*prime[j]]=-mu[i];)intsum[MAXN+10];//找,[l,m]内互质的数的对数longlongsolve(intn,intm)(longlongans=0;if(n>m)swap(nzm);=la+1)sum[i-l])*(n/i)*(m/i);for(inti=1,la=0;i<=n;(la=min(n/(n/i),m/(m/i));ans+=(longlong)(sum[la]returnans;intmain()(Mobius();sum[0]=0;for(inti=l;i<=MAXN;i++)sum[i]=sum[i-l]+mu[i];inta,b,c,d,k;intT;scanf(n%d"z&T);while(T——)(scan£(”％d%d%d%d%d",&b,&c,&d,&k);

54longlongans=solve(b/k,d/k)-solve((a-1)/k,d/k)-solve(b/k,(c-1)/k)+solve((a-1)/k,(c-l)/k);printf(n%lld

55"tans);)return0;)14、Baby-StepGiant-Step(POJ2417,3243)//baby_stepgiant_step//aAx=b(modn)n是素数和不是素数都可以//求解上式0<=xn)break;}return-1;15、自适应simpson积分doublesimpson(doublea,doubleb)doublec=a+(b-a)/2;return(F(a)+4*F(c)+F(b))*(b-a)/6;)doubleasr(doublea,doublebzdoubleepsxdoubleA)(doublec=a+(b-a)/2;doubleL=simpson(arc),R=simpson(c,b);if(fabs(L+R-A)<=15*eps)returnL+R+(L+R-A)/15.0;returnasr(a,c,eps/2,L)+asr(cxb,eps/2zR);)doubleasr(doublea,doublebzdoubleeps)(returnasr(a,b,eps,simpson(a,b));相关公式1、欧拉定理对于互质的整数a和n,有邰⑺三1(modn)费马定理：a是不能被质数P整除的正整数，有三l(modp)2、Polya定理设G是p个对象的一个置换群，用k种颜色去染这p个对象，若一种染色方案在群G的作

56用下变为一种方案，则这两个方案当作是同一种方案，这样的不同染色方案数为：C(f)为循环节，目表示群的置换方法数。对于n个位置的手镯，有n种旋转置换和n种翻转置换对于旋转置换：C(。)=gcd(",/),i表示旋转i颗宝石以后。i=0时gcd(n,0)=n对于翻转置换：如果n为偶数：则有n/2个置换C(乃1,有n/2个置换C(f)=1+122如果n为奇数：则有n个置换C(r)=J+123、欧拉函数向")陶)积性函数，对于一个质数p和正整数A,有(p(pk)=pk_pk-i=(P—Dp"=P"(1――)f)=n当〃>1时，L..Z7中与〃互质的整数和为2

57数据结构1、划分树/**划分树(查询区间第k大)*/constintMAXN=100010;inttree[20][MAXN];//表示每层每个位置的值intsorted[MAXN];//已经排序好的数inttoleft[20][MAXN];//toleft[p][i]表示第i层从1)1分入左边voidbuild(int1,intr,intdep){if(1==r)return;intmid=(1+r)>>1;intsame=mid-1+1;//表示等于中间值而且被分入左边的个数for(inti=1;i<=r;i++)//注意是1,不是oneif(tree[dep][i]0)(tree[dep+l][lpos++]=tree[dep][i];same—;}elsetree[dep+l][rpos++]=tree[dep][i];toleft[dep][i]=toleft[dep][1-1]+Ipos-1;)build(1,mid,dep+1);build(mid+1,r,dep+1);)//查询区间第k大的数，[L,R]是大区间，[1,门是要查询的小区间intquery(intLrintR,int1,intr,intdep,intk){if(1==r)returntree[dep][1];intmid=(L+R)>>1;intent=toleft[dep][r]-toleft[dep][1-1];if(ent>=k){intnewl=L+toleft[dep][1-1]-toleft[dep][L-l];intnewr=newl+ent-1;returnquery(L,mid,newl,newr,dep+1,k);)else{intnewr=r+toleft[dep][R]-toleft[dep][r];intnewl=newr-(r-l-cnt);returnquery(mid+1,R,newl,newr,dep+l,k-cnt);))intmain()

58(intn,m;while(scanf(M%d%dM,&n,&m)==2)memset(tree,0,sizeof(tree));for(inti=1;i<=n;i++)(scanf(n%dM,&tree[0][i]);sorted[i]=tree[0][i];)sort(sorted+1,sorted+n+1);build(I,n,0);ints,t,k;while(m—)(scanf(,,%d%d%dH,&sz&tz&k);printf("%d

59n,query))return0;2、RMQ2.1—维求最大值，数组下标从1开始。求最小值，或者最大最小值下标，或者数组从0开始对应修改即可。constintMAXN=50010;intdp[MAXN][20];intmm[MAXN];//初始化RMQ,b数组下标从1开始，从0开始简单修改voidinitRMQ(intn,intb[])(mm[0]=-1;for(inti=1;i<=n;i++){mm[i]=((i&(i-1))==0)?mm[i-l]+1:mm[i-l];dp[i][0]=b[i];)for(intj=1;j<=mm[n];j++)for(inti=1;i+(1<

60intmain(){//在外面对咽数组进行初始化mm[0]=-1;for(inti=1;i<=305;i++)mm[i]=((i&(i-1))==0)?mm[i-l]+1;intn,m;intQ;intrl,cl,r2,c2;while(scanf(M%d%dM,&n,&m)==2){for(inti=1;i<=n;i++)for(intj=1;j<=m;j++)scanf(M%d"z&val[i][j]);initRMQ(n,m);scanf(M%d",&Q);while(Q——)(scanf(n%d%d%d%dw,&rl,&cl,&r2,&c2);if(rl>r2)swap(rl,r2);if(cl>c2)swap(cl,c2);inttmp=rmq(rl/cl/r2rc2);printf(n%dn,tmp);if(tmp==val[rl][cl]||tmp==val[rl][c2]||tmp==val(r2](cl]||tmp==val[r2][c2])printf("yes

61");elseprintf(*'no

62n);)return0;3、树链剖分3.1点权基于点权，查询单点值，修改路径的上的点权(HDU3966树链剖分+树状数组)constintMAXN=50010;structEdge(intto,next;}edge[MAXN*2];inthead[MAXN],tot;inttop[MAXN];//top[v]表示v所住的电链的顶端付点intfa[MAXN];//父亲节点intdeep[MAXN];//i¥ffiintnum[MAXN];//num[v]表示以v为根的子树的节点数intp[MAXN];//p[v]亲示v对应的位置intfp[MAXN];//^£_和p数组相反intson[MAXN];//重儿子intpos;voidinit()tot=0;memset(head,-1,sizeof(head));pos=1;//使用树状数组，编号从头1开始memset(son,-1,sizeof(son));}voidaddedge(intu,intv)|edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;)voiddfsl(intu,intpre,intd){deep[u]=d;fa[u]=pre;num[u]=1;for(inti=head[u];i!=-1;i=edge[i].next)(intv=edge[i].to;if(v!=pre)(dfsl(v,u,d+l);num[u]+=num[v];if(son[u]==-1||num[v]>num[son[u]])son[u]=v;)

63})voidgetpos(intu,intsp)(top[u]=sp;p[u]=pos++;fp[p[u]]=u;if(son[u]==-1)return;getpos(son[u],sp);for(inti=head[u];i!=-1;i=edge[i].next)(intv=edge[i].to;if(v!=son[u]&&v!=fa[u])getpos(v,v);〃树状数组intlowbit(intx){returnx&(-x);)intc[MAXN];intn;intsum(inti){ints=0;while(i>0)(s+=c[i];i-=lowbit(i);}returns;}voidadd(inti,intval)|while(i<=n)(c[i]+=val;i+=lowbit(i);}voidChange(intu,intv,intval)//u->v的路径上点的值改变{intfl=top[u],f2=top[v];inttmp=0;while(fl!=f2)(if(deep[fl]deep[v])swap(uzv);add(p[u],val);add(p[v]+lz-val);)inta[MAXN];intmain(){intM,P;while(scanf("%d%d%dMr&nr&M,&P)==3)(intu,v;intC1,C2,K;charop[10];

64init();for(inti=1;i<=n;i++){scanf(M%dMz&a[i]);}while(M——){scanf(**%d%dn,&u,&v);addedge(uzv);addedge(v,u);)dfsl(1,0,0);getpos(1/1);memset(c,0,sizeof(c));for(inti=l;i<=n;i++){add(p[i],a[i]);add(p[i]+lr-a[i]);)while(P——){scanf(op);if(op[0]=='Qf)scanf(M%d",&u);printf("%d

65"，sum(p[u]));)else(scanf(M%d%d%d"z&C1,&C2,&K);if(op[0]==*D1)K=-K;Change(Cl,C2,K);}return0;）3.2边权基于边权，修改单条边权，查询路径边权最大值（SPOJQTREE树链剖分+线段树）constintMAXN=10010;structEdgeintto,next;ledge[MAXN*2];inthead[MAXN],tot;inttop[MAXN];//top[v]表示v所。i0点intfa[MAXN];〃父亲节点intdeep[MAXN];//；笨度intnum[MAXN];//虫生[v]表示以v为根的子树的节点数intp[MAXN];//p[v]表示v与其父。工住线段树中的位置intfp[MAXN];//和p数组相反intson[MAXN];//重儿子intpos;voidinit()(tot=0;memset(head,-1,sizeof(head));pos=0;memset(son,-1,sizeof(son));)voidaddedge(intu,intv){edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;}voiddfsl(intu,intpre,intd)/第一遍dfs求出fa,deep,num,son{deep[u]=d;fa[u]=pre;num[u]=1;

66for(inti=head[u];i!=-1;i=edge[i].next)(intv=edge[i].to;if(v!=pre){dfsl(v,u,d+1);num[u]+=num[v];if(son[u]==-1||num[v]>num[son[u]])son[u]=v;)})voidgetpos(intu,intsp)//第二遍建且求出top和p{top[u]=sp;p[u]=pos++;fp[p[u]]=u;if(son[u]==-1)return;getpos(son[u],sp);for(inti=head[u];i!=-1;i=edge[i].next)(intv=edge[i].to;if(v!=son(u]&&v!=fa[u])getpos(v,v);}}//线段树structNodeint1,r;intMax;)segTree[MAXN*3];voidbuild(intirint1,intr)|segTree[i].1=1;segTree[i].r=r;segTree[i].Max=0;if(1==r)return;intmid=(1+r)/2;build(i«lrlrmid);build((i<mid)returnquery((i<v边的最大值{intfl=top[u],f2=top[v];inttmp=0;while(fl!=f2)(if(deep[f1]deep[v])swap(urv);returnmax(tmp,query(1,p[son[u]],p[v]));)inte[MAXN][3];intmain()//freopen("in.txt","r"，stdin);//freopen("out.txt"，"w",stdout);intT;intn;scanf(M%dnz&T);while(T-)(init();scanf("％d”,&n);for(inti=0;ideep[e[i][1]])swap(e[i][0]ze[i][1]);update(l,p[e(i][l]],e[i][2]);)charop[10];

67intu,v;while(scanf(*•%s"zop)==1){if(op[0]=='D*)break;scanf("%d%dn,&u,&v);if(op[0]=='Qf)printf(M%d

68n,find(u,v))〃/查询u->v路径上边权的最大值elseupdate(l,p[e[uT]//修改第u条边的长度为v)}return0;4、伸展树(splaytree)题目：维修数列。经典题，插入、删除、修改、翻转、求和、求和最大的子序列#defineKey_valuech[ch[root][1]][0]constintMAXN=500010;constintINF=0x3f3f3f3f;intpre[MAXN],ch[MAXN][2],key[MAXN]zsize[MAXN];introot,totl;intsum[MAXN],rev[MAXN],same[MAXN];intlx[MAXN]rrx[MAXN],mx[MAXN];ints[MAXN],tot2;〃内存池和容量inta[MAXN];intn,q;//debug部分voidTreavel(intx)(if(x)(Treavel(ch[x][0]);printf(”结点：%2d:左儿子%2d右儿子%2d父结点%2dsize=%2d

69w,xrch[x][0],ch[x][1],pre[x],size[x]);Treavel(ch[x][1]);voiddebug(){printf(**root:%d

70”,root);Treavel(root);)//以上是debugg|J5>**************************************voidNewNode(int&r,intfather,intk){if(tot2)r=s;//取的时候是17的时优，ot2elser=++totl;pre[r]=father;ch[r][0]=ch[r][1]=0;key[r]=k;sum[r]=k;rev[r]=same[r]=0;lx[r]=rx[r]=mx[r]=k;

71size[r]=1;)voidUpdate_Rev(intr)(if(!r)return;swap(ch[r][0]rch[r][1]);swap(lx[r],rx[r]);rev[r]人=1;)voidUpdate_Same(intr,intv){if(!r)return;key[r]=v;sum[r]=v*size[r];lx[r]=rx[r]=mx[r]=max(v,v*size[r]);same[r]=1;)voidpush__up(intr){intIson=ch[r][0]/rson=ch[r][1];size[r]=size[Ison]+size[rson]+1;sum[r]=sum[Ison]+sum[rson]+key[r];lx[r]=max(lx[Ison],sum[Ison]+key[r]+max(0,lx[rson]));rx[r]=max(rx[rson],sum[rson]+key[r]+max(0,rx[Ison]));mx[r]=max(0,rx[Ison])+key[r]+max(0,lx[rson]);mx[r]=max(mx[r],max(mx[Ison],mx[rson]));)voidpush_down(intr)if(same[r])(Update_Same(ch[r][0],key[r]);Update_Same(ch[r][1],key[r]);same[r]=0;|if(rev[r])(Update_Rev(ch[r][0]);Update_Rev(ch[r][1]);rev[r]=0;})voidBuild(int&x,int1,intr,intfather){if(1>r)return;intmid=(1+r)/2;NewNode(x,father,a[mid]);Build(ch[x]Build(ch[x][1],mid+1,r,x);push_up(x);)voidInit(){root=totl=tot2=0;ch[root][0]=ch[root][1]=size[root]=pre[root]=0;same[root]=rev[root]=sum[root]=key[root]=0;lx[root]=rx[root]=mx[root]=-INF;NewNode(root,0z-1);NewNode(ch[root][1],root,-1);for(inti=0;i

72intkind=ch[pre[y]][0]==y;if(ch[y][kind]==r){Rotate(r,!kind);Rotate(rzkind);}else(Rotate(y,kind);Rotate(r,kind);))}push_up(r);if(goal==0)root=r;)intGet_kth(intr,intk){push_down(r);intt=size[ch[r][0]]+1;if(t==k)returnr;if(t>k)returnGet_kth(ch[r][0]rk);elsereturnGet_kth(ch[r][1],k-t);)//在第pos个数后面插入tot个数voidInsert(intposrinttot){for(inti=0;i

73push_up(ch[root][1]);push_up(root);)//将第pos个数开始的连续tot个数进行反转voidReverse(intpos,inttot){Splay(Get_kth(root,pos),0);Splay(Get_kth(root,pos+tot+1),root);Update_Rev(Key_value);push_up(ch[root][1]);push_up(root);)//得到第pos个数开始的tot个数的和intGet_Sum(intpos,inttot)Splay(Get_kth(root,pos),0);Splay(Get_kth(root,pos+tot+1),root);returnsum[Key_value];)//得到第pos个数开始的tot个数中最大的子段和intGet_MaxSum(intpos,inttot){Splay(Get_kth(root,pos),0);Splay(Get_kth(root,pos+tot+1),root);returnmx[Key_value];)voidInOrder(intr)(if(!r)return;push_down(r);InOrder(ch[r][0]);printf(M%dnzkey[r]);InOrder(ch[r][1]);}intmain()(//freopen("in.txt","r",stdin);//freopen("out.txtn,nwn,stdout);while(scanf(H%d%cinz&n,&q)==2)Init();charop[20];intx,y,z;while(q--)(scanf(**%s*',op);if(strcmp(op,nINSERT")==0){scanf(*'%d%cin,&x,&y);Insert(x,y);}elseif(strcmp(op,MDELETEM)==0){scanf(*'%d%dM,&x,&y);Delete(x,y);)elseif(strcmp(opzMMAKE-SAMEn)==0)scanf("%d%d%dn,&x,&y,&z);Make_Same(x,y,z);}elseif(strcmp(op,MREVERSEM)==0){scanf(M%d%dM,&x,&y);Reverse(x,y);)elseif(strcmp(opzMGET-SUMM)==0)

74scanf(M%d%dM,&x,&y);printf("%d

75”,Get_Sum(xry));)elseif(strcmp(op,MMAX-SUMM)==0)printf(n%d

76n,Get_MaxSum(1,size[root]-2));)}return0;5、动态树5.1HDU4010(切割、合并子树，路径上所有点的点权增加一个值，查询路径上点权的最大值)//动态维护一组森林，要求支持一下操作：//link(a,b):如果a,b不在同一颗子树中，则通过在a,b之间连边的方式，连接这两颗子树//cut(a,b):如果a,b在同一颗子树中，且a!=b，则将a视为这颗子树的根以后，切断b与其父亲结点的连接//ADD(a,b,w):如果a,b在同一颗子树中，则将a,b之间路径上所有点的点权增加w//query(a,b):如果a,b在同•颗子树中，返回a,b之间路径上点权的最大值constintMAXN=300010;intch[MAXN][2],pre[MAXN],key[MAXN];intadd[MAXN],rev[MAXN]rMax[MAXN];boolrt[MAXN];voidUpdate_Add(intr,intd)(i£(!r)return;key[r]+=d;add[r]+=d;Max[r]+=d;}voidUpdate_Rev(intr)(if(!r)return;swap(ch[r][0]rch[r][1]);rev[r]A=1;)voidpush_down(intr)(if

77elseRotate(r),Rotate(r);}push_up(r);}intAccess(intx)inty=0;for(;x;x=pre[y=x])(Splay(x);rt[ch[x][1]]=true,rt[ch[x][1]=y]=false;push_up(x);}returny;)//判断是否是同根(真实的树，非splay)booljudge(intu,intv){while(pre[u])u=pre[u];while(pre[v])v=pre[v];returnu==v;}//使r成为它所在的树的根voidmroot(intr)(Access(r);Splay(r);Update_Rev(r);)//调用后u是原来□和v的lea,v和ch[u][1]分别存着lea的2个儿子//(原来u和v所在的2颗子树)voidlea(int&u,int&v)(Access(v),v=0;while(u){Splay(u);if(!pre[u])return;rt[ch[u][1]]=true;rt[ch[u][1]=v]=false;push_up(u);u=pre[v=u];}}voidlink(intu,intv){if(judge(u,v))(puts("-1");return;}mroot(u);pre[u]=v;)//使u成为u所在树的根，并且v和它父亲的边断开

78voidcut(intu,intv)if(u==v||!judge(urv))(puts;return;)mroot(u);Splay(v);pre[ch[v][0]]=pre[v];pre[v]=0;rt[ch[v][0]]=true;ch[v][0]=0;push_up(v);}voidADD(intu,intv,intw)(if(!judge(u,v))(puts(**-1**);return;}lea(u,v);Update_Add(ch[u][1],w);Update_Add(vrw);key[u]+=w;push_up(u);)voidquery(intu,intv)if(!judge(uzv))(puts("-1*');return;}lea(u,v);printf("%d

79H,max(max(Max[v],Max[ch[u][1]])zkey[u]));)structEdgeintto,next;}edge[MAXN*2];inthead[MAXN]ttot;voidaddedge(intu,intv)edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;)voiddfs(intu)(for(inti=head[u];i!=-1;i=edge[i].next)(intv=edge[i].to;if(pre[v]!=0)continue;pre[v]=u;dfs(v);intmain()//freopen("in.txt'Snrn,stdin);

80//freopen(°out.txt"，"w",stdout);intn,q,u,v;while(scanf(**%dM,&n)==1)(tot=0;for(inti=0;i<=n;i++)(head[i]=-1;pre[i]=0;ch[i][0]=ch[i][1]=0;rev[i]=0;add[i]=0;rt[i]=true;)Max[0]=-2000000000;for(inti=1;i

81");return0;

826、主席树6.1查询区间有多少个不同的数(SPOJDQUERY)/**给出一个序列，查询区间内有多少个不相同的数constintMAXN=30010;constintM=MAXN*100;intn,q,tot;inta[MAXN];intT[MAXN],Ison[M],rson[M],c[M];intbuild(int1,intr)introot=tot++;c[root]=0;if(1!=r)(intmid=(1+r)>>1;Ison[root]=build(lfmid);rson[root]=build(mid+1,r);)returnroot;)intupdate(introot,intpos,intval)(intnewroot=tot++/tmp=newroot;c[newroot]=c[root]+val;int1=1,r=n;while(1>1;if(pos<=mid){Ison[newroot]=tot++;rson[newroot]=rson[root];newroot=Ison[newroot];root=Ison[root];r=mid;elserson[newroot]=tot++;Ison[newroot]=Ison[root];newroot=rson[newroot];root=rson[root];1=mid+1;)c[newroot]=c[root]+val;returntmp;intquery(introot,intpos){intret=0;int1=1,r=n;while(pos>1;if(pos<=mid)r=mid;root=Ison[root];)else{ret+=c[Ison[root]];root=rson[root];1=mid+1;)

83returnret+c[root];)intmain(){//freopen("in.txt",wr",stdin);//—reopen(nout.txt","w”，stdout);while(scanf(M%dn,&n)==1)(tot=0;for(inti=l;i<=n;i++)scanf("%d0,&a[i]);T[n+1]=build(lzn);mapmp;for(inti=n;i>=1;i)(if(mp.find(a[i])==mp.end()){T[i]=update(T[i+l],izl);)else{inttmp=update(T[i+1],mp[a[i]],-1);T[i]=update(tmp,i,1);)mp[a[i]]=i;}scanf(,&q);while(q——)int1,r;scanf("%d%dn,&1,&r);printf(n%d

84n,query(T[1]zr));)}return0;6.2静态区间第k大(POJ2104)constintMAXN=100010;constintM=MAXN*30;intn,qfm,tot;inta[MAXN],t[MAXN];intT[MAXN],Ison[M],rson[M],c[M];voidInit_hash(){for(inti=1;i<=n;i++)t[i]=a[i];sort(t+lxt+l+n);m=unique(t+lzt+l+n)-t-l;)intbuild(int1,intr){introot=tot++;c[root]=0;if(1!=r)(intmid=(1+r)>>1;Ison[root]=build(lzmid);rson[root]=build(mid+lzr);}returnroot;)inthash(intx){returnlower_bound(t+1,t+l+m,x)-t;)intupdate(introot,intpos,intval)

85intnewroot=tot++,tmp=newroot;c[newroot]=c[root]+val;int1=1,r=m;while(1>1;if(pos<=mid)Ison[newroot]=tot++;rson[newroot]=rson[root];newroot=Ison[newroot];root=Ison[root];r=mid;)elserson[newroot]=tot++;Ison[newroot]=Ison[root];newroot=rson[newroot];root=rson[root];1=mid+1;)c[newroot]=c[root]+val;returntmp;}intquery(intleft_rootzintright_root,intk){int1=1,r=m;while(1>1;if(c[Ison[left_root]]-c[Ison[right_root]]>=k)(r=mid;left_root=Ison[left_root];right_root=Ison[right_root];)else(1=mid+1;k-=c[Ison[left_root]]-c[Ison[right_root]];left_root=rson[left_root];right_root=rson[right_root];)}return1;)intmain(){//freopen("in.txt"，"r",stdin);//freopen("out.txt",**wn,stdout);while(scanf(M%d%d,*,&n,&q)==2)(tot=0;for(inti=1;i<=n;i++)scanf(M%dMr&a[i]);Init_hash();T[n+1]=build(lzm);for(inti=n;i;i——)(intpos=hash(a[i]);T[i]=update(T[i+l],posz1);)while(q——)(int1,r,k;scanf(M%d%d%dMr&1,&rz&k);printf("%d

86"，t[query(T[1],T[r+l]zk)]);return0;)6.3树上路径点权第k大(SPOJCOT)LCA+主席树//主席树部分*****************8constintMAXN=200010;constintM=MAXN*40;intTOT;inta[MAXN],t[MAXN];intT[MAXN],Ison[M],rson[M],c[M];voidInit_hash()for(inti=1;i<=n;i++)t[i]=a[i];sort(t+lrt+l+n);m=unique(t+l,t+n+l)-t-1;intbuild(int1,intr)(introot=TOT++;c[root]=0;if(1!=r)(intmid=(1+r)>>1;Ison[root]=build(lz

87mid);rson[root]=build(mid+1,r);|returnroot;}inthash(intx)(returnlower_bound(t+1,t+l+mrx)-t;)intupdate(introot,intpos,intval){intnewroot=TOT++,tmp=newroot;c[newroot]=c[root]+val;int1=1,r=m;while(1>1;if(pos<=mid)(Ison[newroot]=TOT++;rson[newroot]=rson[root];newroot=Ison[newroot];root=Ison[root];r=mid;)else{rson[newroot]=TOT++；Ison[newroot]=Ison[root];newroot=rson[newroot];root=rson[root];1=mid+1;)c[newroot]=c[root]+val;}returntmp;}intquery(intleft_root,intright_rootzintLCA,intk)|intlca_root=T[LCA];intpos=hash(a[LCA]);int1=1,r=m;while(1>1;inttmp=c[Ison[left_root]]+c[Ison[right_root]]-2*c[Ison[lca_root]]+(pos>=1&&pos<=mid);if(tmp>=k){left_root=Ison[left__root];right_root=Ison[right_root];lca_root=Ison[lca_root];r=mid;else{k-=tmp;left_root=rson[left_root];right_root=rson[right_root];lca_root=rson[lca_root];1=mid+1;))return1;)//LCA部分intrmq[2*MAXN];//rmq数组,了structST{intmm[2*MAXN];intdp[2*MAXN][20];//最小值对应的卜标voidinit(intn)(mm[0]=-1;for(inti=l;i<=n;i++){mm[i]=((i&(i-1))==0)+1;dp[i][0]=i;)for(intj=1;j<=mm[n];j++)for(inti=1;i+(1<b)swap(a,b);intk=mm[b-a+1];returnrmq[dp[a][k]]<=rmq[dp[b-(l«k)+l][k]]?dp[a][k]:dp[b-(l«k)+1][k];}}；//边的结构体定义structEdgeintto,next;)；Edgeedge[MAXN*2];inttot,head[MAXN];intF[MAXN*2];//欧拉序列，就是dfs遍历的顺序,长--1,下标从1开始intP[MAXN];//P[i]表示点i在F中第一次出现的位置intent;STst;voidinit()(tot=0;memset(head,-1,sizeof(head));)voidaddedge(intu,intv)//加边，无向边需要加两次edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++；)voiddfs(intu,intpre,intdep)F[++cnt]=u;rmq[ent]=dep;P[u]=ent;for(inti=head[u];i!=-1;i=edge[i].next)(intv=edge[i].to;if(v==pre)continue;dfs(v,u,dep+l);F[++cnt]=u;rmq[ent]=dep;))voidLCA_init(introot,intnode_num)//查询LCA前的初始化{

88ent=0;dfs(root,rootr0);st,init(2*node_num-l);)intquery_lca(intu,intv)//查询u,v的lea编号{returnF[st.query(P[u],P[v])];)voiddfs_build(intu,intpre){intpos=hash(a[u]);T[u]=update(T[pre],pos,1);for(inti=head[u];i!=-1;i=edge[i].next)(intv=edge[i].to;if(v==pre)continue;dfs_build(v,u);})intmain(){//freopen("in.txt",nrn,stdin);//freopen("out.txt",nwn,stdout);while(scanf(n%d%dM,&n,&q)==2)(for(inti=1;i<=n;i++)scanf&a[i]);Init_hash();init();TOT=0;intu,v;for(inti=1;i

89n,t[query(T[u],T[v],query.,lea(u,v)rk)]);)return0;)return0;)6.4动态第k大(ZOJ2112)树状数组套主席树constintMAXN=60010;constintM=2500010;intn,q,tot;inta[MAXN],t[MAXN];intT[MAXN]tIson[M],rson[M],c[M];intS[MAXN];structQuery{intkind;intrzk;}query[10010];voidInit_hash(intk){sort(t,t+k);m=unique(trt+k)-t;}inthash(intx)

90returnlower_bound(trt+m,x)-t;}intbuild(int1,intr){introot=tot++;c[root]=0;if(1!=r)(intmid=(1+r)/2;Ison[root]=build(1,mid);rson[root]=build(mid+l,r);returnroot;)intInsert(introot,intpos,intval)intnewroot=tot++ztmp=newroot;int1=0,r=m-1;c[newroot]=c[root]+val;while(1>1;if(pos<=mid)Ison[newroot]=tot++;rson[newroot]=rson[root];newroot=Ison[newroot];root=Ison[root];r=mid;)elserson[newroot]=tot++;Ison[newroot]=Ison[root];newroot=rson[newroot];root=rson[root];1=mid+1;)c[newroot]=c[root]+val;}returntmp;intlowbit(intx){returnx&(-x);}intuse[MAXN];voidadd(intx,intposfintval)(while(x<=n)(S[x]=Insert(S[x],pos,val);x+=lowbit(x);}intsum(intx)intret=0;while(x>0)(ret+=c[Ison[use[x]]];x-=lowbit(x);}returnret;}intQuery(intleft,intright,intk)(intleft_root=T[left-1];intright_root=T[right];int1=0,r=m-1;for(inti=left-1;i;i-=lowbit(i))use[i]=S[i];for(inti=right;i;i-=lowbit(i))use[i]=S[i];while(1=k){r=mid;for(inti=left-1;i;i-=lowbit(i))use[i]=Ison[use[i]];for(inti=right;i;i-=lowbit(i))use[i]=Ison[use[i]];left_root=Ison[left_root];right_root=Ison[right_root];)else(2=mid+1;k-=tmp;for(inti=left-1;i;i-=lowbit(i))use[i]=rson[use[i]];

91for(inti=right;i;i-=lowbit(i))use[i]=rson[use[i]];left_root=rson[left_root];right_root=rson[right_root];)}return1;)voidModify(intx,intp,intd)(while(x<=n)(S[x]=Insert(S[x]rpzd);x+=lowbit(x);intmain()(//freopen("in.txt'*,nr*\stdin);//freopen("out.txtn,Mwn,stdout);intTease;scanf("%d"z&Tcase);while(Tease——)(scanf("%d%d"z&nz&q);tot=0;m=0;for(inti=1;i<=n;i++)scanf(n%dMr&a[i]);t[m++]=a[i];)charop[10];for(inti=0;i

92",t[Query(query[i].1,query[i].r,query[i].k)]);else(Modify(query[i].1,hash(a[query[i].1]),-1);Modify(query[i]・1,hash(query[i].r),1);a[query[i].1]=query[i].r;)}}return0;

937、TreapZOJ3765longlonggcd(longlonga,longlongb){if(b==0)returna;elsereturngcd(b,a%b);}constintMAXN=300010;intnum[MAXN],st[MAXN];structTreap(inttotl;ints[MAXN],tot2;//内存池和容鼠intch[MAXN][2];intkey[MAXN]rsize[MAXN];intsumO[MAXN],suml[MAXN];intstatus[MAXN];voidInit()(tot1=tot2=0;size[0]=0;ch[0][0]=ch[0][1]=0;sumO[0]=suml[0]=0;}boolrandom(doublep)(return(double)rand()/RAND_MAX

94}voidpush_up(intr)(intIson=ch[r][0],rson=ch[r][1];size[r]=size[Ison]+size[rson]+1;sumO[r]=gcd(sumO[Ison],sumO[rson]);suml[r]=gcd(suml[Ison],suml[rson]);if(status[r]==0)sumO[r]=gcd(sumO[r],key[r]);elsesuml[r]=gcd(suml[r],key[r]);}voidmerge(int&p,intx,inty)(if(!x||!y)P二x|y;elseif(random((double)size[x]/(size[x]+size[y])))(merge(ch[x][1]rch[x][1]ry);push_up(p=x);else{merge(ch[y][0]rxrch[y][0]);push_up(p=y);}}voidsplit(intp,int&x,int&y,intk)(if(!k)(x=0;y=p;return;)if(size[ch[p][0]]>=k)(y=p;split(ch[p][0]Xx,ch[y][0]zk);push_up(y);}else{x=p;split(ch[p][1]rch[x][1]ry,k-size[ch[p][0]]-1);push_up(x);))

95voidbuild(int&p,int1,intr)(if(1>r)return;intmid=(1+r)/2;p=newnode(num[mid],st[mid]);build(ch[p][0],lzmid-l);build(ch[p][1],mid+lzr);push_up(p);}voiddebug(introot)(if(root==0)return;printf("%d左儿子：%d右儿子：%dsize=%dkey=%d

96"rroot,ch[root][0],ch[root][1],size[root],key[root]);debug(ch[root][0]);debug(ch[root][1]);TreapT;charop[10];intmain()(//freopen(win.txt"r"r**,stdin);//freopen("out.txt",nwn,stdout);intnfq;while(scanf(n%d%dM,&n,&q)==2)(introot=0;T.Init();for(inti=1;i<=n;i++)scanf(n%d%dn,&num[i],&st[i]);T.build(root,1,n);while(q-){scanf(n%s",op);if(op[0]=='Qf)(int1,r,s;scanf(&1,&r,&s);intx,y,z;T.split(root,x,z,r);T.split(x,x,y,1-1);if(s==0)printf("%d

97'\T.sumO[y]==0?-1:T.sumO[y]);elseprintf(n%d

98MzT.suml[y]==0?-l:T.suml[y]);T.merge(x,x,y);

99T.merge(root,x,z);}elseif(op[0]==T){intv,s,loc;scanf(**%d%d%dn,&locr&v,&s);intxzy;T,split(root,x,v，loc);T.merge(xzx,T.newnode(vrs));T.merge(root,x,y);)elseif(op[0]==1D1)intloc;

100)}return}scanf(n%d",&loc);intx,y,z;T.split(root,xzz,loc);T.split(x,x,y,loc-1);T.del(y);T.merge(root,x,z);)elseif(op[0]==1R*){intloc;scanf(,,%dn/&loc);intx,y,z;T.split(root,x,z,loc);T.split(x,x,y,loc-1);T.status[y]=1-T.status[y];T.push_up(y);T.merge(x,xry);T.merge(root,x,z);)else(intloc,v;scanf("%d%dM,Sloe,&v);intx,y,z;T.split(root,x,z,loc);T.split(x,x,y,loc-1);T.key[y]=v;T.push_up(y);T.merge(x,x,y);T.merge(root,x,z);

101图论1、最短路1.1Dijkstra单源最短路，邻接矩阵形式权值必须是非负/**单源最短路径，Dijkstra算法，邻接矩阵形式，复杂度为0(22)*求出源beg到所有点的最短路径，传入图的顶点数，和邻接矩阵cost[][]*返回各点的最短路径1-口，路径吟口.一[i]记录beg至Ui路径上的父结点,pre[beg]=-1*可更改路径权类型，但是权值必须为非负**/constintMAXN=1010;#definetypecintconsttypec工NF=0x3f3f3f3£;//防I上后而溢出，这个不能太大boolvis[MAXN];intpre[MAXN];voidDijkstra(typeccost[][MAXN]ttypeclowcost[],intnzintbeg){for(inti=0;i

102上海大学ACM模板bykuangbinlowcost[i]=lowcost[k]+cost[k][i];

103pre[i]=k;)1.1Dijkstar算法+堆优化使用优先队列优化，复杂度O(ElogE)/**使用优先队列优化Dijkstra算法*复杂度O(ECogE)*注意对vectorE[MAXN]进行初始化后加边*/constintINF=0x3f3f3f3f;constintMAXN=1000010;structqnode{intv;intc;qnode(int_v=0,int_c=0):v(_v),c(_c){}booloperator<(constqnode&r)const(returnc>r.c;})；structEdge(intv,cost;Edge(int_v=0,int__cost=0):v(_v),cost(_cost){})；vectorE[MAXN];boolvis[MAXN];intdist[MAXN];voidDijkstra(intn,intstart)//点的编号从1开始(memset(vis,false,sizeof(vis));for(inti=l;i<=n;i++)dist[i]=INF;priority_queueque;while(!que.empty())que.pop();dist[start]=0;que.push(qnode(start,0));qnodetmp;while(!que.empty())(tmp=que.top();que.pop();intu=tmp.v;if(vis[u])continue;vis[u]=true;for(inti=0;idist[u]+cost)(dist[v]=dist[u]+cost;que.push(qnode(v,dist[v]));

104)})voidaddedge(intu,intv,intw)(E[u].push_back(Edge(v,w));)1.3单源最短路bellman_ford算法/**单源最短路bellman_ford算法，复杂度O(VE)*可以处理负边权图。*可以判断是否存在负环回路。返回true,当且仅当图中不包含从源点可达的负权网路*vectorE;先E.clear()初始化，然后加入所有边*点的编号从1开始(从。开始简单修改就可以了)*/constintINF=0x3f3f3f3f;constintMAXN=550;intdist[MAXN];structEdge(intv;intcost;Edge(int_u=0,int_v=0,int_cost=0):u(_u),v(_v),cost(_cost){}}；vectorE;boolbellman_ford(intstart,intn)//点的编号从1开始{for(inti=l;i<=n;i++)dist[i]=INF;dist[start]=0;for(inti=l;idist[u]+cost)(dist[v]=dist[u]+cost;flag=true;)}if(!flag)returntrue;//没有负环回路}for(intj=0;jdist[E[j].u]+E[j].cost)returnfalse;//有负?不向路returntrue;//没有负环回路)1.4单源最短路SPFA/★*单源最短路SPFA*时间复杂度O(kE)*这个是队列实现，有时候改成栈实现会更加快，很容易修改*这个复杂度是不定的*/constintMAXN=1010;constintINF=0x3f3f3f3f;structEdge(intv;intcost;Edge(int_v=0,int_cost=0):v(_v),cost(_cost){}}；vectorE[MAXN];voidaddedge(intu,intv,intw){E[u].push-back(Edge(v,w));)boolvis[MAXN];//在队歹U标志intent[MAXN];〃每个点的入队列次数intdist[MAXN];boolSPFA(intstart,intn)memset(vis,false,sizeof(vis));for(inti=l;i<=n;i++)dist[i]=INF;vis[start]=true;dist[start]=0;queueque;while(!que.empty())que.pop();que.push(start);memset(ent,0,sizeof(ent));ent[start]=1;while(!que.empty())(

105intu=que.front();que.pop();vis[u]=false;for(inti=0;idist[u]+E[u][i].cost)(dist[v]=dist[u]+E[u][i].cost;if(!vis[v])(vis[v]=true;que.push(v);if(++cnt[v]>n)returnfalse;〃*[i]为入队列次数，用来判定是否存在负环回路)))}returntrue;2、最小生成树2.1Prim算法/**Prim求MST*耗费矩阵cost口口，标号从0开始，。〜n-l*返1口1最小生成树的权值，返1口1-1表示原图不连通*/constintINF=0x3f3f3f3f;constintMAXN=110;boolvis[MAXN];intlowc[MAXN];intPrim(intcost[][MAXN],intn)//点是。〜nT{intans=0;memset(vis,false,sizeof(vis));vis[0]=true;for(inti=l;ilowc[j]){minc=lowc[j];P=j；)if(minc==INF)returnT;//原图不连通ans+=minc;vis[p]=true;for(intj=0;jcost[p][j])lowc[j]=cost[p][j];)returnans;}2.2Kruskal算法/**Kruskal算法求MST*/constintMAXN=110;//破大点数constintMAXM=10000;//最大边数intF[MAXN];〃并查集《用structEdge{intu,vzw;

106)“96[1^^1];//存储边的inttol;〃边数,加边前W.voidaddedge(intu,intv,intw)edge[tol],u=u;edge[tol].v=v;edge[tol++].w=w;}boolcmp(Edgea,Edgeb){//排序函数，讲边按照权值从小到大排序returna.wlowc[j])(minc=lowc[j];P=j；)if(minc==INF)return-1;ans+=minc;vis[p]=true;used[p][pre[p]]=used[pre[p]][p]=true;for(intj=0;jcost[p][j])(lowc[j]=cost[p][j];pre[j]=p;)))returnans;)

1074、有向图的强连通分量4.1Tarjan/**Tarjan算法*复杂度O(N+M)*/constintMAXN=20010;//点数constintMAXM=50010;//边数structEdge{intto,next;}edge[MAXM];inthead[MAXN],tot;intLow[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1-sccintIndex,top;intsee;//强连通分量的个数boolInstack[MAXN];intnum[MAXN];〃各个强连通分量包含点的<组编号1〜see//num数组不一定需要,结合实际情况voidaddedge(intu,intv){tot++;edge(tot].to=v;edge[tot].next=head[u];head(u]}voidTarjan(intu)(intv;Low[u]=DFN[u]=++Index;Stack[top++]=u;Instack[u]=true;for(inti=head[u];i!=-1;i=edge[i].next)(v=edge[i].to;if(!DFN[v])(Tarjan(v);if(Low[u]>Low[v])Low[u]=Low[v];)elseif(Instack[v]&&Low[u]>DFN[v])Low[u]=DFN[v];}if(Low[u]==DFN[u])(SCC++；dov=Stack[—top];Instack[v]=false;Belong[v]=see;num[see]++;)while{v!=u);)}voidsolve(intN){memset(DFN,0,sizeof(DFN));

108memset(Instack,false,sizeof(Instack));memset(num,0,sizeof(num));Index=see=top=0;for(inti=l;i<=N;i++)if(!DFN[i])Tarjan(i);)voidinit(){tot=0;memset(head,-1,sizeof(head));4.1Kosaraju/**Kosaraju算法,复杂度0(N+M)constintMAXN=20010;constintMAXM=50010;structEdge(intto,next;Jedgel[MAXM]redge2[MAXM];//edgel是原图G,edge2是逆图GTintheadl[MAXN],head2[MAXN];boolmarkl[MAXN],mark2[MAXN];inttotlrtot2;intcntl,cnt2;intst[MAXN];//对原佟I进行巨工巨，、时间从小]intBelong[MAXN];//每个点，属，0~cnt2-1)intnum;//中间变连通分的中点的个数intsetsNum[MAXN];〃强连通分量中点的个数，编号0~cnt2-lvoidaddedge(intu,intv)(edgel[totl].to=v;edgel[totl].next=headl[u];headl[u]=totl++;edge2[tot2].to=u;edge2[tot2].next=head2[v];head2[v]=tot2++;)voidDFS1(intu){markl[u]=true;for(inti=headl[u];i!=-1;i=edgel[i].next)if(!markl[edgel[i].to])DFS1(edgel[i].to);st[cntl++]=u;)voidDFS2(intu){mark2[u]=true;num++;Belong[u]=cnt2;for(inti=head2[u];i!=-1;i=edge2[i].next)if(!mark2[edge2[i].to])DFS2(edge2[i].to);}voidsolve(intn)//点的编号从1开始{memset(markl,false,sizeof(markl));memset(mark2xfalse,sizeof(mark2));cntl=cnt2=0;for(inti=l;i<=n;i++)if(!markl[i])DFS1(i);for(inti=cntl-1;i>=0;i)if(!mark2[st[i]])num=0;DFS2(st[i]);setNum[cnt2++]=num;))5、图的割点、桥和双连通分支的基本概念［点连通度与边连通度］在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。一个图的点连通度的定义为，最小割点集合中的顶点数。类似的，如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合.—个图的边连通度的定义为，最小割边集合中的边数。［双连通图、割点与桥］如果一个无向连通图的点连通度大于1.则称该图是点双连通的(pointbiconnected),简称双连通或重连通一个图有割点，当且仅当这个图的点连通度为1,则割点集合的唯一元素被称为割点(cutpoint),又叫关节点(articulationpoint)»如果一个无向连通图的边连通度大于1,则称该图兄边双连通的(edgebiconnected),简称双连通或重连通。一个图有桥，当且仅当这个图的边连通度为1,则割边集合的唯一元素被称为桥(bridge),又叫关节边(articulationedge).可以看出，点双连通与边双连通都可以简称为双连通，它们之间是有着某种联系的，下文中提到的双连通，

109均既可指点双连通，又可指边双连通。［双连通分支］在图G的所有子图G中，如果G'是双连通的，则称G'为双连通子图如果•个双连通子图G它不是任何-个双连通子图的真子集，则G为极大双连通子图双连通分支(biconnectedcomponent),岐重连通分支.就是图的极大双连通子图.特殊的，点双连通分支又叫做块，［求割点与桥］该算法是RTarjan发明的。对图深度优先搜索，定义DFS(u)为u在搜索树(以下简称为树)中被遍历到的次序号。定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点。根据定义，则有：Low(u)=Min{DFS(u)DFS(v)(u,v)为后向边(返祖边)等价于DFS(v)

110v=edge[i].to;if(v==pre)continue;if(!DFN[v])(son++;Tarjan(v,u);if(Low[u]>Low[v])Low[u]=Low[v];//桥//一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)DFN[u])|bridge++;edge[i].cut=true;edge[iAl].cut=true;}//割点//一个顶点u是割点，当且仅当满足(1)或(2)(1)u为树根，且u有多于一个子树.//(2)u不为树根，且满足存在(u,v)为树枝边(或称父子边，//即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v)if(u!=pre&&Low[v]>=DFN[u])//不是树根{cut[u]=true;add_block[u]++;}}elseif(Low[u]>DFN[v])Low[u]=DFN[v];}//树根，分支数大于1if(u==pre&&son>1)cut[u]=true;if(u==pre)add_block.[u]=son-1;Instack[u]=false;top——;}调用：*)UVA796CriticalLinks给出一个无向图，按顺序输出桥voidsolve(intN)memset(DFN,0,sizeof(DFN));memset(Instack,false,sizeof(Instack));memset(add_blockz0,sizeof(add_block));memset(cut,false,sizeof(cut));Index=top=0;bridge=0;for(inti=1;i<=N;i++)if(!DFN[i])Tarjan(i,i);printf(n%dcriticallinks

111wzbridge);vector>ans;for(intu=1;u<=N;u++)for(inti=head[u];i!=-1;i=edge[i].next)if(edge[i].cut&&edge[i].to>u){ans.push__back(make_pair(u,edge[i].to));}sort(ans.begin(),ans.end());//按顺序输出桥for(inti=0;i

112n,ans[i].first-1,ans[i].second-1);printf("

113");}voidinit()|tot=0;memset(head,-1,sizeof(head));}//处理重边mapmapit;inlineboolisHash(intu,intv)

114if(mapit[u*MAXN+v])returntrue;if(mapit[v*MAXN+u])returntrue;mapit[u*MAXN+v]=mapit[v*MAXN+u]=1;returnfalse;intmain()(intn;while(scanf(M%d",&n)==1){init();intu;intk;intv;//mapit.clear();for(inti=1;i<=n;i++)(scanf("%d(%d)n,&u,&k);u++;//这样加边，要保证正边和反边是相邻的，建无向图while(k——){scanf("%d",&v);v++;if(v<=u)continue;//if(isHash(u,v))continue;addedge(u,v);addedge(v,u);}}solve(n);)return0;)*)POJ2117求删除一个点后，图中最多有多少个连通块voidsolve(intN){memset(DFN,0,sizeof(DFN));memset(Instack,0,sizeof(Instack));memset(add__blockz0,sizeof(add_block));memset(cut,false,sizeof(cut));Index=top=0;intent=0;//原来的连通块数for(inti=1;i<=N;i++)if(!DFN[i])(Tarjan(i,i);//找一点调用必须是Tarjan(i,i.)cnt++；}intans=0;for(inti=1;i<=N;i++)ans=max(ans,cnt+add_block[i]);printf(n%d

115*',ans);)voidinit(){tot=0;memset(head,-1,sizeof(head));}intmain()intn,m;intufv;while(scanf("%d%dn,&n,&m)==2){if(n==0&&m==0)break;init();while(m——)(scanf(”％d%d”,&u,&v);u++;v++;addedge(u,v);addedge(v,u);}solve(n);)return0;}7、边双连通分支去掉桥，其余的连通分支就是边双连通分支了。一个有桥的连通图要变成边双连通图的话，把双连通子图收缩为一个点，形成一颗树。需要加的边为(leaf+l)/2(leaf为叶子结点个数)

116POJ3177给定一个连通的无向图G,至少要添加几条边，才能使其变为双连通图。#include#include#include#include#include

117n,(ans+1)/2);)intmain()intn,m;inturv;while(scanf("％d%d",&n,&m)==2){init();while(m--)(scanf("%d%d",&ur&v);addedge(uzv);addedge(vru);}solve(n);)return0;

118)8、点双连通分支对于点双连通分支，实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈，存储当前双连通分支，在搜索图时，每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中。如果遇到某时满足DFS(u)<=Low(v),说明u是一个割点，同时把边从栈顶一个个取出，直到遇到了边(u,v),取出的这些边与其关联的点，组成一个点双连通分支。割点可以属于多个点双连通分支，其余点和每条边只属于且属于一个点双连通分支。POJ2942奇圈，二分图判断的染色法，求点双连通分支/*POJ2942KnightsoftheRoundTable亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突，并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求：1、相互憎恨的两个骑士不能坐在直接相邻的2个位置：2、出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。注意：1、所给出的憎恨关系一定是双向的，不存在单向憎恨关系。2,由于是圆桌会议，则每个出席的骑士身边必定刚好有2个骑士。即每个骑士的座位两边都必定各有一个骑士.3,一个骑士无法开会，就是说至少有3个骑士才可能开会。首先根据给出的互相憎恨的图中得到补图。然后就相当于找出不能形成奇圈的点.利用下面两个定理：(1)如果一个双连通分量内的某些顶点在一个奇圈中(即双连通分量含有奇圈)，那么这个双连通分量的其他顶点也在某个奇圈中；(2)如果一个双连通分量含有奇圈，则他必定不是一个二分图。反过来也成立，这是一个充要条件。所以本题的做法，就是对补图求点双连通分量。然后对于求得的点双连通分量，使用染色法判断是不是二分图，不是：分图，这个双连通分量的点是可以存在的constintMAXN=1010;constintMAXM=2000010;structEdge{intto,next;}edge[MAXM];inthead[MAXN],tot;intLow[MAXN],DFN[MAXN]zStack[MAXN]zBelong[MAXN];intIndex,top;intblock;//.'.'.'JZiiboolInstack[MAXN];boolcan[MAXN];boolok[MAXN];//标记inttmp[MAXN];//暂时不f储双连通分量耳1的点intcc;//tmp的计数intcolor[MAXN];//染色voidaddedge(intu,intv)(edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;}booldfs(intu,intcol)//染色判断二分图

119{color[u]=col;for(inti=head[u];i!=-1;i=edge[i].next){intv=edge[i].to;if(!ok[v])continue;if(color[v]!=-1)(if(color[v]==col)returnfalse;continue;}if(!dfs(vz!col))returnfalse;)returntrue;)voidTarjan(intu,intpre){intv;Low[u]=DFN[u]=++Index;Stack,[top++]=u;Instack[u]=true;for(inti=head[u];i!=-1;i=edge[i].next)v=edge[i].to;if(v==pre)continue;if(!DFN[v])(Tarjan(v,u);if(Low[u]>Low[v])Low[u]=Low[v];if(Low[v]>=DFN[u]){block++;intvn;cc=0;memset(ok,false,sizeof(ok));dovn=Stack[——top];Belong[vn]=block;Instack[vn]=false;ok[vn]=true;tmp[cc++]=vn;while(vn!=v);ok[u]=1;memset(color,-1,sizeof(color));if(!dfs(u,0))(can[u]=true;while(cc--)can(tmp[cc]]=true;})}elseif(Instack[v]&&Low[u]>DFN[v])Low[u]=DFN[v];))voidsolve(intn){memset(DFN,0,sizeof(DFN));memset(Instack,false,sizeof(Instack));Index=block=top=0;memset(can,false,sizeof(can));for(inti=l;i<=n;i++)if(!DFN[i])Tarjan(i,-1);intans=n;

120for(inti=1;i<=n;i++)if(can[i])ans--;printf(n%d

121H,ans);)voidinit()tot=0;memset(head,-1,sizeof(head));)intg[MAXN][MAXN];intmain(){intn,m;inturv;while(scanf(M%d%dM,&n,&m)==2){if(n==0&&m==0)break;init();memset(g,0,sizeof(g));while(m——)(scanf(n%d%d",&uz&v);g[u][v]=g[v][u]=l;}for(inti=1;i<=n;i++)for(intj=l;j<=n;j++)if(i!=j&&g[i][j]==s0)addedge(i,j);solve(n);)return0;9、最小树形图#include#include#include#include〈algorithm〉usingnamespacestd;/**最小树形图*int型*复杂度O(NM)*点从0开始*/constintINF=0x3f3f3f3f;constintMAXN=1010;constintMAXM=40010;structEdge{intu,vrcost;)；Edgeedge[MAXM];intpre[MAXN],id[MAXN],visit[MAXN]zin[MAXN];intzhuliu(introot,intn,intm,Edgeedge[])(intres=0,u,v;whiled)

122for(inti=0;i

123edge[L++].cost=g[i][j];}intans=zhuliu(0,nzL,edge);printf("Case#%d:*',iCase);i£(ans==-1)printf(wPossums!

124M);elseprintf(n%d

125n,ans);)

12610、二分图匹配1)一个二分图中的最大匹配数等于这个图中的最小点覆盖数Konig定理是一个二分图中很重要的定理，它的意思是，一个二分图中的最大匹配数等于这个图中的最小点覆盖数。如果你还不知道什么是最小点覆盖，我也在这里说一下：假如选了一个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖所有的边。2)最小路径覆盖=|G|-最大匹配数在一个N*N的有向图中，路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；(如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次)：如果不考虑图中存在回路，那么每每条路径就是一个弱连通子集.由上面可以得出：1.一个单独的顶点是一条路径；2.如果存在一路径p1,p2pk,其中p1为起点，pk为终点，那么在覆盖图中，顶点p1,p2pk不再与其它的顶点之间存在有向边.最小路径覆盖就是找出最小的路径条数，使之成为G的一个路径覆盖.路径覆盖与二分图匹配的关系：最小路径覆盖=IGI一最大匹配数；3)二分图最大独立集=顶点数-二分图最大匹配独立集：图中任意两个顶点都不相连的顶点集合。10.1邻接矩阵(匈牙利算法)/★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★//二分图匹配(匈牙利算法的DFS实现)(邻接矩阵形式)//初始化：两边顶点的划分情况//建立g[i][j]表示i->j的有向边就可以了，是左边向右边的匹配//g没有边相连则初始化为0//uN是匹配左边的顶点数，VN是匹配右边的顶点数//调用：res=hungary();输出最大匹配数//优点：适用于稠密图，DFS找增广路，实现简洁易于理解//时间复杂度：0(VE)//顶点编号从0开始的constintMAXN=510;intuN,vN;//u,v的数比使用前面必须赋值intg[MAXN][MAXN];//邻接矩阵intlinker[MAXN];boolused[MAXN];booldfs(intu)(for(intv=0;v

127memset(linker,-1,sizeof(linker));for(intu=0;u

128memset(used,false,sizeof(used));if(dfs(u))res++;)returnres;)10.2Hopcroft-Carp算法I★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★*二分图匹配(Hopcroft-Carp算法)*复杂度0(sqrt(n)*E)*邻接表存图，vector实现*vector先初始化，然后假如边*UN为左端的顶点数，使用前赋值(点编号0开始)*/constintMAXN=3000;constintINF=0x3f3f3f3f;vectorG[MAXN];intuN;intMx[MAXN],My[MAXN];intdx[MAXN],dy[MAXN];intdis;boolused[MAXN];boolSearchP(){queueQ;dis=INF;memset(dx,-1,sizeof(dx));memset(dy,-1,sizeof(dy));for(inti=0;idis)break;intsz=G[u].size();for(inti=0;i

129if(My[v]!=-1&&dy[v]==dis)continue;if(My[v]==-1||DFS(My[v]))IMy[v]=u;Mx[u]=v;returntrue;)})returnfalse;)intMaxMatch()intres=0;memset(Mx,-1,sizeof(Mx));memset(My,-1,sizeof(My));while(Search?()){memset(used,false,sizeof(used));for(inti=0;i

130printf("%d

131n,ret.det(n-1));

132计算生成树个数，不取模，SPOJ104#include#include#include#include#includeusingnamespacestd;constdoubleeps=le-8;constintMAXN=110;intsgn(doublex)(if(fabs(x)

133printf(M%.Olf

134Mrans);)return0;)11、二分图多重匹配constintMAXN=1010;constintMAXM=510;intuN,vN;intg[MAXN][MAXM];intlinker[MAXM][MAXN];boolused(MAXM];intmim[MAXM];//右边最大的匹配数booldfs(intu)for(intv=0;v

135visx[x]=true;for(inty=0;ytmp)slack[y]=tmp;)returnfalse;)intKM()(memset(linker,-1,sizeof(linker));memset(ly,0,sizeof(ly));for(inti=0;ilx[i])lx[i]=g[i][j];)for(intx=0;xslack[i])d=slack[i];for(inti=0;i

136for(intj=0;j

137"rKM());)return0;13、最大流13.1SAP邻接矩阵形式/**SAP算法(矩阵形式)*结点编号从0开始*/constintMAXN=1100;intmaze[MAXN][MAXN];intgap[MAXN],dis[MAXN],pre[MAXN],cur[MAXN];intsap(intstart,intend,intnodenum)(memset(cur,0,sizeof(cur));memset(dis,0,sizeof(dis));memset(gap,0,sizeof(gap));intu=pre[start]=start,maxflow=0,aug=-l;gap[0]=nodenum;while(dis[start]maze[u][v])aug=maze[u][v];pre[v]=u;u=cur[u]=v;if(v==end)(maxflow+=aug;for(u=pre[u];v!=start;v=u,u=pre[u]){maze[u][v]-=aug;maze[v][u]+=aug;)aug=-l;gotoloop;)intmindis=nodenum-l;for(intv=0;vdis[v])(cur[u]=v;mindis=dis[v];}if((-gap[dis[u]])==0)break;gap[dis[u]=mindis+l]++;u=pre[u];)returnmaxflow;)13.2SAP邻接矩阵形式2保留原矩阵，可用于多次使用最大流/**SAP邻接矩阵形式*点的编号从0开始*增加个flow数组，保留原矩阵maze,可用于多次使用最大流*/constintMAXN=1100;

138intmaze(MAXN)[b4AXN];intgap[MAXN],dis[MAXN],pre[MAXN],cur[MAXN];intflow[MAXN][MAXN];//存最大流的容量intsap(intstart,intend,intnodenum)(memset(cur,0,sizeof(cur));memset(dis,0,sizeof(dis));memset(gap,0,sizeof(gap));memset(flow,0,sizeof(flow));intu=pre[start]=start,maxflow=0zaug=-l;gap[0]=nodenum;while(dis[start]maze[u][v]-flow[u][v])aug=maze[u][v]-flow[u][v];pre[v]=u;u=cur[u]=v;if(v==end)(maxflow+=aug;for(u=pre[u];v!=start;v=u,u=pre[u]){flow[u][v]+=aug;flow[v][u]-=aug;)aug=-l;}gotoloop;}intmindis=nodenum-l;for(intv=0;vdis[v])(cur[u]=v;mindis=dis[v];|if((——gap[dis[u]])==0)break;gap[dis[u]=mindis+l]++;u=pre[u];)returnmaxflow;)*3.3ISAP邻接表形式constintMAXN=100010；//点数的最大值constintMAXM=400010;//边数的最大值constintINF=0x3f3f3f3f;structEdge(intto,next,cap,flow;)edge[MAXM];//注意是MAXMinttol;inthead[MAXN];intgap[MAXN],dep[MAXN],pre[MAXN]rcur[MAXN];voidinit(){tol=0;memset(head,-1,sizeof(head));)//加边，单向图三个参数，双向图四个参数voidaddedge(intu,intv,intw,intrw=0)edge[tol].to=v;edge[tol].cap=w;edge[tol].next=head[u];edge[tol].flow=0;head[u]=tol++;

139edge[tol].to=u;edge[tol].cap=rw;edge[tol].next=head[v];edge[tol].flow=0;head[v]=tol++;)//输入参数：起点、终点、点的总数//点的编号没有影响，只要输入点的总数intsap(intstart,intend,intN){memset(gap,0,sizeof(gap));memset(dep,0,sizeof(dep));memcpy(cur,head,sizeof(head));intu=start;pre[u]=-1;gap[0]=N;intans=0;while(dep(start]edge[i].cap-edge[i].flow)Min=edge[i].cap-edge[i].flow;for(inti=pre[u];i!=-1;i=pre[edge[iAl].to]){edge[i].flow+=Min;edge[iAl].flow-=Min;)u=start;ans+=Min;continue;boolflag=false;intv;for(inti=cur[u];i!=-1;i=edge[i].next)(v=edge[i].to;if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u])(flag=true;cur[u]=pre[v]=i;break;}}if(flag)(u=v;continue;}intMin=N;for(inti=head[u];i!=-1;i=edge[i].next)if(edge[i].cap-edge[i].flow&&dep[edge[i].to]

140memset(dep,-1,sizeof(dep));memset(gap,0,sizeof(gap));gap[0]=1;intfront=0,rear=0;dep[end]=0;Q[rear++]=end;while(front!=rear)intu=Q[front++];for(inti=head[u];i!=-1;i=edge[i].next)(intv=edge[i].to;if(dep[v]!=-1)continue;Q[rear++]=v;dep[v]=dep[u]+1;gap[dep[v]]++;}))intS[MAXN];intsap(intstart,intend,intN)BFS(start,end);memcpy(cur,head,sizeof(head));inttop=0;intu=start;intans=0;while(dep[start]edge(S[i]].cap-edge[S[i]].flow)(Min=edge[S[i]].cap-edge[S[i]].flow;inser=i;)for(inti=0;i

141dep[u]=Min+1;gap[dep[u]]++;if(u!=start)u=edge[S[-top]A1].to;)returnans;14、最小费用最大流最小费用最大流，求最大费用只需要取相反数，结果取相反数即可。点的总数为N,点的编号O~N-1constintMAXN=10000;constintMAXM=100000;constintINF=0x3f3f3f3f;structEdgeintto,next/cap,flow,cost;}edge[MAXM];inthead[MAXN]rtol;intpre[MAXN],dis[MAXN];boolvis[MAXN];intN;〃节点总个数,以点编号从0〜N-1voidinit(intn)(N=n;tol=0;memset(head,-1,sizeof(head));)voidaddedge(intu,intv,intcap,intcost){edge[tol].to=v;edge[tol].cap=cap;edge[tol].cost=cost;edge[tol].flow=0;edge[tol].next=head[u];head[u]=tol++;edge[tol].to=u;edge[tol].cap=0;edge[tol].cost=-cost;edge[tol].flow=0;edge[tol].next=head[v];head[v]=tol++;}boolspfa(ints,intt){queueq;for(inti=0;i

142if(edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){dis[v]=dis[u]+edge[i].cost;pre[v]=i;if(!vis[v])(vis[v]=true;q.push(v);})))if(pre[t]==-1)returnfalse;elsereturntrue;)//返回的是最大流，cost存的是最小费用intminCostMaxflow(ints,intt,int&cost)(intflow=0;cost=0;while(spfa(s,t)){intMin=INF;for(inti=pre[t];i!=-1;i=pre[edge[iAl].to])(if(Min>edge[i].cap-edge[i].flow)Min=edge[i].cap-edge[i].flow;)for(inti=pre[t];i!=-1;i=pre[edge[iAl].to])(edge[i].flow+=Min;edge[iAl].flow-=Min;cost+=edge[i].cost*Min;}flow+=Min;)returnflow;15、2-SAT15.1染色法(可以得到字典序最小的解)HDU1814constintMAXN=20020;constintMAXM=100010;structEdge{intto,next;}edge[MAXM];inthead[MAXN],tot;voidinit()(tot=0;memset(head,-1,sizeof(head));voidaddedge(intuzintv)(tot++;edge[tot].to=v;edge[tot].next=head[u];head[u])boolvis[MAXN];•为匚rue表示选择intS[MAXN],top;//栈booldfs(intu)

143(if(vis[uAl])returnfalse;if(vis[u])returntrue;vis[u]=true;S[top++]=u;for(inti=head[u];i!=-1;i=edge[i].next)if(!dfs(edge[i].to))returnfalse;returntrue;)boolTwosat(intn){memset(vis,false,sizeof(vis));for(inti=0;i

144”,i+1);}elseprintf(nNIE

145");)return0;)15.1强连通缩点法(拓扑排序只能得到任意解)POJ3648WeddingI/*★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★//2-SAT强连通缩点

146constintMAXN=1010;constintMAXM=100010;structEdge{intto,next;}edge[MAXM];inthead[MAXN]ttot;voidinit()tot=0;memset(head,T,sizeof(head));}voidaddedge(intu,intv){edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;}intLow[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值1〜seeintIndex,top;intsee;boolInstack[MAXN];intnum[MAXN];voidTarjan(intu)intv;Low[u]=DFN[u]=++Index;Stack[top++]=u;Instack[u]=true;for(inti=head[u];i!=-1;i=edge[i).next){v=edge[i].to;if(!DFN[v])(Tarjan(v);if(Low[u]>Low[v])Low[u]=Low[v];}elseif(Instack[v]&&Low[u]>DFN[v])Low[u]=DFN[v];)if(Low[uJ==DFN[u])SCC++；do(v=Stack[--top];Instack[v]=false;Belong[v]=see;num[see]++;}while(v!=u);))boolsolvable(intn)//n是总个数，需要选择一半{memset(DFN,0,sizeof(DFN));memset(Instack,false,sizeof(Instack));memset(num,0,sizeof(num));Index=see=top=0;for(inti=0;iql,q2;vector>dag;//缩点后的逆向DAG图charc。工or[MAXN];//染色，为，R，是选择的intindeg[MAXN];//A/8intcf[MAXN];voidsolve(intn)

147《dag.assign(scc+1,vector());memset(indeg,0,sizeof(indeg));memset(color,0,sizeof(color));for(intu=0;u=,0,&&s[i]<=,9,){ret*=10;ret+=s[i]-101;i++；)if(s[i]==1w*)return2*ret;elsereturn2*ret+l;)intmain(){intn,m;charsl[10]zs2[10];while(scanf(M%d%dM,&nr&m)==2)if(n==0&&m==0)break;init();while(m-)

148(scanf(”％s%s”，sl,s2);intu=change(si);intv=change(s2);addedge(uAlzv);addedge(vAl,u);}addedge(1,0);if(solvable(2*n))(solve(2*n);for(inti=1;i

149M);}}elseprintf("badluck

150M);)return0;16、曼哈顿最小生成树POJ3241求曼哈顿最小生成树上第k大的边

151constintMAXN=100010;constintINF=0x3f3f3f3f;structPoint{intx,y,id;}p[MAXN];boolcmp(Pointa,Pointb){if(a.x!=b.x)returna.x0)(if(val

152)intdist(Pointa,Pointb)(returnabs(a.x-b.x)+abs(a.y-b.y);)voidManhattan_minimum_spanning_tree(intn,Pointp[]){inta[MAXN],b[MAXN];tot=0;for(intdir=0;dir<4;dir++)(//4种坐标变换if(dir==1||dir==3)for(inti=0;i=0;i){intpos=lower_bound(b,b+m,a[i])-b+1;intans=ask(pos,m);if(ans!=-1)addedge(p[i].id,p[ans].id,dist(p[i],p[ans]));update(pos,p[i].x+p[i].y,i);)}}intsolve(intk){Manhattan_minimum_spanning_tree(n,p);memset(F,-1,sizeof(F));sort(edge,edge+totzcmpedge);for(inti=0;i

153H,solve(n-k));}return0;)17、一般图匹配带花树URAL1099constintMAXN=250;

154intN;//点的个数，点的编弓从1到NboolGraph[MAXN][MAXN];intMatch[MAXN];boolInQueue[MAXN],InPath[MAXN],InBlossom[MAXN];intHead,Tail;intQueue[MAXN];intStart,Finish;intNewBase;intFather[MAXN],Base[MAXN];intCount;//匹配数,匹配对数是Count/2voidCreateGraph(){intuzv;memset(Graph,false,sizeof(Graph));scanf(M%dn,&N);while(scanf("%d%dn,&u,&v)==2){Graph[u][v]=Graph[v][u]=true;voidPush(intu)(Queue[Tail]=u;Tail++;InQueue[u]=true;)intPop()(intres=Queue[Head];Head++;returnres;)intFindCommonAncestor(intu,intv){memset(InPath,false,sizeof(InPath));while(true)(u=Base[u];InPath[u]=true;if(u==Start)break;u=Father[Match[u]];)while(true)(v=Base[v];if(InPath[v])break;v=Father[Match[v]];}returnv;)voidResetTrace(intu)(intv;while(Base[u]!=NewBase){v=Match[u];InBlossom[Base[u]]=InBlossom[Base[v]]=true;u=Father[v];if(Base[u]!=NewBase)Father[u]=v;})voidBloosomContract(inturintv){NewBase=FindCommonAncestor(u,v);memset(InBlossom,false,sizeof(InBlossom));ResetTrace(u);

155ResetTrace(v);if(Base[u]!=NewBase)Father[u]=v;if(Base[v]!=NewBase)Father[v]=u;for(inttu=1;tu<=N;tu++)if(InBlossom[Base[tu]])Base[tu]=NewBase;if(!InQueue[tu])Push(tu);

156voidFindAugmentingPath()(memset(InQueue,false,sizeof(InQueue));memset(Father,0,sizeof(Father));for(inti=l;i<=N;i++)Base[i]=i;Head=Tail=1;Push(Start);Finish=0;while(Head0)&&Father[Match[v]]>0))BloosomContract(u,v);elseif(Father[v]==0)(Father[v]=u;if(Match[v]>0)Push(Match[v]);else(Finish=v;return;)))})voidAugmentPath(){intu,v,w;u=Finish;while(u>0)(v=Father[u];w=Match[v];Match[v]=u;Match[u]=v;u=w;)}voidEdmonds()(memset(Match,0,sizeof(Match));for(intu=1;u<=N;u++)if(Match[u]==0)Start=u;FindAugmentingPath();if(Finish>0)AugmentPath();))voidPrintMatch()Count0;for(intu=1;u<=N;u++)if(Match[u]>0)Count++;printfC^dXn",Count);for(intu=1;u<=N;u++)if(u

157n,u,Match[u]);)intmain()(CreateGraph();//建图Edmonds();//进行匹配PrintMatch();//输出匹配数和匹配return0;18、LCA18.1dfs+ST在线算法/**LCA(POJ1330)*在线算法DFS+ST*/constintMAXN=10010;intrmq[2，MAXN];//rmq数组,了structST{intmm[2*MAXN];intdp[2*MAXNH20];//最小值对应的下标voidinit(intn)(mm[0]=-1;for(inti=l;i<=n;i++)mm[i]=((i&(i-1))==0)?mm[i-l]+1;dp[i][0]=i;)for(intj=1;j<=mm[n];j++)for(inti=1;i+(1<b)swap(a,b);intk=mm[b-a+1];returnrmq[dp[a][k]]<=rmq[dp[b-(l<

158Edgeedge[MAXN*2];inttot,head[MAXN];intF[MAXN*2];//^^n-1,卜标从一intP[MAXN];//P[i]发示点i在F中第•次出现的位置intent;STst；voidinit(){tot=0;memset(head,-1,sizeof(head));)voidaddedge(intu,intv)//力口边，无向边需要力口两次{edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;)voiddfs(intu,intpre,intdep)(F[++cnt]=u;rmq[ent]=dep;P[u]=ent;for(inti=head[u];i!=-1;i=edge[i].next)(intv=edge[i].to;if(v==pre)continue;dfs(v,u,dep+1);F[++cnt]=u;rmq[ent]=dep;|)voidLCA_init(introot,intnode_num)//查询LCA前的初始化(ent=0;dfs(root,root,0);st.init(2*node_num-1);)intquery_lca(intu,intv)//查询u,v的len编，|returnF[st.query(P[u],P[v])];)boolflag[MAXN];intmain()|intT;intN;intu,v;scanf("%d",&T);while(T-)(scanf;init();memset(flag,false,sizeof(flag));for(inti=1;i

159"，query_lca(u,v));}return0;)18.1离线Tarjan算法/**POJ1470*给出一颗有向树，Q个查询*输出查询结果中每个点出现次数*//★*LCA离线算法，Tarjan*复杂度O(n+Q);*/constintMAXN=1010;constintMAXQ=500010;//查询数的最大值//并查集部分intF[MAXN];//需要初始化为-1intfind(intx){if(F[x]==-1)returnx;returnF[x]=find(F[x]);)voidbing(intu,intv)(inttl=find(u);intt2=find(v);if(tl!=t2)F[tl]=t2;

160)//************************boolvis[MAXN]；〃访问标记intancestor[MAXN];//祖先structEdge{intto,next;}edge[MAXN*2];inthead[MAXN],tot;voidaddedge(intu,intv)(edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++；structQuery{intq,next;intindex;〃查询编号}query[MAXQ*2];intanswer[MAXQ]，/存储最后的杳询结果，卜标0-Q-1inth[MAXQ];inttt;intQ;voidadd_query(intu,intv,intindex){query[tt].q=v;query[tt].next=h[u];query[tt].index=index;h[u]=tt++;query[tt].q=u;query[tt].next=h[v];query[tt].index=index;h[v]=tt++;)voidinit(){tot=0;memset(head,-1,sizeof(head));tt=0;memset(h,-1,sizeof(h));memset(vis,false,sizeof(vis));memset(F,-1,sizeof(F));memset(ancestor,0,sizeof(ancestor));)voidLCA(intu)(ancestor[u]=u;vis[u]=true;for(inti=head[u];i!=-1;i=edge[i].next)(intv=edge[i].to;if(vis[v])continue;LCA(v);bing(u,v);ancestor[find(u)]=u;}for(inti=h[u];i!=-1;i=query[i].next)(intv=query[i].q;if(vis[v]){answer[query[i].index]=ancestor[find(v)];)})boolflag[MAXN];intCount_num[MAXN];intmain()(intn;intu,v,k;while(scanf("%dM,&n)==1)(init();memset(flag,false,sizeof(flag));for(inti=l;i<=n;i++)(

161scanf(n%d:(%d)"，&u,&k);while(k--)(scanf(*'%d",&v);flag[v]=true;addedge(u,v);addedge(v,u);))scanf("％d"，&Q);for(inti=0;i>ch;scanf(w%d%d)*',&uf&v);add_query(u,v,i);)introot;for(inti=l;i<=n;i++)if(!flag[i]){root=i;break;)LCA(root);memset(Count__num,0,sizeof(Count_num));for(inti=0;i0)printf(M%d:%d

162M,i,Count_num[i]);return0;)18.1LCA倍增法/**POJ1330*LCA在线算法*/constintMAXN=10010;constintDEG=20;structEdge{intto,next;}edge[MAXN*2];inthead[MAXN],tot;voidaddedge(intuzintv)(edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;)voidinit()(tot=0;

163memset(head,-1,sizeof(head));)intfa[MAXN][DEG];//且[iHj]/"、站点…向第"j个祖先intdeg[MAXN];〃深度数组voidBFS(introot)queueque;deg[root]=0;fa[root][0]=root;que.push(root);while(!que.empty())(inttmp=que.front();que.pop();for(inti=1;ideg[v])swap(u,v);inthu=deg[u],hv=deg[v];inttu=u,tv=v;for(intdet=hv-hu,i=0;det;det>>=lri++)if(det&l)tv=fa[tv][i];if(tu==tv)returntu;for(inti=DEG-1;i>=0;i-)(if(fa[tu][i]==fa[tv][i])continue;tu=fa[tu][i];tv=fa[tv][i];}returnfa[tu][0];)boolflag[MAXN];intmain()intT;intn;inturv;scanf(“茗d”，&T);while(T-)(scanf("%dM,&n);init();memset(flag,false,sizeof(flag));for(inti=1;i

164”，LCA(u,v));

165)return0;}19、欧拉路欧拉回路：每条边只经过一次，而且回到起点欧拉路径：每条边只经过一次，不要求回到起点欧拉回路判断：无向图：连通(不考虑度为。的点)，每个顶点度数都为偶数。有向图：基图连通(把边当成无向边，同样不考虑度为。的点)，每个顶点出度等于入度。混合图(有无向边和有向边)：首先是基图连通(不考虑度为。的点)，然后需要借助网络流判定。首先给原图中的每条无向边随便指定一个方向(称为初始定向)，将原图改为有向图G3然后的任务就是改变G，中某些边的方向(当然是无向边转化来的，原混合图中的有向边不能动)使其满足每个点的入度等于出度.设D[i]为G，中(点i的出度-点i的入度).可以发现，在改变G，中边的方向的过程中，任何点的D值的奇偶性都不会发生改变(设将边改为.则i入度加1出度减1.j入度减1出度加1.两者之差加2或减2,奇偶性不变)！而最终要求的是每个点的入度等于出度，即每个点的D值都为0,是偶数，故可得：若初始定向得到的G，中任意一个点的D值是奇数，那么原图中一定不存在欧拉环！若初始D值都是偶数，则将G，改装成网络：设立源点S和汇点T,对于每个D[i]>0的点i,连边.容量为D[i]/2;对于每个D[j]<0的点j,连边,容量为-D[j]/2;G，中的每条边在网络中仍保留，容量为1(表示该边最多只能被改变方向一次)。求这个网络的最大流，若S引出的所有边均满流，则原混合图是欧拉图，将网络中所有流量为1的中间边(就是不与S或T关联的边)在G'中改变方向，形成的新图一定是有向欧拉图；若S引出的边中有的没有满流，则原混合图不是欧拉图。欧拉路径的判断：无向图：连通(不考虑度为0的点)，每个顶点度数都为偶数或者仅有两个点的度数为偶数。有向图：基图连通(把边当成无向边，同样不考虑度为。的点)，每个顶点出度等于入度或者有且仅有一个点的出度比入度多1,有且仅有一个点的出度比入度少1,其余出度等于入度。混合图：如果存在欧拉回路，一点存在欧拉路径了。否则如果有且仅有两个点的(出度-入度)是奇数，那么给这个两个点加边，判断是否存在欧拉回路。19.1有向图POJ2337给出n个小写字母组成的单词，要求将n个单词连接起来，使得前一个单词的最后一个字母和后一个单词的第一个字母相同。输出字典序最小的解。structEdge(inttoznext;intindex;boolflag;}edge[2010];inthead[30],tot;voidinit()《tot=0;memset(head,-1,sizeof(head));)voidaddedge(intuzintv,intindex){edge[tot].to=v;

166edge[tot].next=head[u];edge[tot].index=index;edge[tot].flag=false;head[u]=tot++;}stringstr[1010];intin[30],out[30];intent;intans[1010];voiddfs(intu)|for(inti=head[u];i!=-1;i=edge[i].next)if(!edge[i].flag)(edge[i].flag=true;dfs(edge[i].to);ans[cnt++]=edge[i].index;)}intmain()//freopen("in.txt","r",stdin);//freopen("out.txt",nwn,stdout);intTzn;scanf(n%dnr&T);whiled—)(scanf("%dn,&n);for(inti=0;i>str[i];sort(str,str+n);//要输出字典序最小的解，先按照字典厅JII序init();memset(in,0,sizeof(in));memset(out,0,sizeof(out));intstart=100;for(inti=n-1;i>=0;i-)//字典序大的先加入{intu=str[i][0]-*a1;intv=str[i][str[i].lengthO-1]-1;addedge(u,v,i);out[u]++;in[v]++;if(u

167elseif(out[i]-in[i]==-1)cc2++;elseif(out[i]-in[i]!=0)ccl=3;)if(!((ccl==0&&cc2==0)||(ccl==1&&cc2==1)))printf(n***

168n);continue;)ent=0;dfs(start);if(ent!=n)//判断是否连通(printf(”***

169M);continue;)for(inti=cnt-1;i>=0;i){cout<0)printf(n.M);elseprintf(n

170n);}}return0;)19.2无向图SGU101structEdge(intto,next;intindex;intdir;boolflag;}edge[220];inthead[10]rtot;voidinit()(memset(head,-1,sizeof(head));tot=0;)voidaddedge(intu,intv,intindex)(edge[tot].to=v;edge[tot].next=head[u];edge[tot].index=index;edge[tot].dir=0;edge[tot].flag=false;head[u]=tot++；edge[tot].to=u;edge(tot].next=head[v];edge[tot].index=index;edge[tot].dir=1;edge[tot].flag=false;head[v]=tot++;}intdu[10];vectorans;voiddfs(intu)(for(inti=head[u];i!=-1;i=edge[i].next)if(!edge[i].flag)(edge[i].flag=true;edge[iAl].flag=true;

171dfs(edge[i].to);ans,push_back(i);))intmain()//freopen("in.txt**,nrM,stdin);//freopen("out.txtn,*'wn,stdout);intn;while(scanf("%dnt&n)==1)(init();intu,v;memset(du,0,sizeof(du));for(inti=l;i<=n;i++)(scanf("%d%d”，&u,&v);addedge(u,v,i);du[u]++;du[v]++;)ints=-1;intent=0;for(inti=0;i<=6;i++)if(du[i]&1){cnt++;s=i;}if(du[i]>0&&s==-1))boolff=true;if(ent!=0&&ent!=2){printf("Nosolution

172M);continue;)ans•clear();dfs(s);if(ans.size()!=n)(printf("Nosolution

173M);continue;)for(inti=0;i

174");elseprintf(n+

175n);return0;)19.3混合图POJ1637(本题保证了连通，故不需要判断连通，否则要判断连通)constintMAXN=210;//最大流1SAP部分constintMAXM=20100;constintINF=0x3f3f3f3f;structEdge(intto,next,cap,flow;}edge[MAXM];inttol;inthead[MAXN];

176intgap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];voidinit(){tol=0;memset(head,-1,sizeof(head));)voidaddedge(intu,intv,intw,intrw=0){edge[tol].to=v;edge[tol].cap=w;edge[tol].next=head[u];edge[tol].flow=0;head[u]=tol++；edge[tol].to=u;edge[tol].cap=rw;edge[tol].next=head[v];edge[tol].flow=0;head[v]=tol++;)intsap(intstart,intend,intN)(memset(gap,0,sizeof(gap));memset(dep,0,sizeof(dep));memcpy(cur,head,sizeof(head));intu=start;pre[u]=-1;gap[0]=N;intans=0;while(dep[start]edge[i].cap-edge[i].flow)Min=edge[i].cap-edge[i].flow;for(inti=pre[u];i!=-1;i=pre[edge[iAl].to])(edge[i].flow+=Min;edge[iA1].flow-=Min;)u=start;ans+=Min;continue;)boolflag=false;intv;for(inti=cur[u];i!=-1;i=edge[i].next)(v=edge[i].to;if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u])flag=true;cur[u]=pre[v]=i;break;))if(flag)(u=v;continue;)intMin=N;for(inti=head[u];i!=-1;i=edge[i].next)if(edge[i].cap-edge[i].flow&&dep[edge[i].to]0)addedge(0,i,(out[i]-in[i])/2);elseif(in[i]-out[i]>0)addedge(i,n+1,(in[i]-out[i])/2);if((out[i]-in[i])&1)flag=false;)if(!flag)(printf(nimpossible

177n);

178continue;)sap(0,n+1,n+2);for(inti=head[0];i!=-1;i=edge[i].next)if(edge[i].cap>0&&edge[i].cap>edge[i].flow){flag=false;break;)if(flag)printf(npossible

179w);elseprintf(**impossible

180M);}return0;计算几何1、基本函数1.1Point定义constdoubleeps=le-8;constdoublePI=acos(-1.0);intsgn(doublex)if(fabs(x)

181returnPoint(x-b.x,y-b.y);}//叉积doubleoperatorA(constPoint&b)const(returnx*b.y-y*b.x;}//点积doubleoperator*(constPoint&b)const(returnx*b.x+y*b.y;}//绕原点旋转角度B(弧度值)，后x,y的变化voidtransXY(doubleB)(doubletx=x,ty=y;x=tx*cos(B)-ty*sin(B);y=tx*sin(B)+ty*cos(B);1.2Line定义structLine(Points,e;Line(){)Line(Point_s,Point_e)(s=_s;e=_e;}//两直线相交求交点//第一个值为0表示直线重合，为1表示平行，为。表示相交，为2是相交〃只有第一个值为2时，交点才有意义pairoperator&(constLine&b)const{Pointres=s;if(sgn((s-e)(b.s-b.e))==0)(if(sgn((s-b.e)A(b.s-b.e))==0)returnmake_pair(0,res);//重合elsereturnmake_pair(1,res);//平行

182doubletres.x+==((s-b.s)A(b.s-b.e))/((s-e)A(b.s-b.e));(e.x-s.x)*t;res.y+=(e.y-s.y)*t;returnmake_pair(2,res);))；1.2两点间距离//*两点间距离doubledist(Pointa,Pointb)(returnsqrt((a-b)*(a-b));}1.3判断：线段相交//*判断线段相交boolinter(Line11,Line12){returnmax(ll.s.x,ll.e.x)>=min(12.s.xz12.e.x)&&max(12.s.x,12.e.x)>=min(11.s.x,ll.e.x)&&max(ll.s.yrll.e.y)>=min(12.s.yr12.e.y)&&max(12.s.y,12.e.y)>=min(ll.s.yfll.e.y)&&sgn((12.szll.e)(ll.s-ll.e))*sgn((12.e-ll.e)A(ll.s-ll.e))<=0&&sgn((ll.s-12.e)A(12.s-12.e))*sgn((ll.e-12.e)A(12.s-12.e))<=0;1.4判断：直线和线段相交//判断直线和线段相交boolSeg_inter_line(Line11,Line12)〃判断直线11和线段12是否相交(returnsgn((12.s-ll.e)A(ll.s-ll.e))*sgn((12.e-11.e)A(11.s-11.e))<=0;}1.5点到直线距离//点到直线距离//返回为result,是点到直线最近的点PointPointToLine(PointP,LineL)Pointresult;doublet=((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s));result.x=L.s.x+(L.e.x-L.s.x)*t;result.y=L.s.y+(L.e.y-L.s.y)*t;returnresult;}1.6点到线段距离〃点到线段的距离//返回点到线段最近的点PointNearestPointToLineSeg(PointP,LineL)|Pointresult;doublet=((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s));if(t>=0&&t<=1){result.x=L.s.x+(L.e.x-L.s.x)*t;result.y=L.s.y+(L.e.y-L.s.y)*t;)else{if(dist(PrL.s)

1831.2计算多边形面积//计算多边形面积//点的编号从O-n-1doubleCalcArea(Pointp[]zintn)(doubleres=0;for(inti=0;i0)//点的编号//返回值：〃T:点在凸多边形外//0:点在凸多边形边界上//I:点在凸多边形内intinConvexPoly(Pointa,Pointp[],intn){for(inti=0;i

184side.e=poly[(i+1)%n];if(OnSeg(pzside))return0;//如果平行轴则不考虑if(sgn(side.s.y-side.e.y)==0)continue;if(OnSeg(side.s,ray)){if(sgn(side.s.y-side.e.y)>0)cnt++；)elseif(OnSeg(side.e,ray)){if(sgn(side.e.y-side.s.y)>0)cnt++;)elseif(inter(ray,side))cnt++;)if(ent%2==1)return1;elsereturn-1;}1.2判断凸多边形//判断凸多边形//允许共线边//点可以是顺时针给出也可以是逆时针给出//点的编号l~n-lboolisconvex(Pointpoly[],intn)(bools[3];memset(s,false,sizeof(s));for(inti=0;i0)returntrue;elseif(sgn(tmp)==0&&sgn(dist(plrlist[0])-dist(p2,list[0]))<=0)returntrue;elsereturnfalse;}voidGraham(intn)《PointpO;intk=0;pO=list[0];〃找最下边的一个点for(inti=1;ilist[i].y)I|(p0.y==list[i].y&&p0.x>list[i].x))(pO=list[i];k=i;)}swap(list[k],list[0]);sort(list+1,list+n,_cmp);

185if(n==1)(top=1;Stack[0]=0;return;}if(n==2)(top=2;Stack[0]=0;Stack[1]=1;return;}Stack[0]=0;Stack[1]=1;top=2;for(inti=2;i1&&sgn((list[Stack[top-1]]-list[Stack[top-2]])A(list[i]-list[Stack[top-2]]))<=0)top一;Stack[top++]=i;))3、平面最近点对（HDU1007）#include#include#include#include#includeusingnamespacestd;constdovibleeps=le-6;constintMAXN=100010;constdoubleINF=le20;structPoint(doublex,y;)；doubledist(Pointa,Pointb){returnsqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));)Pointp[MAXN];Pointtmpt[MAXN];boolcmpxy(Pointa,Pointb)(if(a.x!=b.x)returna.x

186)intmain()intn;while(scanf(M%d",&n)==1&&n)for(inti=0;i

187",Closest_Pair(0,n-1)/2);)return0;)4、旋转卡壳4.1求解平面最远点对(POJ2187BeautyContest)structPoint(intxry;Point(int__x=0,int_y=0){x=_x;y=_y;)Pointoperator—(constPoint&b)constreturnPoint(x-b.x,y-b.y);)intoperatorA(constPoint&b)const{returnx*b.y-y*b.x;)intoperator*(constPoint&b)constreturnx*b.x+y*b.y;)voidinput(){scanf("%d%dM,&x,&y);)}；//距离的平方intdist2(Pointa,Pointb)return(a-b)*(a-b);)〃******二维凸包，int***********constintMAXN=50010;Pointlist[MAXN];intStack[MAXN],top;bool_cmp(Pointpl,Pointp2)inttmp=(pl-list[0])(p2-list[0]);if(tmp>0)returntrue;elseif(tmp==0&&dist2(pl,list[0])<=dist2(p2,list[0]))returntrue;elsereturnfalse;)voidGraham(intn){Pointp0;intk=0;p0=list[0];for(inti=1;ilist[i].yII(pO.y==list[i].y&&pO.x>list[i].x))(pO=list[i];swap(list[k],list[0]);sort(list+l,list+nr_cmp);if(n==1){top=1;Stack[0]=0;return;)if(n==2)top=2;Stack[0]=0;Stack[1]=1;return;)Stack[0]=0;Stack[1]=1;top=2;for(inti=2;i1&&((list[Stack[top-1]]-list[Stack[top-2]])A(list[i]-list[Stack[top-2]]))<=0)top——;Stack[top++]=i;)}

188//旋转卡壳，求两点间距离平方的最大值introtating_calipers(Pointp[],intn)(intans=0;Pointv;intcur=1;for(inti=0;i

189n,rotating_calipers(p,top));)return0;)4.2求解平面点集最大三角形//旋转卡壳计算平面点集最大三角形面积introtating_calipers(Pointp[],intn)《intans=0;Pointv;for(inti=0;i

190M,(double)rotating_calipers(p,top)/2);)return0;)4.3求解两凸包最小距离(POJ3608)constdoubleeps=le-8;intsgn(doublex)(if(fabs(x)=0&&t<=1){result.x=L.s.x+(L.e.x-L.s.x)*t;result.y=L.s.y+(L.e.y-L.s.y)*t;}else{if(dist(P,L.s)

191/**求凸包，Graham算法*点的编号。〜n-l*返回凸包结果Stack［。〜top-1］为凸包的编号*/constintMAXN=10010;Pointlist[MAXN];intStack[MAXN]ztop;〃相对于list[0]的极角排序bool_cmp(Pointpl,Pointp2)(doubletmp=(pl-list[0])(p2-list(0]);if(sgn(tmp)>0)returntrue;elseif(sgn(tmp)==0&&sgn(dist(plrlist[0])-dist(p2flist[0]))<=0)returntrue;elsereturnfalse;}voidGraham(intn)(PointpO;intk=0;pO=list[0];〃找最下边的一个点for(inti=1;ilist[i].y)||(pO.y==list[i].y&&p0.x>list[i].x))(pO=list[i];k=i;)}swap(list[k],list[0]);sort(list+1,list4-n,_cmp);if(n==1)(top=1;Stack[0]=0;return;}if(n==2)(top=2;Stack[0]=0;Stack[1]=1;return;}Stack[0]=0;Stack[1]=1;top=2;for(inti=2;i1&&sgn((list[Stack[top-1]]-list[Stack[top-2]])A(list[i]-list[Stack[top-2]]))<=0)top——;Stack[top++]=i;})〃点pO到线段plp2的距离doublepointtoseg(Pointp0fPointpl,Pointp2){returndist(pO,NearestPointToLineSeg(pO,Line(pl,p2)));//平行线段pOpl和p2P3的距离doubledispallseg(PointpO,PointplzPointp2,Pointp3){doubleansi=min(pointtoseg(pOrp2,p3),pointtoseg(plrp2rp3));doubleans2=min(pointtoseg(p2rpO,pl)zpointtoseg(p3zp0,pl));returnmin(ansi,ans2);}//得到向量ala2和blb2的位置关系doubleGet_angle(Pointal,Pointa2,PointblrPointb2)(return(a2-al)(bl-b2);)doublerotating_calipers(Pointp[],intnp,Pointq[],intnq){intsp=0,sq=0;for(inti=0;i0)sq=i；doubletmp;doubleans=dist(p[sp]zq[sq]);for(inti=0;i

192",solve(p,n,q,m));)return0;)

1935、半平面交5.1半平面交模板(fromUESTC)constdoubleeps=le-8;constdoublePI=acos(-1.0);intsgn(doublex){if(fabs(x)eps)returna.keps)line[tot++]=line[i];inthead=0,tail=1;Q[0]=line[0];Q[l]=lined];resn=0;for(inti=2;ieps)tail—;while(headeps)head++;Q[++tail]=line[i];)while(headeps)tail—;while(headeps)head++;if(tail<=head4-1)return;for(inti=head;i

194Point(double_x,double__y)(x=_x;y=__y;)Pointoperator—(constPoint&b)const(returnPoint(x-b.x,y-b.y);}doubleoperatorA(constPoint&b)const(returnx*b.y-y*b.x;}doubleoperator*(constPoint&b)const(returnx*b.x+y*b.y;}}；//计算多边形面积doubleCalcArea(Pointp[],intn)(doubleres=0;for(inti=0;i

195if(sgn(c)>=0)returnfalse;elsecontinue;}Cut(a,b,c,p,ent);)if(sgn(CalcArea(pzent))==0)returnfalse;elsereturntrue;)intmain(){while(scanf(M%d",&n)==1)(for(inti=0;i

196n);elseprintf("No

197M);)}return0;)6、三点求圆心坐标（三角形外心）//过三点求圆心坐标Pointwaixin(Pointa,Pointb,Pointc){doubleal=b.x-a.x,bl=b.y-a.y,cl=(al*al+bl*bl)/2;doublea2=c.x-a.x,b2=c.y-a.y,c2=(a2*a2+b2*b2)/2;doubled=al*b2-a2*bl;returnPoint(a.x+(cl*b2-c2*bl)/dfa.y+(al*c2-a2*cl)/d);}7、求两圆相交的面积//两个圆的公共部分面积doubleArea_of_overlap(Pointclfdoublerl,Pointc2,doubler2){doubled=dist(cl,c2);if(rl+r2

1988、Pick公式顶点坐标均是整点的简单多边形：面积=内部格点数目+边上格点数目/2-1动态规划1、最长上升子序列O(nlogn)constintMAXN=500010;inta[MAXN]rb[MAXN];//用二分查找的方法找到一个位置，使得num>b[i-1)并且[i],并用num代替b[i]intSearch(intnum,intlow,inthigh){intmid;while(low<=high)mid=(low+high)/2;if(num>=b[mid])low=mid+l;elsehigh=mid-l;)returnlow;)intDP(intn)(inti,Yen,pos;b[l]=a[l];len=l;for(i=2;i<=n;i++){if)〃如果比b[]数组中最大还大直接插入到后面即可(len=len+l;b[len]=a[i];)“■•//用二分的方法在b□数组中找出第一个比a[i]大的位置并且让a[i]替代这个位置(pos=Search(a[i]z1,len);b[pos]=a[i];})returnlen;搜索1>DancingLinks1.1精确覆盖/**POJ3074*/constintN=9;//3*3数独

199constintMaxN=N*N*N+10;constintMaxM=N*N*4+10;constintmaxnode=MaxN*4+MaxM+10;charg[MaxN];structDLX(intn,m,size;intU[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];intH[MaxN],S[MaxM];intansd,ans[MaxN];voidinit(int_n,int_m)(n=_n;m=_m;for(inti=0;i<=m;i++)(S[i]=0;U[i]=D[i]=i;L[i]=i-1;R[i]=i+1;)R[m]=0;L[0]=m;size=m;for(inti=1;i<=n;i++)H[i]=-1;}voidLink(intr,intc)(++S[Col[++size]=c];Row[size]=r;D[size]=D[c];U[D[c]]=size;U[size]=c;D[c]=size;if(H[r]<0)H[r]=L[size]=R[size]=size;else{R[size]=R[H[r]];L[R[H[r]]]=size;L[size]=H[r];R[H[r]]=size;)}voidremove(intc){L[R[C]]=L[c];R[L[c]]=R[c]；for(inti=D[c];i!=c;i=D[i])for(intj=R[i];j!=i;j=R[j]){U[D[j]]=U[j];D[U[j]]=D[j];—S[Col[j]];)}voidresume(intc)(for(inti=U[c];i!=c;i=U[i])for(intj=L[i];j!=i;j=L[j])++S[Col[U[D[j]]=D[U[j]]=j]]；L[R[C]]=R[L[c]]=c；}boolDance(intd)(if(R[0]==0)(for(inti=0;i

200M);returntrue;|intc=R[0];for(inti=R[0];i!=0;i=R[i])if(S[i]

201remove(c);for(inti=D[c];i!=c;i=D[i])(ans[d]=Row[i];for(intj=R[i];j!=i;j=R[j])remove(Col[j]);if(Dance(d+1))returntrue;for(intj=L[i];j!=i;j=L[j])resume(Col[j]);)resume(c);returnfalse;})；voidplace(int&r,int&cl,int&c2zint&c3,int&c4,inti,intj,intk){r=(i*N+j)*N+k;cl=i*N+j+l;c2=N*N+i*N+k;c3=N*N*2+j*N+k;c4=N*N*3+((i/3)*3+(j/3))*N+k;)DLXdlx;intmain()(while(scanf(M%sn,g)==1)(if(strcmp(gz,,end,')==0)break;dlx.init(N*N*N,N*N*4);intr,cl,c2,c3,c4;for(inti=0;i

202S[i]=0;U[i]=D[i]=i;L[i]=i-1;R[i]=i+1;)R[m]=0;L[0]=m;size=m;for(inti=1;i<=n;i++)H[i]=-1;)voidLink(intr,intc)(++S[Col[++size]=c];Row[size]=r;D[size]=D[c];U[D[c]]=size;U[size]=c;D[c]=size;size;if(H[r]<0)H[r]=L[size]=R[size]elseR[size]=R[H[r]];L[R[H[r]]]=size;L[size]=H[r];R[H[r]]=size;)voidremove(intc)(for(inti=D[c];i!=c;i=D[i])L[R[i]]=L[i],R[L[i]]=R[i]；}voidresume(intc)(for(inti=U[c];i!=c;i=U[i])L[R[i]]=R[L[i]]=i;}boolv[MaxM];intf()(intret=0;for(intc=R[0];c!=0;c=R[c])v[c]=true;for(intc=R[0];c!=0;c=R[c])if(v[c]){ret++;v[c]=false;for(inti=D[c];i!=c;i=D[i])for(intj=R[i];j!=i;j=R[j])v[Col[j]]=false;)returnret;}voidDance(intd)(

203if(d+f()>=ansd)return;if(R[0]==0){if(d

204printf(n%d

205M,g.ansd);)return0;其他1、高精度/**高精度，支持乘法和加法*/structBiglnt{conststaticintmod=10000;conststaticintDLEN=4;inta[600],len;Biglnt()(memset(a,0,sizeof(a));len=1;)Biglnt(intv)(memset(a,0,sizeof(a));len=0;do(a[len++]=v%/nod;v/=mod;}while(v);}Biglnt(constchars[])(memset(a,0,sizeof(a));intL=strlen(s);len=L/DLEN;i£(L%DLEN)len++;intindex=0;for(inti=L-l;i>=0;i-=DLEN)\intt=0;intk=i-DLEN+1;if(k<0)k=0;for(intj=k;j<=i;j++)t=t*10+s[j]-,O1;a[index++]=t;)}Biglntoperator+(constBiglnt&b)const(Biglntres;res.len=max(len,b.len);for(inti=0;i<=res.len;i++)res.a[i]=0;

206for(inti=0;i0)res.len++;returnres;}Biglntoperator*(constBiglnt&b)const(Biglntres;for(inti=0;i

207)if(up!=0)res.a[i+b.len]=up;)res.len=len+b.len;while(res.a[res.len-1]==0&&res.len>1)res.len--;returnres;}voidoutput()(printf(n%dn,a[len-1]);for(inti=len-2;i>=0;i)printf("%04d",a[i]);printf("

208n);2、完全高精度HDU1134求卡特兰数#include#include#include〈algorithm〉#includeusingnamespacestd;/**完全大数模板*输出cin>>a*输出a.print();*注意这个输入不能自动去掉前导。的，可以先读入到char数组，去掉前导0,再用构造函数。*/#defineMAXN9999#defineMAXSIZE1010#defineDLEN4classBigNum{private:inta(500];//可以控制大数的位数intlen;public:BigNum(){len=l;memset(a,0,sizeof(a));}//构造函数BigNum(constint);//将一个int类型的变敢转化成大数BigNum(constchar*);//将一个字符串类型的变量转化为大数BigNum(constBigNum&);//拷贝构造函数BigNum&operators(constBigNum&);，赋值运算符,大数之间进行赋值运算friendistreamsoperator»(istreams,BigNum&);//1friendostreamSoperator«(ostreams,BigNum&);//HBigNumoperator+(constBigNumoperator-(constBigNumoperator*(constBigNumoperator/(constint&)const;运算BigNumoperatorA(constint&)const;BigNum&)const;BigNum&)const;BigNum&)const;〃重载加法运算符，两个大数之间的相加运算〃重载减法运算符，两个大数之间的相减运算//重载乘法运算符，两个大数之间的相乘运算//重载除法运算符，大数对一个整数进行相除//大数的n次方运算intoperator%(constint&)const;//大数对一个类型的变昂:进行取模运算booloperator>(constBigNum&T)const;//人数和另一个人数的大小比卒爻booloperator〉(constint&t)const;//人数和一个in-2忖的人小比较voidprint();//输出大数)；

209BigNum::BigNum(constintb)//将一个立J类型的变鼠转化为大数《intcfd=b;len=0;memset(a,0,sizeof(a));while(d>MAXN){c=d-(d/(MAXN+1))*(MAXN+1);d=d/(MAXN+1);a[len++]=c;)a[len++]=d;)BigNum::BigNum(constchar*s)//将一个字符串类型的变星转化为大数{intt,k,index,L,i;memset(a,0,sizeof(a));L=strlen(s);len=L/DLEN;if(L%DLEN)len++;index=0;for(i=L-l;i>=0;i-=DLEN)[t=0;k=i-DLEN+l;if(k<0)k=0;for(intj=k;j<=i;j++)t=t*10+s[a[index++]=t;))BigNum::BigNum(constBigNum&T):len(T.len)//拷贝构造函数(inti;memset(a,0,sizeof(a));for(i=0;i>(istream&in,BigNum&b)(charch[MAXSIZE*4];inti=-l;in>>ch;intL=strlen(ch);intcount=0,sum=O;for(i=L-l;i>=0;){sum=0;intt=l;for(intj=0;j<4&&i>=0;j++,i—,t*=10)(sum+=(ch[i]-,0,)*t;)b.a[count]=sum;count++;)b.len=count++;returnin;)ostream&operator«(ostreamsout,BigNumsb)中栽、汇"1:运算符{inti;cout<=0;i){printf(M%04dw,b.a[i]);)returnout;)BigNumBigNum::operator+(constBigNum&T)const//两个大数之间的相力'(BigNumt(*this);inti,big;big=T.len>len?T.len:len;for(i=0;iMAXN)(t.a[i+1]++;t.a[i]-=MAXN+l;})if(t.a[big]!=0)t,len=big+l;

210elset.len=big;returnt;}BigNumBigNum::operator-(constBigNum&T)const//两个大数之间的相减运算{inti,j,big;boolflag;BigNumtl,t2;if(*this>T){tls=*this;t2=T;flag=0;)elsetl=T;t2=*this;flag=l;)big=tl.len;for(i=0;ii)tl.a[j-]+=MAXN;tl.a[i]+=MAXN+l-t2.a[i];}elsetl.a[i]--t2.a[i];)tl.len=big;while(tl.a[len-1]==0&&t1.len>l){tl,len—;big——;)if(flag)tl.a[big-1]=0-tl.a[big-1];returntl;)BigNumBigNum::operator*(constBigNum&T)const//两个大数之间的相乘BigNumret;inti,j,up;inttemp,tempi;for(i=0;iMAXN){templ=temp-temp/(MAXN+1)*(MAXN+1);up=temp/(MAXN+1);ret.a[i+j]=templ;}else[up=0;ret.a[i+j]=temp;}}if(up!=0)ret.a[i+j]=up;)ret.len=i+j;while(ret.a[ret.len-1]==0&&ret.len>l)ret.len--;returnret;BigNumBigNum::operator/(constint&b)const//大数对个整数进行相除运算(BigNumret;inti,down=0;for(i=len-l;i>=0;i)(ret.a[i]=(a[i]+down*(MAXN+1))/b;

211down=a[i]+down*(MAXN+1)-ret.a[i]*b;)ret.len=len;while(ret.a[ret.len-1]==0&&ret.len>l)ret.len——;returnret;}intBigNum::operator%(constint&b)const工数对一个int类型的变■进行取模{inti,d=0;for(i=len-l;i>=0;i)d=((d*(MAXN+1))%b+a[i])%b;returnd;)BigNumBigNum::operatorA(constint&n)const//大数的n次方运算{BigNumt,ret(1);inti;if(n<0)exit(-1);if(n==0)return1;if(n==l)return*this;intm=n;while(m>l){t=*this;for(i=l;(i<(constBigNum&T)const//大数和另个大数的大小比较{intIn;if(len>T.len)returntrue;elseif(len==T.len){ln=len-l;while(a[In]==T.a[In]&&ln>=0)In——;if(ln>=0&&a[ln]>T.a[ln])returntrue;elsereturnfalse;)elsereturnfalse;boolBigNum::operator>(constint&t)const//人数和一个典J类型的变的大小比较(BigNumb(t);return*this>b;)voidBigNum::print()//输出大数inti;printf(n%dwza[len-l]);for(i=len-2;i>=0;i)printf("%04d"za[i]);printf("

212");)BigNumf[110]〃/卡特兰数intmain(){f[0]=l;for(inti=l;i<=100;i++)f[i-l]*(4*i-2)/(i+1);//卡特"I数递推式

213intn;while(scan£(“%d"，&n)==1)(if(n==-l)break;f[n].print();return0;3、strtok和sscanf结合输入空格作为分隔输入，读取一行的整数：gets(buf);intv;char*p=strtok(bufznn);while(p){sscanf(p,"％d”，&v);p=strtok(NULL,n**);}4、解决爆栈，手动加栈#pragmacomment(linker,"/STACK:1024000000,1024000000")5、STL5.1优先队列priority_queueempty()如果队列为空返回真pop()删除对顶元素push()加入一个元素size()返回优先队列中拥有的元素个数top()返回优先队列队顶元素在默认的优先队列中，优先级高的先出队。在默认的int型中先出队的为较大的数。priority_queueql;//大的先出对priority_queue,greater>q2;//小的先出队自定义比较函数：structcmp(booloperator()(intx,inty)(returnx>y;//x小的优先级高//也可以写成其他方式，如：returnp[x]>p[y];表示p[i]小的优先级高)}；priority_queue,cmp>q;//定义方法//其中，第二个参数为容器类型。第三个参数为比较函数。

214结构体排序：structnode(intx,y;friendbooloperator<(nodea,nodeb)returna.x>b.x;//结构体中，x小的优先级高))；priority_queueq;//定义方法//在该结构中，v为值，x为优先级。//通过自定义operatorc操作符来比较元素中的优先级。〃在重载”〃时，最好不要重载〃>〃，可能会发生编译错误5.1set和multisetset和multiset用法一样，就是multiset允许重复元素。元素放入容器时，会按照一定的排序法则自动排序，默认是按照less。排序规则来排序。不能修改容器里面的元素值，只能插入和删除。自定义int排序函数：(默认的是从小到大的，下面这个从大到小)structclasscomp{booloperator()(constint&lhszconstint&rhs)const{returnlhs>rhs;});//这里有个逗号的，注意multisetfifth;//classasCompare上面这样就定义成了从大到小排列了。结构体自定义排序函数：(定义set或者multiset的时候定义了排序函数，定义迭代器时一样带上排序函数)structNode(intxry;structclasscomp//先按照x从小到大排序，x相同则按照y从大到小排序(booloperator()(constNode&a,constNode&b)const{if(a.x!=b.x)returna.xb.y;));//注意这里有个逗号multisetmt;multiset::iteratorit;主要函数：begin()返回指向第一个元素的迭代器dear()清除所有元素count()返回某个值元素的个数empty()如果集合为空，返回trueend()返回指向最后一个元素的迭代器erase()删除集合中的元素(参数是一个元素值，或者迭代器)find()返回一个指向被查找到元素的迭代器insertf)在集合中插入元素size。集合中元素的数目lower_bound()返回指向大于(或等于)某值的第一个元素的迭代器upper_bound()返回大于某个值元素的迭代器equal_range()返回集合中与给定值相等的上下限的两个送代器

215(注意对于multiset删除操作之间删除值会把所以这个值的都删掉，删除一个要用迭代器)6、输入输出外挂//适用于正负整数templateinlineboolscan_d(T&ret){charc;intsgn;if(c=getchar(),c==EOF)return0;//EOFwhile(c!=*-1&&(c<*0*IIc>191))c=getchar();sgn=(c==*-*)?-l:1;ret=(c==*-*)?0:(c-*0*);while(c=getchar(),c>=,0&c<=’91)ret=ret*10+(c-101);ret*=sgn;return1;)inlinevoidout(intx){if(x>9)out(x/10);putchar(x%10+*0*);7、莫队算法莫队算法，可以解决一类静态，离线区间查询问题。BZOJ2038:[2009国家集训队]小Z的袜子(hose)Description作为一个生活散漫的人，小z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小z再也无法忍受这恼人的找袜子过程，于是他决定听天由命......具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(LInput输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。接下来一行包含N个正整数Ci,其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。再接下来M行，每行两个正整数L,R表示一个询问。Output包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1,否则输出的A/B必须为最简分数。(详见样例)SampleInput6412333226133516SampleOutput2/50/11/14/15题解：尸=%==一工产;Q2g(R—/■+D*(R-L)/2(Fl-L+1)*(F_L)只需要统计区间内各个数出现次数的平方和

216莫队算法，两种方法，一种是直接分成sqrt(n)块，分块排序。另外一种是求得曼哈顿距离最小生成树，根据manhattanMST的dfs序求解。7.1分块constintMAXN=50010;constintMAXM=50010;structQuery{intL,R,id;Jnode[MAXM];longlonggcd(longlongazlonglongb)if(b==0)returna;returngcd(b,a%b);)structAnslonglonga,b;a/bvoidreduce()//分数化简(longlongd=gcd(a,b);a/=d;b/=d;}ans[MAXM];inta[MAXN];intnum[MAXN];intn,m,unit;boolcrop(Querya,Queryb)(if(a.L/unit!=b.L/unit)returna.L/unitnode[i].R){temp-=(longlong)num[a[R]]*num[a[R]];num[a[R]]一;temp+=(longlong)num[a[R]]*num(a[R]];R—；)while(Lnode[i].L)(L-；temp-=(longlong)num[a[L]]*num(a[L]];num[a[L]]++;temp+=(longlong)num[a[L]]*num[a[L]];)ans[node[i].id].a=temp-(R-L+l);ans[node[i].id].b=(longlong)(R-L+l)*(R-L);ans[node[i].id].reduce();})intmain()|while(scanf(*'%d%dn,&n,&m)==2)(for(inti=1;i<=n;i++)scanf("%dM,&a[i]);for(inti=0;i

217scanf("%d%d",&node[i].L,&node[i].R);)unit=(int)sqrt(n);sort(node,node+m,cmp);work();for(inti=0;i

218n,ans[i].azans[i].b);)return0;)7.1ManhattanMST的dfs顺序求解constintMAXN=50010;constintMAXM=50010;constintINF=0x3f3f3f3f;structPointintx,y,id;}p[MAXN],pp[MAXN];boolcmp(Pointa,Pointb){if(a.x!=b.x)returna.x

219void_addedge(intu,intv){e[total].to=v;e[total].next=head[u];head[u]=total++；)intlowbit(intx)returnx&(-x);)voidupdate(inti,intval,intpos){while(i>0)(if(val=0;i)intpos=lower_bound(b,b+m,a[i])-b+1;intans=ask(pos,m);if(ans!=-1)addedge(p[i].id,p[ans]•id,dist(p[i]fp[ans]));update(pos,p[i].x+p[i].y,i);)}

220memset(F,-1,sizeof(F));sort(edge,edge+tot,cmpedge);total=0;memset(head,-1,sizeof(head));for(inti=0;irl)add(rl+1,r2);if(12>11)del(llr12-l);if(r2rl)del(rl-i-l,r2);if(12>11)add(llr12-1);if(r2

221while(scanf(*'%d%dM,&nz&m)==2)(for(inti=l;i<=n;i++)scanf(M%ciMr&a[i]);for(inti=0;i

222n,ans[i].a/d,ans[i].b/d);

223return0;)8、VIM配置setnusethistory=1000000settabstop=4setshiftwidth=4setsmarttabsetcindentcoloeveningsetnobackupsetnoswapfilesetmouse=amap:callCR()func!CR()exec"w**exec"!g++%-o%{}0map:callSetTitleOfuncSetTitle()let1=0let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|let1=1+1|callcallcallcallcallcallcallcallcallcallcallcallcallcallcallcallcallsetline(1,setline(1,setline(1,setline(1,setline(lrsetline(1,setline(1,setline(1,setline(1,setline(1,setline(1,setline(1,setline(1,setline(1,setline(1,setline(1,setline(1,•#include1#include'#include1#include'#include'#include'#include'#include•#include1#include'#include1#include,using*int1(')'),),}(algorithm〉'')1)')

224endfunc