CSU Monthly 2013 Oct 中南大学ACM月赛 - c++编程基础

题目很好，比较活跃，有难度，同时对基础要求又比较好，总体感觉这题目做起来挺不错的，没做出的去补一下

http://acm.csu.edu.cn/OnlineJudge/problem.php id=1318

数学题：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; int main() { ll n; while(scanf("%lld",&n) == 1) { ll ans = 1; ll num = 1; while((num*2) - 1 < n) { ans++; num *= 2; } printf("%lld\n",ans); } return EXIT_SUCCESS; }

http://acm.csu.edu.cn/OnlineJudge/problem.php id=1321

spfa，记录最短路径的同时记录妹子的数量

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; int n,m; bool vis[10000 + 5]; int dis[10000 + 5]; int ans[10000 + 5]; int num [10000 + 5]; int head[10000 + 5]; typedef struct Node { int from,to; int nex; int w; }; Node edge[100000 + 5]; int tot; void clear() { memset(num,0,sizeof(num)); memset(edge,0,sizeof(edge)); memset(head,-1,sizeof(head)); tot = 0; } void add(int u,int v,int w) { edge[tot].from = u; edge[tot].to = v; edge[tot].nex = head[u]; edge[tot].w = w; head[u] = tot++; } int spfa(int s,int e) { memset(vis,false,sizeof(vis)); for(int i=0;i<=n;i++) dis[i] = inf; for(int i=1;i<=n;i++) ans[i] = inf; dis[s] = 0; ans[s] = num[s]; vis[s] = true; queue
                    
                      q; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int i=head[u];i!=-1;i=edge[i].nex) { int v = edge[i].to; if(dis[u] + edge[i].w < dis[v]) { dis[v] = edge[i].w + dis[u]; ans[v] = ans[u] + num[v]; if(!vis[v]) { vis[v] = true; q.push(v); } } else if(dis[v] == dis[u] + edge[i].w) { if(ans[v] < ans[u] + num[v]) { ans[v] = ans[u] + num[v]; if(!vis[v]) { vis[v] = true; q.push(v); } } } } } if(dis[n] == inf) return -1; else return ans[n]; } int main() { while(scanf("%d %d",&n,&m) == 2) { clear(); for(int i=1;i<=n;i++) scanf("%d",&num[i]); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d %d %d",&u,&v,&w); add(u,v,w); add(v,u,w); } int answer = spfa(1,n); printf("%d\n",answer); } return EXIT_SUCCESS; }

http://acm.csu.edu.cn/OnlineJudge/problem.php id=1320

仔细写几个，不能遗漏，发现是卡特兰数，因为要取模涉及到整除问题，所以要用扩展欧几里德求乘法逆元来避免这个问题

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; const ll MOD = 1000000007; ll dp[10000 + 5]; ll n; ll exgcd(ll a, ll b, ll &x, ll &y) { if(!b) { x = 1; y = 0; return a; } ll r = exgcd(b, a%b, y, x); y -= a/b*x; return r; } ll inv(ll a, ll m) //求逆元直接模版套上 { ll x,y,gcd = exgcd(a, m, x, y); if(x < 0) x += m; return x; } void clear() { memset(dp,0,sizeof(dp)); dp[1] = 1; dp[2] = 2; for(int i=3;i<10001;i++) { dp[i] = ((dp[i-1]*(4*i-2)%MOD) * ((inv(i+1,MOD) + MOD)%MOD))%MOD; } } int main() { clear(); while(scanf("%lld",&n) == 1) { printf("%lld\n",dp[n]); } return EXIT_SUCCESS; }

http://acm.csu.edu.cn/OnlineJudge/problem.php id=1326

符合分组背包，所以用分组背包做一下，注意分组要求

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; vector
                    
                      G[1000 + 5]; int n,V,q; int dp[1000 + 5]; int p[1000 + 5],w[1000 + 5]; int father[1000 + 5]; void clear() { memset(dp,0,sizeof(dp)); for(int i=0;i<1005;i++) father[i] = i; for(int i=0;i<1005;i++) G[i].clear(); } int find(int x) { if(father[x] != x) return find(father[x]); return x; } void merge(int x,int y) { int dx = find(x); int dy = find(y); if(dx!=dy) { father[dx] = dy; } } int main() { while(scanf("%d %d %d",&n,&V,&q) == 3) { clear(); for(int i=0;i
                     
                      =w[i];j--) if (dp[j - w[i]] + p[i] > dp[j]) dp[j] = dp[j - w[i]] + p[i]; } for (int i=0;i
                      
                       =0;k--) { for (int j=0;j
                       
                         k) continue; if (dp[k - w[G[i][j]]] + p[G[i][j]] > dp[k]) dp[k] = dp[k - w[G[i][j]]] + p[G[i][j]]; } } } printf("%d\n",dp[V]); } return EXIT_SUCCESS; }