ACM常?模板題基礎(chǔ)

ACM常用模板(+模板題)(基礎(chǔ))模板終究只是模板，最好還是自己真正掌握，經(jīng)常依賴模板，123456789101112131415161718192021222324252627//題目鏈接:/problem?id=2506//題目大意:就是問你用2*1,1*2,2*2的磚拼成2*n的長(zhǎng)方形,有多少種拼法//解題思路:考慮n的時(shí)候,假設(shè)我們已經(jīng)鋪好了n-1塊磚,第n塊只能豎著放//假設(shè)我們已經(jīng)鋪好了n-2塊磚,最后兩列有3種方式,但是其中有一種方法和#include<stdio.h>#include<iostream>#include<string.h>usingnamespacestd;constintmaxn=10000+10;//加法stringbigIntegerAdd(strings1,strings2){inta[maxn],b[maxn];memset(a,0,sizeof(a));memset(b,0,sizeof(b));intlen1=s1.size(),len2=s2.size();intmaxL=max(len1,len2);for(inti=0;i<len1;i++)a[i]=s1[len1-1-i]-'0';for(inti=0;i<len2;i++)b[i]=s2[len2-1-i]-'0';for(inti=0;i<maxL;i++){if(a[i]+b[i]>=10){inttemp=a[i]+b[i];a[i]=temp%10;a[i+1]+=(temp/10);}elsea[i]+=b[i];28293031323334353637383940414243444546474849505152535455565758596061626364656667686970}stringc="";if(a[maxL]!=0)c+=a[maxL]+'0';for(inti=maxL-1;i>=0;i--)c+=a[i]+'0';returnc;}//乘法stringbigIntegerMul(strings1,strings2){inta[maxn],b[maxn],c[maxn*2+5];memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c));intlen1=s1.size(),len2=s2.size();for(inti=0;i<len1;i++)a[i]=s1[len1-1-i]-'0';//倒置for(inti=0;i<len2;i++)b[i]=s2[len2-1-i]-'0';for(inti=0;i<len1;i++){for(intj=0;j<len2;j++){c[i+j]+=a[i]*b[j];}}for(inti=0;i<maxn*2;i++){if(c[i]>=10){c[i+1]+=c[i]/10;c[i]%=10;}}stringans="";inti;for(i=maxn*2;i>=0;i--)if(c[i]!=0)break;for(;i>=0;i--)ans+=c[i]+'0';returnans;}intmain(){//freopen("in.txt","r",stdin);intn;strings[255];s[0]="1",s[1]="1";//注意0的時(shí)候是1for(inti=2;i<=255;i++){71727374757677stringtemp=bigIntegerMul("2",s[i-2]);s[i]=bigIntegerAdd(s[i-1],temp);}while(~scanf("%d",&n))cout<<s[n]<<endl;return0;}1234567891011121314151617181920212223242526272829303132#include<bits/stdc++.h>constintmaxn=200+10;usingnamespacestd;typedeflonglongLL;//具體實(shí)現(xiàn)stringsubInfo(char*s1,char*s2){inta[maxn],b[maxn];memset(a,0,sizeof(a));memset(b,0,sizeof(b));intlen1=strlen(s1),len2=strlen(s2);intmaxLen=max(len1,len2);for(inti=0;i<len1;i++)a[i]=s1[len1-i-1]-'0';for(inti=0;i<len2;i++)b[i]=s2[len2-i-1]-'0';for(inti=0;i<maxLen;i++){if(a[i]-b[i]<0){a[i]=a[i]+10-b[i];a[i+1]-=1;}elsea[i]-=b[i];}stringstr="";inti;for(i=maxLen-1;i>=0;i--)if(a[i]!=0)break;for(;i>=0;i--)str+=a[i]+'0';returnstr;}//大數(shù)減法的模板stringbigIntegerSub(char*s1,char*s2){if(s1==s2)return"0";//相等33intlen1=strlen(s1),len2=strlen(s2);34if(len1>len2)35returnsubInfo(s1,s2);36elseif(len1<len2)37return"-"+subInfo(s2,s1);//負(fù)數(shù)38else{//長(zhǎng)度相等時(shí)判斷大小39for(inti=0;i<len1;i++){40if(s1[i]-'0'>s2[i]-'0')41returnsubInfo(s1,s2);42elseif(s1[i]-'0'<s2[i]-'0')43return"-"+subInfo(s2,s1);44}45}46}4748intmain(){49chars1[maxn],s2[maxn];50scanf("%s\n%s",s1,s2);51cout<<bigIntegerSub(s1,s2)<<endl;52return0;53}1///JudgeOnline/problem.php?pid=282//大數(shù)階乘的模板3#include<bits/stdc++.h>4usingnamespacestd;5constintmaxn=100000+10;67//大數(shù)計(jì)算階乘位數(shù)8//lg(N!)=[lg(N*(N-1)*(N-2)*......*3*2*1)]+1=[lgN+lg(N-1)+lg(N-2)+.9intfactorialDigit(intn){10doublesum=0;11for(inti=1;i<=n;i++){12sum+=log10(i);13}14return(int)sum+1;15}1617//大數(shù)計(jì)算階乘18stringbigFactorial(intn){1920212223242526272829303132333435363738394041424344454647intans[maxn],digit=1;ans[0]=1;for(inti=2;i<=n;i++){intnum=0;for(intj=0;j<digit;j++){inttemp=ans[j]*i+num;ans[j]=temp%10;num=temp/10;}while(num!=0){ans[digit]=num%10;num/=10;digit++;}}stringstr="";for(inti=digit-1;i>=0;i--)str+=ans[i]+'0';returnstr;}intmain(){intn;while(~scanf("%d",&n)){//cout<<factorialDigit(n)<<endl;//階乘的位數(shù)cout<<bigFactorial(n)<<endl;//求出階乘}return0;}二分的寫法可以有很多種，這里列舉幾個(gè)常見的，主要是上求最小的i，使得a[i]=key，若不存在，則返回-1(lowerbound函數(shù))；求最大的i的下一個(gè)元素的下標(biāo)(c++中的upperbound函數(shù))，使得a[i]=key，若不存在，則返回-1；求最大的i，使得a[i]=key，若不存在，則返回-1；求最小的i，使得a[i]>key，若不存在，則返回-1；求最大的i，使得a[i]<key，若不存在，則返回-1；12345678910111213141516171819202122232425262728293031323334353637383940#include<bits/stdc++.h>usingnamespacestd;constintmaxn=100+10;intcmp(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;}//普通的二分查找intbs(int*arr,intL,intR,inttarget){while(L<=R){intmid=(L)+(R-L)/2;if(arr[mid]==target)returnmid;if(arr[mid]>target)R=mid-1;elseL=mid+1;}return-1;//notfind}//求最小的i，使得a[i]=target，若不存在，則返回-1//返回如果有重復(fù)的下界(比如1,2,2,2,3,4)查找2,返回1intfirstEqual(intarr[],intL,intR,inttarget){while(L<R){intmid=L+(R-L)/2;if(arr[mid]<target)L=mid+1;elseR=mid;}if(arr[L]==target)returnL;return-1;}//求最大的i的下一個(gè)元素的下標(biāo)(c++中的upperbound函數(shù))，使得a[i]=target，若不intlastEqualNext(intarr[],intL,intR,inttarget){41424344454647484950515253545556575859606162636465666768697071727374757677787980818283while(L<R){intm=L+(R-L)/2;if(arr[m]<=target)L=m+1;elseR=m;}if(arr[L-1]==target)returnL;return-1;}//求最大的i，使得a[i]=target，若不存在，則返回-1intlastEqual(intarr[],intL,intR,inttarget){while(L<R){intmid=L+((R+1-L)>>1);//向上取整if(arr[mid]<=target)L=mid;elseR=mid-1;}if(arr[L]==target)returnL;return-1;}//求最小的i，使得a[i]>target，若不存在，則返回-1intfirstLarge(intarr[],intL,intR,inttarget){while(L<R){intm=L+((R-L)>>1);//向下取整if(arr[m]<=target)L=m+1;elseR=m;}if(arr[R]>target)returnR;return-1;}//求最大的i，使得a[i]<target，若不存在，則返回-1intlastSmall(intarr[],intL,intR,inttarget){while(L<R){84858687888990919293intm=L+((R+1-L)>>1);//向上取整84858687888990919293L=m;elseR=m-1;}if(arr[L]<target)returnL;return-1;}9495969798991001019596979899100101102103//freopen("in.txt","r",stdin);intn,a[maxn],v;scanf("%d",&n);for(inti=0;i<n;i++)scanf("%d",&a[i]);//13294137scanf("%d",&v);//inputthenumberyouneedfindqsort(a,n,sizeof(a[0]),cmp);//11222334printf("aftersorted:\n");for(inti=0;i<n;i++)printf("%d",a[i]);104105printf("\n-------------test----------------");105106107108109110111112113114115116117118printf("\n%d\n",firstEqual(a,0,n,v));printf("%d\n",lastEqualNext(a,0,n,v));printf("%d\n"107108109110111112113114115116117118printf("%d\n",firstLarge(a,0,n,v));printf("%d\n",lastSmall(a,0,n,v));return0;}測(cè)試數(shù)據(jù):2//output//output//output//output//output2第一個(gè)4+1,最后一個(gè)4最后一個(gè)5(第一個(gè)3大于21(不是0)119第10頁(yè)共78頁(yè)枚舉排列的算法也有幾個(gè)，包括劉汝佳書上的和經(jīng)典的，還有做過的幾個(gè)LeetCode46。12345678910111213141516171819#include<bits/stdc++.h>usingnamespacestd;constintmaxn=100+10;voidpermutation(int*arr,intn,intcur){if(cur==n){//邊界for(inti=0;i<n;i++)printf("%d",arr[i]);printf("\n");}elsefor(inti=1;i<=n;i++){//嘗試在arr[cur]中填充各種整數(shù)boolflag=true;for(intj=0;j<cur;j++)if(i==arr[j]){//如果i已經(jīng)在arflag=false;break;}if(flag){arr[cur]=i;//把i填充到當(dāng)前位置2021222324252627282930313233123456789101112131415161718192021222324252627permutation(arr,n,cur+1);}}}//求1~n的全排列，arr數(shù)組作為中間打印數(shù)組intmain(intargc,charconst**argv){inta[maxn],n;scanf("%d",&n);permutation(a,n,0);return0;}//可重集的全排列#include<bits/stdc++.h>constintmaxn=100+10;voidpermutation(int*arr,int*p,intn,intcur){if(cur==n){for(inti=0;i<n;i++)printf("%d",arr[i]);printf("\n");}elsefor(inti=0;i<n;i++)if(!i||p[i]!=p[i-1]){intc1=0,c2=0;for(intj=0;j<n;j++)if(p[j]==p[i])//重復(fù)元素的個(gè)數(shù)c1++;for(intj=0;j<cur;j++)if(arr[j]==p[i])//前面已經(jīng)排列的重復(fù)元素的個(gè)數(shù)c2++;if(c2<c1){arr[cur]=p[i];permutation(arr,p,n,cur+1);}}}intmain(){inta[maxn],p[maxn]={5,6,7,5};//可以有重復(fù)元素的全排列std::sort(p,p+4);第12頁(yè)共78頁(yè)282930311234567891011121314151617181920212223242526permutation(a,p,4,0);return0;}//全排列的非去重遞歸算法#include<bits/stdc++.h>usingnamespacestd;constintmaxn=100+10;voidpermutation(intarr[],intcur,intn){if(cur==n){for(inti=0;i<n;i++)printf("%d",arr[i]);printf("\n");}elsefor(inti=cur;i<n;i++){swap(arr[i],arr[cur]);permutation(arr,cur+1,n);swap(arr[i],arr[cur]);}}intmain(){intn,a[maxn];scanf("%d",&n);for(inti=0;i<n;i++)scanf("%d",&a[i]);permutation(a,0,n);return0;}增量構(gòu)造法，位向量法，二進(jìn)制法(常用)1234#include<bits/stdc++.h>usingnamespacestd;constintmaxn=100+10;第13頁(yè)共78頁(yè)5//打印0~n-1的所有子集6//按照遞增順序就行構(gòu)造子集防止子集的重復(fù)7voidprint_subset(int*arr,intn,intcur){8for(inti=0;i<cur;i++)9printf("%d",arr[i]);10printf("\n");11ints=cur?arr[cur-1]+1:0;//確定當(dāng)前元素的最小可能值12for(inti=s;i<n;i++){13arr[cur]=i;14print_subset(arr,n,cur+1);15}16}17intmain(){18intn,arr[maxn];19scanf("%d",&n);20print_subset(arr,n,0);21return0;22}231//1~n的所有子集：位向量法2#include<bits/stdc++.h>3constintmaxn=100+10;4usingnamespacestd;5intbits[maxn];//位向量bits[i]=1,當(dāng)且僅當(dāng)i在子集A中67voidprint_subset(intn,intcur){8if(cur==n){9for(inti=0;i<cur;i++)10if(bits[i])11printf("%d",i);12printf("\n");13return;14}15bits[cur]=1;16print_subset(n,cur+1);17bits[cur]=0;18print_subset(n,cur+1);19}20第14頁(yè)共78頁(yè)21222324252627intmain(){intn;scanf("%d",&n);print_subset(n,0);return0;}二進(jìn)制枚舉子集用的多，這里舉個(gè)例子n=3；則要枚舉0-7對(duì)應(yīng)的是有7個(gè)子集，每個(gè)子集去找有哪些元素print_subset中的1<<i，也就是對(duì)應(yīng)的那個(gè)位置是有元素的，例如1的二進(jìn)制是0001也就是代表0位置有元素，0010是2，代表第一個(gè)位置是1，0100代表第2個(gè)位置上有元素，相應(yīng)的1000=8對(duì)應(yīng)第3個(gè)位置上有元素。第15頁(yè)共78頁(yè)1234//0~n-1的所有子集：二進(jìn)制法枚舉0~n-1的所有子集#include<bits/stdc++.h>constintmaxn=100+10;第16頁(yè)共78頁(yè)5678910111213141516171819usingnamespacestd;voidprint_subset(intn,intcur){//這一步其實(shí)就是判斷cur的二進(jìn)制的各個(gè)位上是不是1，如果是1,就輸出對(duì)應(yīng)的那個(gè)for(inti=0;i<n;i++)if(1&(cur>>i))printf("%d",i);printf("\n");}intmain(intargc,charconst**argv){intn;scanf("%d",&n);for(inti=0;i<(1<<n);i++)print_subset(n,i);//枚舉各子集對(duì)應(yīng)的編碼0,1,2...pow(2,n)-1return0;}123456789101112131415161718192021//n皇后問題：普通回溯法#include<bits/stdc++.h>constintmaxn=100+10;usingnamespacestd;intsum,n,cnt;//解的個(gè)數(shù)，n皇后，遞歸次數(shù)intC[maxn];voidSearch(intcur){//逐行放置皇后cnt++;if(cur==n)sum++;elsefor(inti=0;i<n;i++){//嘗試在各列放置皇后boolflag=true;C[cur]=i;//嘗試把第cur行的皇后放在第i列//如果等下不行的話就下for(intj=0;j<cur;j++){//檢查是否和已經(jīng)放置的沖突if(C[cur]==C[j]||C[cur]+cur==C[j]+j||cur-C[flag=false;break;}}if(flag)Search(cur+1);}}第17頁(yè)共78頁(yè)22232425262728intmain(){scanf("%d",&n);//輸入n皇后sum=cnt=0;//解的個(gè)數(shù)和遞歸的次數(shù)Search(0);printf("%d%d\n",sum,cnt);return0;}1234567891011121314151617181920212223242526272829303132//n皇后問題：優(yōu)化的回溯法#include<bits/stdc++.h>constintmaxn=100+10;usingnamespacestd;intsum,n,cnt;intC[maxn];boolvis[3][maxn];intMap[maxn][maxn];//打印解的數(shù)組//一般在回溯法中修改了輔助的全局變量，一定要及時(shí)把他們恢復(fù)原狀voidSearch(intcur){//逐行放置皇后cnt++;if(cur==n){sum++;for(inti=0;i<cur;i++)Map[i][C[i]]=1;//打印解for(inti=0;i<n;i++){for(intj=0;j<n;j++)printf("%d",Map[i][j]);printf("\n");}printf("\n");memset(Map,0,sizeof(Map));//還原}elsefor(inti=0;i<n;i++){//嘗試在cur行的各列放置皇后if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n]){//判斷當(dāng)vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=true;C[cur]=i;//cur行的列是iSearch(cur+1);vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=false;//切記}}}第18頁(yè)共78頁(yè)33343536373839404142intmain(){scanf("%d",&n);memset(vis,false,sizeof(vis));memset(Map,0,sizeof(Map));sum=cnt=0;Search(0);printf("%d%d\n",sum,cnt);//輸出解決方案和遞歸次數(shù)return0;}123456789101112131415161718192021222324252627//題目連接:/problem?id=1611//題目大意:病毒傳染，可以通過一些社團(tuán)接觸給出一些社團(tuán)(0號(hào)人物是被感染的)問有多#include<stdio.h>constintmaxn=100000+10;intparent[maxn],rank[maxn];//parent[]保存祖先,rank記錄每個(gè)'樹的高度'voidinit(){for(inti=0;i<maxn;i++)parent[i]=i;//注意這里for(inti=0;i<maxn;i++)rank[i]=1;}//非遞歸intfindRoot(intv){while(parent[v]!=v){parent[v]=parent[parent[v]];//路徑壓縮v=parent[v];}returnv;}voidunions(inta,intb){intaRoot=findRoot(a);第19頁(yè)共78頁(yè)28293031323334353637383940414243444546474849505152535455565758596061626364intbRoot=findRoot(b);if(aRoot==bRoot)return;if(rank[aRoot]<rank[bRoot])parent[aRoot]=bRoot;elseif(rank[aRoot]>rank[bRoot]){parent[bRoot]=aRoot;}else{parent[aRoot]=bRoot;rank[bRoot]++;}}intis_same(intx,inty){//檢查是不是在同一個(gè)集合中returnfindRoot(x)==findRoot(y);}intmain(){intn,m,k,x,root;while(~scanf("%d%d",&n,&m)&&(n||m)){init();for(inti=0;i<m;i++){scanf("%d%d",&k,&root);for(intj=1;j<k;j++){scanf("%d",&x);unions(root,x);}}intsum=1;for(inti=1;i<n;i++)if(findRoot(i)==findRoot(0))sum++;//找和0是一個(gè)集合的printf("%d\n",sum);}return0;}樹狀數(shù)組的主要用于需要頻繁的修改數(shù)組元素，同時(shí)又要頻繁的查詢數(shù)第20頁(yè)共78頁(yè)第21頁(yè)共78頁(yè)所以計(jì)算2^k次方我們可以用如下代碼123intlowbit(intx){returnx&(-x);//或者returnx&(x^(x-1));}第22頁(yè)共78頁(yè)這里給出一個(gè)例題POJ2352Stars題目意思就是給你一些星星的坐標(biāo)，每個(gè)星星的級(jí)別是他左下方的星第23頁(yè)共78頁(yè)題目中一個(gè)重要的信息就是輸入是按照y遞增，如果對(duì)于第i顆星星，它的level就是之前出現(xiàn)過的星星中，橫坐標(biāo)小于等于i的星星的數(shù)量。代碼中有個(gè)小細(xì)節(jié)就是x++這是因?yàn)閘owbit不能傳值為0，否則會(huì)陷入死循環(huán)。123456789101112#include<stdio.h>#include<string.h>constintmaxn=32000+10;intn,c[maxn],level[15000+10];//計(jì)算2^kintlowbit(intx){returnx&(-x);}//更新數(shù)組的值voidupdate(inti,intval){第24頁(yè)共78頁(yè)13141516171819202122232425262728293031323334353637383940414243while(i<maxn){//注意這里是最大的x,沒有記錄所以用maxn,c[i]+=val;i+=lowbit(i);//不斷的往上面更新}}//查詢intsum(inti){ints=0;while(i>0){s+=c[i];i-=lowbit(i);//不斷的往下面加}returns;}intmain(){intx,y;scanf("%d",&n);memset(c,0,sizeof(c));memset(level,0,sizeof(level));for(inti=0;i<n;i++){scanf("%d%d",&x,&y);x++;//加入x+1，是為了避免0，X是可能為0的,LOlevel[sum(x)]++;update(x,1);//上面的層都要+1個(gè)}for(inti=0;i<n;i++)printf("%d\n",level[i]);return0;}12//題目連接:/showproblem.php?pid=1711//題目大意:找第二個(gè)數(shù)組在第一個(gè)數(shù)組中出現(xiàn)的位置，如果不存在，輸出-1第25頁(yè)共78頁(yè)3456789101112131415161718192021222324252627282930313233343536373839404142434445#include<stdio.h>constintmaxn=1000000+10;intn,m,a[maxn],b[10000+10],nexts[10000+10];voidgetNext(int*p,intnext[]){//優(yōu)化后的求next數(shù)組的方法intlen=m;next[0]=-1;//next數(shù)組中的最大長(zhǎng)度值(前后綴的公共最大長(zhǎng)度)的第一intk=-1,j=0;while(j<len-1){if(k==-1||p[j]==p[k]){//p[k]表示前綴p[j]表示后綴k++;j++;if(p[j]!=p[k])next[j]=k;elsenext[j]=next[k];//因?yàn)椴荒艹霈F(xiàn)p[j]=p[next[j]}elsek=next[k];}}intKMPSerach(int*s,int*p){intsLen=n,pLen=m;inti=0,j=0;while(i<sLen&&j<pLen){if(j==-1||s[i]==p[j])i++,j++;elsej=nexts[j];}if(j==pLen)returni-j;elsereturn-1;}intmain(){intT;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(inti=0;i<n;i++)scanf("%d",&a[i]);for(inti=0;i<m;i++)scanf("%d",&b[i]);getNext(b,nexts);//獲取next數(shù)組intans=KMPSerach(a,b);if(ans!=-1)printf("%d\n",ans+1);elseprintf("-1\n");}return0;}第26頁(yè)共78頁(yè)12345678910111213141516171819202122232425262728293031//題目鏈接：/index.php?m=ProblemSet&a=showProb//題目大意：找一串字符中是否出現(xiàn)"bkpstor"這段字符#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd;constintmaxn=1000;intlast(char*p,charc){//找到文本串的"壞字符"在模式串中的位置for(inti=strlen(p)-1;i>=0;i--)if(p[i]==c)returni;return-1;}intBM_index(char*T,char*p){intn=strlen(T);intm=strlen(p);inti=m-1,j=m-1;while(i<=n-1){if(T[i]==p[j])if(j==0)returni;elsei--,j--;else{i=i+m-min(j,1+last(p,T[i]));//文本的不符合的那個(gè)位置j=m-1;//模式串的新位置}}return-1;}intSum(char*T,char*P,ints){//輸出文本串中包含模式串的數(shù)量第27頁(yè)共78頁(yè)323334353637383940414243444546inte=BM_index(T+s,P);returne==-1?0:1+Sum(T,P,s+e+1);}//測(cè)試數(shù)據(jù):123bkpstor456bkpstor67intmain(){chars[maxn];while(~scanf("%s",s)){intcnt=BM_index(s,"bkpstor");//printf("%d\n",Sum(s,"bkpstor",0));出現(xiàn)次數(shù)輸出2if(cnt==-1)printf("Safe\n");elseprintf("Warning\n");}return0;}Sunday算法也是兩個(gè)規(guī)則123456789101112131415161718//題目鏈接：/index.php?m=ProblemSet&a=showProb//題目大意:找一串字符中是否出現(xiàn)"bkpstor"這段字符#include<stdio.h>#include<string.h>#include<algorithm>constintmaxn=1000;usingnamespacestd;intlast(char*p,charc){for(inti=strlen(p)-1;i>=0;i--)if(p[i]==c)returni;return-1;}intSunday(char*s,char*p){intsLen=strlen(s);intpLen=strlen(p);inti=0,j=0;while(i<sLen&&j<pLen){第28頁(yè)共78頁(yè)1920212223242526272829303132333435363738394041if(s[i]==p[j])i++,j++;else{intindex=i+pLen-j;//字符串中右端對(duì)齊的字符if(last(p,s[index])==-1){i=index+1;j=0;}/else{i=index-last(p,s[index]);j=0;//否則其移動(dòng)步}}}if(j==pLen)returni-j;return-1;}intmain(){chars[maxn];while(~scanf("%s",s)){intcnt=Sunday(s,"bkpstor");if(cnt==-1)printf("Safe\n");elseprintf("Warning\n");}return0;}01背包，完全背包/liusuangeng/article/details/38374405（很詳細(xì)）/xp731574722/article/details/70766804/na_beginning/article/details/62884939#reply/u013445530/article/details/4021058712345//題目連接:/showproblem.php?pid=2602#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd;第29頁(yè)共78頁(yè)6789101112131415161718192021222324252627282930313233343536373839404112345constintmaxn=1000+5;intw[maxn],v[maxn],dp[maxn][maxn],vis[maxn];//打印解voidprint(intn,intC){for(inti=n;i>1;i--){if(dp[i][C]==dp[i-1][C-w[i]]+v[i]){vis[i]=1;C-=w[i];}}vis[1]=(dp[1][C]>0)?1:0;}intmain(){freopen("in.txt","r",stdin);intn,C,T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&C);for(inti=1;i<=n;i++)scanf("%d",&v[i]);for(inti=1;i<=n;i++)scanf("%d",&w[i]);memset(dp,0,sizeof(dp));//dp[0][0~C]和dp[0~N][0]都為0，前者表示memset(vis,0,sizeof(vis));for(inti=1;i<=n;i++){for(intj=0;j<=C;j++){dp[i][j]=dp[i-1][j];//如果j不大于v[i]的話就dp[i][j]if(j>=w[i])dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]}}printf("%d\n",dp[n][C]);//n個(gè)物品裝入C容量的包能獲得的最大價(jià)值//print(n,C);//for(inti=1;i<=n;i++)if(vis[i])printf("%d",i);//輸}return0;}#include<stdio.h>#include<algorithm>#include<string.h>constintmaxn=1000+5;usingnamespacestd;第30頁(yè)共78頁(yè)678910111213141516171819202122232425261234567891011121314151617181920intw[maxn],v[maxn],dp[maxn][maxn];intmain(){intT,n,C;scanf("%d",&T);while(T--){scanf("%d%d",&n,&C);for(inti=1;i<=n;i++)scanf("%d",&v[i]);for(inti=1;i<=n;i++)scanf("%d",&w[i]);memset(dp,0,sizeof(dp));//dp全部初始化為0for(inti=n;i>=1;i--){for(intj=0;j<=C;j++){dp[i][j]=(i==n?0:dp[i+1][j]);if(j>=w[i])dp[i][j]=max(dp[i][j],dp[i+1][j-w[i]]+}}printf("%d\n",dp[1][C]);}return0;}#include<stdio.h>#include<algorithm>#include<string.h>constintmaxn=1000+5;usingnamespacestd;intw[maxn],v[maxn],dp[maxn];intmain(){intT,n,C;scanf("%d",&T);while(T--){scanf("%d%d",&n,&C);for(inti=1;i<=n;i++)scanf("%d",&v[i]);for(inti=1;i<=n;i++)scanf("%d",&w[i]);memset(dp,0,sizeof(dp));for(inti=1;i<=n;i++){for(intj=C;j>=0;j--){if(j>=w[i])dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}第31頁(yè)共78頁(yè)2122232425}printf("%d\n",dp[C]);}return0;}完全背包和01背包的差別在于每個(gè)物品的數(shù)量有無數(shù)個(gè)，在考慮第i件物品的時(shí)候，不是考12345678for(inti=1;i<n;i++){for(intj=1;j<=v;j++){for(intk=0;k*c[i]<=j;k++){if(c[i]<=j)dp[i][j]=max{dp[i-1][j],dp[i-1][j-k*c[elsedp[i][j]=dp[i-1][j]/*繼承前i個(gè)物品在當(dāng)前空間大小時(shí)的價(jià)值*}}}優(yōu)化:注意完全背包的順序問題：因?yàn)槊糠N背包都是無限的。當(dāng)我們把i從1到N循環(huán)時(shí)，dp[v]表示容量為v在前i種背包時(shí)所得的價(jià)值，這里我們要添加的不是前一個(gè)背包，而第32頁(yè)共78頁(yè)第i次循環(huán)中的狀態(tài)dp[i][v]是由狀態(tài)dp[i-1][v-c[i]]遞推而來。這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時(shí)，依據(jù)的是一個(gè)絕無已經(jīng)選入第i件物品的子結(jié)果dp[i-1][v-c[i]]。而現(xiàn)在完全背包的特點(diǎn)恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時(shí)，卻正需要一個(gè)可能已選入第i種物品的子結(jié)果dp[i][v-c[i]]，所以就參考博客:/Thousa_Ho/article/details/78156678/view/eea4a76b0b1c59eef8c7b497.html/shihuajie/archive/2013/04/27/3046458.html123456789101112#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd;constintmaxn=50000+10;constintINF=-0X7ffff;intw[maxn],v[maxn],dp[maxn];intmain(){intT,n,C;scanf("%d",&T);第33頁(yè)共78頁(yè)131415161718192021222324252627while(T--){scanf("%d%d",&n,&C);for(inti=1;i<=C;i++)dp[i]=INF;dp[0]=0;for(inti=0;i<n;i++)scanf("%d%d",&w[i],&v[i]);for(inti=0;i<n;i++){for(intj=w[i];j<=C;j++){//從前往后遞推，這樣才能保證dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}if(dp[C]>0)printf("%d\n",dp[C]);elseprintf("NO\n");}return0;}最長(zhǎng)(不)上升或下降子序列先說O(N*N)的解法，第i個(gè)元素之前的最長(zhǎng)遞增子序列的長(zhǎng)度要么是1（單獨(dú)成一個(gè)序列），要么就是第i-1個(gè)元素之前的最長(zhǎng)遞增子序列加1，這樣得到狀態(tài)方程：1LIS[i]=max{1,LIS[k]+1}(?k<i，arr[i]>arr[k])這樣arr[i]才能在arr[k]的基礎(chǔ)上構(gòu)成一個(gè)新的遞增子序列。123456789101112131415//題目連接:/JudgeOnline/problem.php?pid=17#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd;constintmaxn=10000+10;intdp[maxn];/*dp[i]記錄到[0,i]數(shù)組的LIS*/intmaxx;/*LIS長(zhǎng)度，初始化為1*/intLIS(char*arr,intn){for(inti=0;i<n;i++){dp[i]=1;for(intj=0;j<i;j++)//注意i只遍歷比它小的元素if(arr[j]<arr[i])dp[i]=max(dp[i],dp[j]+1);//改第34頁(yè)共78頁(yè)1617181920212223242526272829303132333435363738394041424344maxx=max(maxx,dp[i]);}returnmaxx;}/*遞歸輸出LIS，因?yàn)閿?shù)組dp還充當(dāng)了“標(biāo)記”作用*/voidprintLis(char*arr,intindex){boolisLIS=false;if(index<0||maxx==0)return;if(dp[index]==maxx){--maxx;isLIS=true;}printLis(arr,--index);if(isLIS)printf("%c",arr[index+1]);}intmain(){chars[maxn];intn;scanf("%d\n",&n);while(n--){maxx=1;scanf("%s",s);printf("%d\n",LIS(s,strlen(s)));//printLis(s,strlen(s)-1);printf("\n");}return0;}然后就是nlog(n)的解法：參考博客:/a/1190000002641054/joylnwang/article/details/6766317123456//題目連接:/problem?id=3903#include<stdio.h>#include<algorithm>#include<vector>#include<string.h>usingnamespacestd;第35頁(yè)共78頁(yè)78910111213141516171819202122232425262728293031323334353637383940414243444546474849constintINF=0x3f3f3f3f;constintmaxn=100000+5;inta[maxn],dp[maxn],pos[maxn],fa[maxn];vector<int>ans;//用于最長(zhǎng)非遞減子序列種的lower_bound函數(shù)intcmp(inta,intb){returna<=b;}//最長(zhǎng)上升子序列//dp[i]表示長(zhǎng)度為i+1的上升子序列的最末尾元素找到第一個(gè)比dp末尾大的來代替intLIS(intn){memset(dp,0x3f,sizeof(dp));pos[0]=-1;inti,lpos;for(i=0;i<n;++i){dp[lpos=(lower_bound(dp,dp+n,a[i])-dp)]=a[i];pos[lpos]=i;//*靠后打印fa[i]=(lpos?pos[lpos-1]:-1);}n=lower_bound(dp,dp+n,INF)-dp;for(i=pos[n-1];~fa[i];i=fa[i])ans.push_back(a[i]);ans.push_back(a[i]);returnn;}//非遞減的LISintLISS(intn){memset(dp,0x3f,sizeof(dp));pos[0]=-1;inti,lpos;for(i=0;i<n;i++){dp[lpos=(lower_bound(dp,dp+n,a[i],cmp)-dp)]=a[i];/pos[lpos]=i;//*靠后打印fa[i]=(lpos?pos[lpos-1]:-1);}n=lower_bound(dp,dp+n,INF)-dp;for(i=pos[n-1];~fa[i];i=fa[i])ans.push_back(a[i]);ans.push_back(a[i]);returnn;第36頁(yè)共78頁(yè)50515253545556575859606162}intmain(){//freopen("in.txt","r",stdin);intn;while(~scanf("%d",&n)){ans.clear();for(inti=0;i<n;i++)scanf("%d",&a[i]);printf("%d\n",LIS(n));//for(inti=ans.size(}return0;}最長(zhǎng)公共子序列利用動(dòng)態(tài)規(guī)劃的方式解決，具有質(zhì)，dp[i][j]記錄序列Xi和Yi的最長(zhǎng)公共子序列的長(zhǎng)度，當(dāng)i=0或j=0時(shí)，空序列時(shí)Xi和Yi的最長(zhǎng)公共子序列，其余情況如下123456789//題目連接:/problem?id=1458#include<stdio.h>#include<iostream>#include<string.h>usingnamespacestd;constintmaxn=1000+10;intdp[maxn][maxn];intpath[maxn][maxn];//記錄路徑第37頁(yè)共78頁(yè)10111213141516171819202122232425262728293031323334353637383940414243444546474849505152intLCS(char*s1,char*s2){intlen1=strlen(s1)-1,len2=strlen(s2)-1;//注意例如abcfbc的strfor(inti=0;i<=len1;i++)dp[i][0]=0;for(inti=0;i<=len2;i++)dp[0][i]=0;for(inti=1;i<=len1;i++){for(intj=1;j<=len2;j++)if(s1[i]==s2[j]){dp[i][j]=dp[i-1][j-1]+1;path[i][j]=1;}elseif(dp[i-1][j]>=dp[i][j-1]){dp[i][j]=dp[i-1][j];path[i][j]=2;}else{dp[i][j]=dp[i][j-1];path[i][j]=3;}}returndp[len1][len2];}//打印解voidprint(inti,intj,char*s){if(i==0||j==0)return;if(path[i][j]==1){print(i-1,j-1,s);printf("%c",s[i]);}elseif(path[i][j]==2){print(i-1,j,s);}elseprint(i,j-1,s);}intmain(){chars1[maxn],s2[maxn];while(~scanf("%s%s",s1+1,s2+1)){//注意s1[0]不取-注意例如abcfbc的stmemset(path,0,sizeof(path));printf("%d\n",LCS(s1,s2));//print(strlen(s1)-1,strlen(s2)-1,s1);}return0;}第38頁(yè)共78頁(yè)有向無環(huán)圖上的一種排序方式，我的這篇博客也講解了一下。123456789101112131415161718192021222324252627282930313233343536//題目鏈接:/contest/169966#problem/O#include<bits/stdc++.h>usingnamespacestd;constintmaxn=100+10;intn,m;intin[maxn];vector<int>G[maxn];voidtopo(){queue<int>q;for(inti=1;i<=n;i++)if(in[i]==0)q.push(i);boolflag=true;while(!q.empty()){intcur=q.front();q.pop();if(flag){printf("%d",cur);flag=false;}elseprintf("%d",cur);for(inti=0;i<G[cur].size();i++){if(--in[G[cur][i]]==0)q.push(G[cur][i]);}}}intmain(intargc,charconst**argv){intfrom,to;while(~scanf("%d%d",&n,&m)&&(n||m)){第39頁(yè)共78頁(yè)37383940414243444537383940414243444546474849for(inti=1;i<=n;i++)G[i].clear();for(inti=0;i<m;i++){scanf("%d%d",&from,&to);in[to]++;//度G[from].push_back(to);}topo();printf("\n");}return0;}501234512345#include<queue>#include<string.h>usingnamespacestd;#definemaxn5005678910typedef78910struct{///鄰接表實(shí)現(xiàn)next_arc;///下一條邊point;}Arc;///邊的結(jié)構(gòu)體，11121314Arcarc[maxn];121314intnode[maxn],vis[maxn],top[maxn];///儲(chǔ)存每個(gè)頂點(diǎn)，node[i]表示第i個(gè)頂點(diǎn)指intn,m,t;15161718192021222324void161718192021222324for(inti=node[v];i!=-1;i=arc[i].next_arc){if(!vis[arc[i].point]){dfs(arc[i].point);}}vis[v]=1;top[--t]=v;}252627intmain(){27第40頁(yè)共78頁(yè)28293031323334353637383940414243444546inta,b;while(cin>>n>>m&&(m||n)){memset(node,-1,sizeof(node));memset(vis,0,sizeof(vis));for(inti=1;i<=m;i++){cin>>a>>b;arc[i].next_arc=node[a];///第一次是出發(fā)點(diǎn)，以后是下一個(gè)arc[i].point=b;node[a]=i;vis[arc[i].point]=0;}t=n;for(intj=1;j<=n;j++)if(!vis[j])dfs(j);for(inti=0;i<n-1;i++)cout<<top[i]<<"";cout<<top[n-1]<<endl;}return0;}(2)對(duì)于無向圖來說度數(shù)為奇數(shù)的點(diǎn)個(gè)數(shù)為0，對(duì)于有向圖來說每個(gè)點(diǎn)的入度(2)對(duì)于無向圖來說，度數(shù)為奇數(shù)的的點(diǎn)可以有2個(gè)為起點(diǎn)另外一個(gè)為終點(diǎn)。對(duì)于有向圖來說，可以存在兩個(gè)點(diǎn)，判斷連通的方式有DFS或者并查集，然后再判斷一下是否滿足條件即可，之前做的歐拉回路的幾個(gè)好題在我的githu