题目连接：https://vjudge.net/contest/171661#overview
A题:
题目要求：找子集，使子集最长，且子集里的点不互相连接
思路：找规律
代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <string> #include <queue> #include <map> #include <vector> const int maxn=10000+10; using namespace std; long long f[77]; int main() { f[1]=1; f[2]=2; f[3]=2; for(int i=4;i<=76;i++) f[i]=f[i-2]+f[i-3]; int n; while(~scanf("%d",&n)) printf("%lld ",f[n]); return 0; }
B题：
题目要求：给你一段程序，求那个程序里函数的递归次数
思路：dp，可以发现没个问题都可以被分成多个子问题，然后找子问题和母问题的联系，还要用到大整数
代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <string> #include <queue> #include <map> #include <string> #include <vector> const int maxn=10000+10; using namespace std; typedef unsigned long long datatype; string sum(string s1,string s2) { if(s1.length()<s2.length()) { string temp=s1; s1=s2; s2=temp; } int i,j; for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--) { s1[i]=char(s1[i]+(j>=0?s2[j]-'0':0)); //注意细节 if(s1[i]-'0'>=10) { s1[i]=char((s1[i]-'0')%10+'0'); if(i) s1[i-1]++; else s1='1'+s1; } } return s1; } datatype c; datatype trib(int n, unsigned int back) { datatype sum=0; int i; c++; if(n<=0) return 0; if(n==1) return 1; for(i=1;i<=back;i++) sum+=trib(n-i,back); return sum; } datatype ans[65][65]; int main() { int n,m; //memset(ans,1,sizeof(ans)); for(int i=0;i<=61;i++) { for(int j=0;j<=61;j++) { if(i==0||j==0||i==1) { ans[i][j]=1; continue; } for(int k=1;k<=j;k++) { if(i-k<=0) ans[i][j]++; else ans[i][j]+=ans[i-k][j]; } ans[i][j]++; } } int cnt=0; while(~scanf("%d %d",&n,&m)) { c=0; //trib(n,m); //cout<<c<<endl; if(n>60) continue; printf("Case %d: ",++cnt); if(n<=0||m<=0) { cout<<"1"<<endl; continue; } cout<<ans[n][m]<<endl; } return 0; }
C题：
思路：找规律加大整数
代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <string> #include <queue> #include <map> #include <string> #include <vector> const int maxn=10000+10; using namespace std; long long f[77]; string sum(string s1,string s2) { if(s1.length()<s2.length()) { string temp=s1; s1=s2; s2=temp; } int i,j; for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--) { s1[i]=char(s1[i]+(j>=0?s2[j]-'0':0)); //注意细节 if(s1[i]-'0'>=10) { s1[i]=char((s1[i]-'0')%10+'0'); if(i) s1[i-1]++; else s1='1'+s1; } } return s1; } string ans[1005]; int main() { ans[0]="1"; ans[1]="2"; ans[2]="3"; for(int i=3;i<=1004;i++) { ans[i]=sum(ans[i-1],ans[i-2]); } int n; while(~scanf("%d",&n)) cout<<ans[n]<<endl; return 0; }
D题：
题目要求：
求捡到垃圾的最大数量，和捡到这个垃圾的最大方案数，然后任意输出一种方案
代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <queue> #include <stack> #include <map> #define rep(i,a,b) for(int i=a;i<(b);++i) #define de(x) cout<<#x<<"="<<x<<endl #define ll long long using namespace std; int n,m; int mx,sum; int v[105][105]; ll dp[105][105]; ll path[105][105]; struct node { int x,y; }pre[105][105]; void out(int x,int y) { if(pre[x][y].x==-1&&pre[x][y].y==-1&&v[x][y]) { cout<<(x-1)*m+y; if(dp[x][y]!=mx) cout<<" "; return ; } out(pre[x][y].x,pre[x][y].y); if(v[x][y]) { cout<<(x-1)*m+y; if(dp[x][y]!=mx) cout<<" "; } } int main() { int cas=0; while(~scanf("%d %d",&n,&m)) { mx=0;sum=0; if(n==-1&&m==-1) break; memset(v,0,sizeof(v)); memset(dp,0,sizeof(dp)); memset(path,0,sizeof(path)); rep(i,0,105)rep(j,0,105) pre[i][j].x=i,pre[i][j].y=j; int x,y; while(1) { scanf("%d %d",&x,&y); if(x==0&&y==0) break; v[x][y]=1; } rep(i,1,n+1) rep(j,1,m+1) { dp[i][j]=max(dp[i-1][j],dp[i][j-1])+v[i][j]; if(v[i][j]&&dp[i][j]==1)//如果是一个垃圾的话，把它的上一个节点弄成-1，-1，这样我们递归输出的时候有尽头，把他的方案数弄成1 { path[i][j]=1; pre[i][j].x=-1,pre[i][j].y=-1; continue; } if(dp[i-1][j]>dp[i][j-1]) pre[i][j].x=i-1,pre[i][j].y=j; else pre[i][j].x=i,pre[i][j].y=j-1; } rep(i,1,n+1)//暴力求解方案数 ，我的30ms，同学的0ms，还不懂怎么优化 { rep(j,1,m+1) { if(v[i][j]) { rep(k,i,n+1) rep(g,j,m+1) { if(k==i&&g==j) continue; if(v[k][g]&&dp[k][g]-dp[i][j]==1) path[k][g]+=path[i][j]; } } } } mx=dp[n][m]; rep(i,1,n+1) rep(j,1,m+1) { if(dp[i][j]==mx&&v[i][j]) sum+=path[i][j];//总的方案数，就是到任意一个最大垃圾的方案数总和 } if(!dp[n][m]) { printf("CASE#%d: %d %d ",++cas,0,0); continue; } printf("CASE#%d: %d %d ",++cas,dp[n][m],sum); out(n,m); cout<<endl; } return 0; }
E题：
题目要求：只能往两个方向走，有些路不通，求起点到中点的方案数
思路：每个点的方案数都可以有两个方向到这里的方案数相加，如果哪个方向的路堵住了，就不加那个方向过来的
坑点：一个点可能有多个方向堵住了！！！
代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <string.h> #include <queue> #include <map> #include <string> #include <vector> const int maxn=10000+10; using namespace std; long long dp[40][40]; int v[40][40][2][2]; int main() { int T; scanf("%d",&T); int n,m; int bex,bey; int enx,eny; int a,b; char ch; while(T--) { memset(v,0,sizeof(v)); memset(dp,0,sizeof(dp)); scanf("%d",&n); scanf("%d %d %d %d",&bex,&bey,&enx,&eny); scanf("%d",&m); dp[bex][bey]=1; for(int i=0;i<m;i++) { scanf("%d %d %c",&a,&b,&ch); if(ch=='S') v[a][b][0][1]=2; if(ch=='W') v[a][b][0][0]=1; if(ch=='N') v[a][b][1][1]=4; if(ch=='E') v[a][b][1][0]=3; } /*for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cout<<v[i][j]<<" "; } cout<<endl; }*/ for(int i=bex;i<=n;i++) { for(int j=bey;j<=n;j++) { if(i==bex&&j==bey) continue; if(!v[i][j][0][0]&&!v[i-1][j][1][0]) dp[i][j]+=dp[i-1][j]; if(!v[i][j][0][1]&&!v[i][j-1][1][1]) dp[i][j]+=dp[i][j-1]; //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl; } } /*for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cout<<dp[i][j]; } cout<<endl; }*/ //cout<<dp[enx][eny]<<endl; printf("%lld ",dp[enx][eny]); } return 0; }
F题：
G题：
题目要求：求组合数
思路：杨辉三角加大整数
代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <string> #include <queue> #include <map> #include <string> #include <vector> const int maxn=10000+10; using namespace std; string sum(string s1,string s2) { if(s1.length()<s2.length()) { string temp=s1; s1=s2; s2=temp; } int i,j; for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--) { s1[i]=char(s1[i]+(j>=0?s2[j]-'0':0)); //注意细节 if(s1[i]-'0'>=10) { s1[i]=char((s1[i]-'0')%10+'0'); if(i) s1[i-1]++; else s1='1'+s1; } } return s1; } string ans[2100][26000]; int main() { ans[0][1]="1"; int flag=0; for(int i=1;i<=100;i++) { for(int j=0;j<=i;j++) { if(i==j) ans[i][j]="1"; else if(j==0) ans[i][j]="1"; else ans[i][j]=sum(ans[i-1][j],ans[i-1][j-1]); } } int n,m; while(~scanf("%d %d",&n,&m)) { if(n==0&&m==0) break; printf("%d things taken %d at a time is ",n,m); cout<<ans[n][m]<<" exactly."<<endl; } return 0; }
H题：
题目要求：输出杨辉三角，当有出现大于10的60次方（61位）的，输出那一行以后不输出下一行（结束）
思路：大整数
坑点：最后一行也要回车
代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <string> #include <queue> #include <map> #include <string> #include <vector> const int maxn=10000+10; using namespace std; string sum(string s1,string s2) { if(s1.length()<s2.length()) { string temp=s1; s1=s2; s2=temp; } int i,j; for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--) { s1[i]=char(s1[i]+(j>=0?s2[j]-'0':0)); //注意细节 if(s1[i]-'0'>=10) { s1[i]=char((s1[i]-'0')%10+'0'); if(i) s1[i-1]++; else s1='1'+s1; } } return s1; } string ans[2100][26000]; int main() { ans[1][1]="1"; int flag=0; cout<<"1"<<endl; for(int i=2;;i++) { for(int j=1;j<=i;j++) { if(i==j) ans[i][j]="1"; else if(j==1) ans[i][j]="1"; else ans[i][j]=sum(ans[i-1][j],ans[i-1][j-1]); cout<<ans[i][j]; if(j!=i) cout<<" "; if(ans[i][j].size()>=61) flag=1; } cout<<endl; if(flag) break; } /*int n; while(~scanf("%d",&n)) cout<<ans[n]<<" "<<ans[n].size()<<endl;*/ return 0; }