ACM 算法模板2

哈嘻嘟-浙江省第七届程序-2010-4-17 目 录 2 一、图论 2 1.1.最小生成树类prim算法 4 1.2.拓扑排序 5 1.3.最短源路径Folyd实现 6 1.4.关键路径实现算法 8 1.5.二分图最大匹配的匈牙利算法 9 1.6.并查集 11 二、动规 11 2.1.求最长子序列 12 2.2.求解最长升序列长度及子序列 13 2.3.完全背包问 14 2.4.0-1背包问题 15 2.5.母函数DP算法求组合数 17 2.6.滚动数组求回文串问题 18 三、贪心 18 3.1.时间安排问题 19 3.2.求最大子段和 20 3.3.贪心求最少非递减序列数 21 四、数论 21 4.1.简单求Cnk问题 21 4.2.巧求阶乘位数 22 4.3.线性算法求素数 22 五、其他 22 5.1.采用位操作递归求解示例 23 5.2.Stack和Queue用法 24 5.3.map使用详解 25 5.4.字典树建立与查找 26 5.5.KMP匹配算法 28 5.6.后缀数组求最长连续公共子序列长度 30 5.7.循环字符串最小位置表示及同构判断 32 5.8.求哈夫曼树编码长度 34 5.9.堆排序算法 35 5.10.线段树着色问题 39 六、附： 39 6.1.C++最值常量 39 6.2.类型转换 39 6.3.String常用函数举例 40 6.4.C++常用头文件 一、图论 1.1.最小生成树类prim算法 1.1.1下标从1开始 #include #include #include using namespace std; #define SIZE 101 #define MAXSIZE 10201 int n,nline;/*n 个点,nline行关系*/ int in[SIZE]; struct Point{ int x,y;/*编号从1开始*/ int v;/*根据实际情况更改类型*/ }p[MAXSIZE];/*n*(n-1)/2*/ int cmp(Point a,Point b){ return a.v #include #include using namespace std; #define SIZE 101 #define MAXSIZE 10201 int n,nline;/*n 个点,nline行关系*/ int in[SIZE]; struct Point{ int x,y;/*编号从1开始*/ int v;/*根据实际情况更改类型*/ }p[MAXSIZE];/*n*(n-1)/2*/ int cmp(Point a,Point b){ return a.v #include #include #define M 501 using namespace std; int map[M][M],degree[M]; int ne;/*个数*/ void topo(){ int i,j,k; for(i=0;ine){break;}不是拓扑结构 if(i)printf(" "); printf("%d",j); degree[j]=-1; for(k=1;k<=ne;k++){ degree[k]-=map[j][k]; } } printf("\n"); } int main(){ int a,b,i,j,nline;/*nline行*/ while(scanf("%d%d",&ne,&nline)!=EOF){ memset(map,0,sizeof(map)); memset(degree,0,sizeof(degree)); while(nline--){ scanf("%d%d",&a,&b); map[a][b]=1;/*a to b*/ } for(i=1;i<=ne;i++){ for(j=1;j<=ne;j++){ if(map[i][j])degree[j]++; } } topo();/*拓扑*/ } return 0; } 1.3.最短源路径Folyd实现 #include #include #include #define M 201 using namespace std; int n,map[M][M],start,end; void folyd(){ int i,j,k; for(i=0;iv){//一个点到另一个有多条路 map[b][a]=map[a][b]=v; } } scanf("%d%d",&start,&end); folyd(); if(map[start][end]!=-1){ printf("%d\n",map[start][end]); } else printf("-1\n"); } return 0; } 1.4.关键路径实现算法 #include #include #include #define M 501 using namespace std; int map[M][M],degree[M],dp[M]; int ne;/*个数*/ int topoplus(){ int i,j,k,maxnum; for(i=0;ine){break;}不是拓扑结构 degree[j]=-1; for(k=1;k<=ne;k++){ if(map[j][k]){ if(map[j][k]+dp[j]>dp[k]){ dp[k]=map[j][k]+dp[j]; } degree[k]--; } } } for(i=0;i<=ne;i++){ if(dp[i]>maxnum){ maxnum=dp[i]; } } return maxnum; } int main(){ int a,b,v,i,j,nline;/*nline行*/ while(scanf("%d%d",&ne,&nline)!=EOF){ memset(map,0,sizeof(map)); memset(degree,0,sizeof(degree)); memset(dp,0,sizeof(dp)); while(nline--){ scanf("%d%d%d",&a,&b,&v); map[a][b]=v;/*a to b，v>0*/ } for(i=1;i<=ne;i++){ for(j=1;j<=ne;j++){ if(map[i][j])degree[j]++; } } printf("%d\n",topoplus());/*拓扑改进*/ } return 0; } 1.5.二分图最大匹配的匈牙利算法 #include #include #define N 301 using namespace std; int isuse[N]; //

