ACM常⽤模板题基础

ACM常用模板(+模板题)(基础)模板终究只是模板，最好还是自己真正掌握，经常依赖模板，123456789101112131415161718192021222324252627//题目链接:/problem?id=2506//题目大意:就是问你用2*1,1*2,2*2的砖拼成2*n的长方形,有多少种拼法//解题思路:考虑n的时候,假设我们已经铺好了n-1块砖,第n块只能竖着放//假设我们已经铺好了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的时候是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;//具体实现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;}//大数减法的模板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);//负数38else{//长度相等时判断大小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//大数阶乘的模板3#include<bits/stdc++.h>4usingnamespacestd;5constintmaxn=100000+10;67//大数计算阶乘位数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//大数计算阶乘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;//阶乘的位数cout<<bigFactorial(n)<<endl;//求出阶乘}return0;}二分的写法可以有很多种，这里列举几个常见的，主要是上求最小的i，使得a[i]=key，若不存在，则返回-1(lowerbound函数)；求最大的i的下一个元素的下标(c++中的upperbound函数)，使得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//返回如果有重复的下界(比如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的下一个元素的下标(c++中的upperbound函数)，使得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;}测试数据:2//output//output//output//output//output2第一个4+1,最后一个4最后一个5(第一个3大于21(不是0)119第10页共78页枚举排列的算法也有几个，包括刘汝佳书上的和经典的，还有做过的几个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]中填充各种整数boolflag=true;for(intj=0;j<cur;j++)if(i==arr[j]){//如果i已经在arflag=false;break;}if(flag){arr[cur]=i;//把i填充到当前位置2021222324252627282930313233123456789101112131415161718192021222324252627permutation(arr,n,cur+1);}}}//求1~n的全排列，arr数组作为中间打印数组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])//重复元素的个数c1++;for(intj=0;j<cur;j++)if(arr[j]==p[i])//前面已经排列的重复元素的个数c2++;if(c2<c1){arr[cur]=p[i];permutation(arr,p,n,cur+1);}}}intmain(){inta[maxn],p[maxn]={5,6,7,5};//可以有重复元素的全排列std::sort(p,p+4);第12页共78页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;}增量构造法，位向量法，二进制法(常用)1234#include<bits/stdc++.h>usingnamespacestd;constintmaxn=100+10;第13页共78页5//打印0~n-1的所有子集6//按照递增顺序就行构造子集防止子集的重复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;//确定当前元素的最小可能值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,当且仅当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页共78页21222324252627intmain(){intn;scanf("%d",&n);print_subset(n,0);return0;}二进制枚举子集用的多，这里举个例子n=3；则要枚举0-7对应的是有7个子集，每个子集去找有哪些元素print_subset中的1<<i，也就是对应的那个位置是有元素的，例如1的二进制是0001也就是代表0位置有元素，0010是2，代表第一个位置是1，0100代表第2个位置上有元素，相应的1000=8对应第3个位置上有元素。第15页共78页1234//0~n-1的所有子集：二进制法枚举0~n-1的所有子集#include<bits/stdc++.h>constintmaxn=100+10;第16页共78页5678910111213141516171819usingnamespacestd;voidprint_subset(intn,intcur){//这一步其实就是判断cur的二进制的各个位上是不是1，如果是1,就输出对应的那个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);//枚举各子集对应的编码0,1,2...pow(2,n)-1return0;}123456789101112131415161718192021//n皇后问题：普通回溯法#include<bits/stdc++.h>constintmaxn=100+10;usingnamespacestd;intsum,n,cnt;//解的个数，n皇后，递归次数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++){//检查是否和已经放置的冲突if(C[cur]==C[j]||C[cur]+cur==C[j]+j||cur-C[flag=false;break;}}if(flag)Search(cur+1);}}第17页共78页22232425262728intmain(){scanf("%d",&n);//输入n皇后sum=cnt=0;//解的个数和递归的次数Search(0);printf("%d%d\n",sum,cnt);return0;}1234567891011121314151617181920212223242526272829303132//n皇后问题：优化的回溯法#include<bits/stdc++.h>constintmaxn=100+10;usingnamespacestd;intsum,n,cnt;intC[maxn];boolvis[3][maxn];intMap[maxn][maxn];//打印解的数组//一般在回溯法中修改了辅助的全局变量，一定要及时把他们恢复原状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]){//判断当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页共78页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);//输出解决方案和递归次数return0;}123456789101112131415161718192021222324252627//题目连接:/problem?id=1611//题目大意:病毒传染，可以通过一些社团接触给出一些社团(0号人物是被感染的)问有多#include<stdio.h>constintmaxn=100000+10;intparent[maxn],rank[maxn];//parent[]保存祖先,rank记录每个'树的高度'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页共78页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){//检查是不是在同一个集合中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是一个集合的printf("%d\n",sum);}return0;}树状数组的主要用于需要频繁的修改数组元素，同时又要频繁的查询数第20页共78页第21页共78页所以计算2^k次方我们可以用如下代码123intlowbit(intx){returnx&(-x);//或者returnx&(x^(x-1));}第22页共78页这里给出一个例题POJ2352Stars题目意思就是给你一些星星的坐标，每个星星的级别是他左下方的星第23页共78页题目中一个重要的信息就是输入是按照y递增，如果对于第i颗星星，它的level就是之前出现过的星星中，横坐标小于等于i的星星的数量。代码中有个小细节就是x++这是因为lowbit不能传值为0，否则会陷入死循环。123456789101112#include<stdio.h>#include<string.h>constintmaxn=32000+10;intn,c[maxn],level[15000+10];//计算2^kintlowbit(intx){returnx&(-x);}//更新数组的值voidupdate(inti,intval){第24页共78页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个}for(inti=0;i<n;i++)printf("%d\n",level[i]);return0;}12//题目连接:/showproblem.php?pid=1711//题目大意:找第二个数组在第一个数组中出现的位置，如果不存在，输出-1第25页共78页3456789101112131415161718192021222324252627282930313233343536373839404142434445#include<stdio.h>constintmaxn=1000000+10;intn,m,a[maxn],b[10000+10],nexts[10000+10];voidgetNext(int*p,intnext[]){//优化后的求next数组的方法intlen=m;next[0]=-1;//next数组中的最大长度值(前后缀的公共最大长度)的第一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];//因为不能出现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数组intans=KMPSerach(a,b);if(ans!=-1)printf("%d\n",ans+1);elseprintf("-1\n");}return0;}第26页共78页12345678910111213141516171819202122232425262728293031//题目链接：/index.php?m=ProblemSet&a=showProb//题目大意：找一串字符中是否出现"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]));//文本的不符合的那个位置j=m-1;//模式串的新位置}}return-1;}intSum(char*T,char*P,ints){//输出文本串中包含模式串的数量第27页共78页323334353637383940414243444546inte=BM_index(T+s,P);returne==-1?0:1+Sum(T,P,s+e+1);}//测试数据:123bkpstor456bkpstor67intmain(){chars[maxn];while(~scanf("%s",s)){intcnt=BM_index(s,"bkpstor");//printf("%d\n",Sum(s,"bkpstor",0));出现次数输出2if(cnt==-1)printf("Safe\n");elseprintf("Warning\n");}return0;}Sunday算法也是两个规则123456789101112131415161718//题目链接：/index.php?m=ProblemSet&a=showProb//题目大意:找一串字符中是否出现"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页共78页1920212223242526272829303132333435363738394041if(s[i]==p[j])i++,j++;else{intindex=i+pLen-j;//字符串中右端对齐的字符if(last(p,s[index])==-1){i=index+1;j=0;}/else{i=index-last(p,s[index]);j=0;//否则其移动步}}}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（很详细）/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页共78页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个物品装入C容量的包能获得的最大价值//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页共78页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页共78页2122232425}printf("%d\n",dp[C]);}return0;}完全背包和01背包的差别在于每个物品的数量有无数个，在考虑第i件物品的时候，不是考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个物品在当前空间大小时的价值*}}}优化:注意完全背包的顺序问题：因为每种背包都是无限的。当我们把i从1到N循环时，dp[v]表示容量为v在前i种背包时所得的价值，这里我们要添加的不是前一个背包，而第32页共78页第i次循环中的状态dp[i][v]是由状态dp[i-1][v-c[i]]递推而来。这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果dp[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果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页共78页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;}最长(不)上升或下降子序列先说O(N*N)的解法，第i个元素之前的最长递增子序列的长度要么是1（单独成一个序列），要么就是第i-1个元素之前的最长递增子序列加1，这样得到状态方程：1LIS[i]=max{1,LIS[k]+1}(∀k<i，arr[i]>arr[k])这样arr[i]才能在arr[k]的基础上构成一个新的递增子序列。123456789101112131415//题目连接:/JudgeOnline/problem.php?pid=17#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd;constintmaxn=10000+10;intdp[maxn];/*dp[i]记录到[0,i]数组的LIS*/intmaxx;/*LIS长度，初始化为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页共78页1617181920212223242526272829303132333435363738394041424344maxx=max(maxx,dp[i]);}returnmaxx;}/*递归输出LIS，因为数组dp还充当了“标记”作用*/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页共78页78910111213141516171819202122232425262728293031323334353637383940414243444546474849constintINF=0x3f3f3f3f;constintmaxn=100000+5;inta[maxn],dp[maxn],pos[maxn],fa[maxn];vector<int>ans;//用于最长非递减子序列种的lower_bound函数intcmp(inta,intb){returna<=b;}//最长上升子序列//dp[i]表示长度为i+1的上升子序列的最末尾元素找到第一个比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页共78页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;}最长公共子序列利用动态规划的方式解决，具有质，dp[i][j]记录序列Xi和Yi的最长公共子序列的长度，当i=0或j=0时，空序列时Xi和Yi的最长公共子序列，其余情况如下123456789//题目连接:/problem?id=1458#include<stdio.h>#include<iostream>#include<string.h>usingnamespacestd;constintmaxn=1000+10;intdp[maxn][maxn];intpath[maxn][maxn];//记录路径第37页共78页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页共78页有向无环图上的一种排序方式，我的这篇博客也讲解了一下。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页共78页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{///邻接表实现next_arc;///下一条边point;}Arc;///边的结构体，11121314Arcarc[maxn];121314intnode[maxn],vis[maxn],top[maxn];///储存每个顶点，node[i]表示第i个顶点指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页共78页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];///第一次是出发点，以后是下一个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)对于无向图来说度数为奇数的点个数为0，对于有向图来说每个点的入度(2)对于无向图来说，度数为奇数的的点可以有2个为起点另外一个为终点。对于有向图来说，可以存在两个点，判断连通的方式有DFS或者并查集，然后再判断一下是否满足条件即可，之前做的欧拉回路的几个好题在我的githu