暑期集训7/18-白红宇

暑期集训7/18

阅读量：6573 次

发布时间：2019-06-24

本文共 5262 字，大约阅读时间需要 17 分钟。

题目连接：https://vjudge.net/contest/171661#overview

A题:

题目要求：找子集，使子集最长，且子集里的点不互相连接

思路：找规律

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             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\n",f[n]); return 0;}

B题：

题目要求：给你一段程序，求那个程序里函数的递归次数

思路：dp，可以发现没个问题都可以被分成多个子问题，然后找子问题和母问题的联系，还要用到大整数

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              const int maxn=10000+10;using namespace std;typedef unsigned long long datatype;string sum(string s1,string s2){ if(s1.length()
              
               =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<
               
                <
                
                 60) continue; printf("Case %d: ",++cnt); if(n<=0||m<=0) { cout<<"1"<

C题：

思路：找规律加大整数

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              const int maxn=10000+10;using namespace std;long long f[77];string sum(string s1,string s2) { if(s1.length()
              
               =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<
               
                <

D题：

题目要求：

求捡到垃圾的最大数量，和捡到这个垃圾的最大方案数，然后任意输出一种方案

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #define rep(i,a,b) for(int i=a;i<(b);++i)#define de(x) cout<<#x<<"="<
            
             <
             
              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\n",++cas,0,0); continue; } printf("CASE#%d: %d %d ",++cas,dp[n][m],sum); out(n,m); cout<

E题：

题目要求：只能往两个方向走，有些路不通，求起点到中点的方案数

思路：每个点的方案数都可以有两个方向到这里的方案数相加，如果哪个方向的路堵住了，就不加那个方向过来的

坑点：一个点可能有多个方向堵住了！！！

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              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

F题：

G题：

题目要求：求组合数

思路：杨辉三角加大整数

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              const int maxn=10000+10;using namespace std;string sum(string s1,string s2){ if(s1.length()
              
               =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<
               
                <<" exactly."<

H题：

题目要求：输出杨辉三角，当有出现大于10的60次方（61位）的，输出那一行以后不输出下一行（结束）

思路：大整数

坑点：最后一行也要回车

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              const int maxn=10000+10;using namespace std;string sum(string s1,string s2){ if(s1.length()
              
               =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"<
               
                =61) flag=1; } cout<