记录

混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载

y中节点是否使用 int lk[N]; //记录当前与y节点相连的x的节点 int mat[N][N];//记录连接x和y的边，如果i和j之间有边则为1，否则为0 int gn,gm; //二分图中x和y中点的数目 int can(int t){ int i; for(i=1;i<=gm;i++){//下标从1开始 if(isuse[i]==0 && mat[t][i]){ isuse[i]=1; if(lk[i]==-1 || can(lk[i])){ lk[i]=t; return 1; } } } return 0; } int MaxMatch(){ int i,num=0; memset(lk,-1,sizeof(lk)); for(i=1;i<=gn;i++){ memset(isuse,0,sizeof(isuse)); if(can(i))num++; } return num; } int main(){ int t,i,j,k,tmp; scanf("%d",&t); while(t--){ scanf("%d%d",&gn,&gm); memset(mat,0,sizeof(mat));//主要得到mat这个数组 for(i=1;i<=gn;i++){ scanf("%d",&k); for(j=1;j<=k;j++){ scanf("%d",&tmp); mat[i][tmp]=1;//注意从1开始 } } if(MaxMatch()==gn){ printf("YES\n"); } else printf("NO\n"); } return 0; } /* In: 2 3 3 3 1 2 3 2 1 2 1 1 3 3 2 1 3 2 1 3 1 1 Out: YES NO */ 1.6.并查集 #include #include using namespace std; const int N=1010; int pre[N]; void Merge(int x,int y){ int i,t,rx=x,ry=y; while(pre[rx]!=-1)//搜索x的树根 rx=pre[rx]; while(pre[ry]!=-1)//搜索y的树根 ry=pre[ry]; i=x; //压缩x while(pre[i]!=-1){ t=pre[i]; pre[i]=rx; i=t; } i=y;//压缩y while(pre[i]!=-1){ t=pre[i]; pre[i]=rx; i=t; } if(ry!=rx)//合并 pre[ry]=rx; return; } int main(){ int x,y,i,ans,n,m; while(scanf("%d",&n)&&n){ scanf("%d",&m); memset(pre,-1,sizeof(pre)); for(i=0;i #include #define M 1001 using namespace std; char a[M],b[M]; int dp[M+1][M+1],lena,lenb; void init(){ int i,j; for(i=0;i<=lena;i++){ for(j=0;j<=lenb;j++){ dp[i][j]=0; } } } int cmax(int x,int y){ return x>y?x:y; } int main(){ int i,j,len; while(scanf("%s",a)!=EOF){ scanf("%s",b); init(); //下面这步很重要，否则会超时 lena=strlen(a); lenb=strlen(b); for(i=0;i #include #define M 1001 using namespace std; int a[M],dp[M]; void init(int n){ int i; for(i=0;i=0;i--){ for(j=n-1;j>i;j--){ if(a[i]dp[i]){ dp[i]=dp[j]+1; } if(dp[i]>maxlen)maxlen=dp[i]; } } } return maxlen; } void showlis(int n,int maxlen){ int i; for(i=0;i #include #include using namespace std; int type[]={150,200,350};//种类 int dp[10001]; int max(int a,int b){ return a>b?a:b; } int main(){ int t,n,i,j; scanf("%d",&t); while(t--){ scanf("%d",&n); memset(dp,0,sizeof(dp)); for(i=0;i<3;i++){ for(j=type[i];j<=n;j++){ //剩余容量为j时装的东西量最大 dp[j]=max(dp[j],dp[j-type[i]]+type[i]); } } printf("%d\n",n-dp[n]); } return 0; } 2.4.0-1背包问题 #include #include #include #define M 1002 using namespace std; int val[M],wei[M],dp[M][M]; int cmax(int a,int b){ return a>b?a:b; } int main(){ int t,n,w,i,j; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&w); for(i=1;i<=n;i++){ scanf("%d",&val[i]); } for(i=1;i<=n;i++){ scanf("%d",&wei[i]); } memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++){ for(j=0;j<=w;j++){ if(j>=wei[i]) dp[i][j]=cmax(dp[i-1][j-wei[i]]+val[i],dp[i-1][j]); else dp[i][j]=dp[i-1][j]; } } printf("%d\n",dp[n][w]); } return 0; } 2.5.母函数DP算法求组合数 2.5.1.求母函数各系数值DP #include #define M 17 #define MAX 305 using namespace std; int c1[MAX],c2[MAX],add[M+1];//add[]保存M种类 void init(){ int i; for(i=1;i<=M;i++){ add[i]=i*i; } } int solve(int n) { int i,j,k; //c1[k],c2[k]表示展开式中x^k的系数 memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2)); c1[0]=c2[0]=1; //使用前i种币时的情况，也即母函数展开前i个多项式的乘积 for(i=1;i<=M;i++){ //求新的多项式中的系数 for(j=0;j #include #include using namespace std; bool dp[250002]; int val[101],num[101];//对应的值和数量 int main(){ int n,i,j,sum,k; while(scanf("%d",&n)&&n>0){ sum=0; for(i=0;i=0;j--){ if(!dp[j]){ for(k=1;k<=num[i]&&k*val[i]<=j;k++){ dp[j]|=dp[j-k*val[i]]; } } } } for(i=sum/2;i>=0;i--){ if(dp[i]){ printf("%d %d\n",sum-i,i); break; } } } return 0; } /* in: 2 10 1 20 1 3 10 1 20 2 30 1 -1 out: 20 10 40 40 */ 2.6.滚动数组求回文串问题 #include #include #include #define M 5001 using namespace std; char str[M],rstr[M]; int dp[2][M];//滚动DP int cmax(int x,int y){ return x>y?x:y; } int main(){ int n,i,j,s1,s2; while(scanf("%d",&n)!=EOF){ scanf(" %s",str); //反转字符数组 for(i=0;i #include #include #define M 101 using namespace std; int n; struct Point{ int s,e; }p[M]; int cmp(Point a,Point b){ if(a.s==b.s) return a.e=start&&p[i].e<=end){ start=p[i].s; end=p[i].e; } else if(p[i].s>=end){ count++; end=p[i].e; } } return count; } int main(){ int i; while(scanf("%d",&n)&&n){ for(i=0;i using namespace std; int main(){ int t,n,i,a[100002]; int beg,end,x,y,cursum,maxsum; cin>>t; while(t--){ cin>>n; for(i=0;i>a[i]; } beg=end=1; cursum=maxsum=a[0]; x=y=1; for(i=1;imaxsum){ maxsum=cursum; beg=x; end=i+1; } } cout< #include #include using namespace std; int a[1001]; int main(){ int n,i,j,len,count,high; while(scanf("%d",&n)!=EOF){ for(i=0;i using namespace std; int main(){ int n,k,i; double sum; while(cin>>n>>k){ if(n==0&&k==0)break; if(k>n-k)k=n-k; sum=1; for(i=1;i<=k;i++){ sum*=(double)(n-k+i)/i*1.000000000001;//必需要乘 } cout<<(int)sum< #include using namespace std; const double pi=acos(-1.0);//NOTES:pi const double e= 2.71828182845904523536028747135266249775724709369995957; int main() { long long n,tt; cin>>tt; while (tt--) { cin>>n; long long ans=(long long) ((double)log10(sqrt(2*pi*n))+n*log10(n/e))+1; cout< #include using namespace std; unsigned short in[50001],ste;/*用16位的ste保存16种状态*/ unsigned short power[]= {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768}; int n,m,maxnum,i,j; void dfs(int s,int count){ if(count>maxnum)maxnum=count; for(i=s;i说明

关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书