程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CF 191 div2

CF 191 div2

編輯:C++入門知識

A.Flipping Game 題目總結出來就是要求求出一個【i,j】區間,其中0的個數與1的個數是所有區間相差最大的。   題目有個trick,操作一定要執行,所以全是1的時候直接輸出n-1。     [cpp]   int a[MAX];   int num0,num1;   int main() {          int n,i,j,k;       int ans = 0;       cin >> n;       for(i=1; i<=n; i++) {           scanf("%d",&a[i]);           if(a[i] == 1)               ans++;       }       if(ans == n) {           cout << n-1 << endl;           return 0;       }       int span = 0;       for(i=1; i<=n; i++) {           for(j=1; j<=n; j++) {               num0 = 0;               num1 = 0;               for(k=i; k<=j; k++) {                   if(a[k] == 0) num0++;                   if(a[k] == 1) num1++;                  }               span = max(span,num0 - num1);           }       }       cout << span + ans << endl;       return 0;   }     int a[MAX]; int num0,num1; int main() {       int n,i,j,k;     int ans = 0;     cin >> n;     for(i=1; i<=n; i++) {         scanf("%d",&a[i]);         if(a[i] == 1)             ans++;     }     if(ans == n) {         cout << n-1 << endl;         return 0;     }     int span = 0;     for(i=1; i<=n; i++) {         for(j=1; j<=n; j++) {             num0 = 0;             num1 = 0;             for(k=i; k<=j; k++) {                 if(a[k] == 0) num0++;                 if(a[k] == 1) num1++;               }             span = max(span,num0 - num1);         }     }     cout << span + ans << endl;     return 0; }     B.Hungry Sequence   special judge。。。所以打個素數表直接輸出即可     [cpp]   int flag[MAX];   void prime()   {       flag[1] = 1;       for(int i=2; i<=MAX; i++) {           if(flag[i] == 0) {               for(int j=2*i; j<=MAX; j+=i)                   flag[j] = 1;           }       }   }   int main() {          int n,i;       prime();       cin >> n;       int cnt = 0;       for(i=2;;i++) {           if(flag[i] == 0) {               cnt++;               if(cnt == n) {                   cout << i << endl;                   break;               }               else {                   cout << i << ' ';               }           }       }       return 0;   }     int flag[MAX]; void prime() {     flag[1] = 1;     for(int i=2; i<=MAX; i++) {         if(flag[i] == 0) {             for(int j=2*i; j<=MAX; j+=i)                 flag[j] = 1;         }     } } int main() {       int n,i;     prime();     cin >> n;     int cnt = 0;     for(i=2;;i++) {         if(flag[i] == 0) {             cnt++;             if(cnt == n) {                 cout << i << endl;                 break;             }             else {                 cout << i << ' ';             }         }     }     return 0; }       C.Magic Five   快速冪,擴展歐幾裡得求逆元,熟練這兩個就好做了....可是我不熟     [cpp]   char str[MAX];   __int64 k;   int sum[MAX];   __int64 model(__int64 a,__int64 n,__int64 b) {       __int64 t = a;       __int64 ans = 1;       while(n) {           if(n & 1) {               ans = ans * t % b;           }           n >>= 1;           t = t*t % b;       }       return ans;   }   int main() {       scanf("%s",str);       scanf("%I64d",&k);       int len = strlen(str);       __int64 ans = 0;       __int64 q = 0;       for(int i=0; i<len; i++) {           if(str[i] == '0' || str[i] == '5') {               q = (q + model(2,i,mod)) % mod;            }       }       ans = model(2,len*k,mod) % mod - 1;       ans = (ans*model(model(2,len,mod) -1,mod - 2,mod)) % mod;       ans = (q*ans) % mod;       printf("%I64d\n",ans);       return 0;   }     char str[MAX]; __int64 k; int sum[MAX]; __int64 model(__int64 a,__int64 n,__int64 b) {     __int64 t = a;     __int64 ans = 1;     while(n) {         if(n & 1) {             ans = ans * t % b;         }         n >>= 1;         t = t*t % b;     }     return ans; } int main() {     scanf("%s",str);     scanf("%I64d",&k);     int len = strlen(str);     __int64 ans = 0;     __int64 q = 0;     for(int i=0; i<len; i++) {         if(str[i] == '0' || str[i] == '5') {             q = (q + model(2,i,mod)) % mod;          }     }     ans = model(2,len*k,mod) % mod - 1;     ans = (ans*model(model(2,len,mod) -1,mod - 2,mod)) % mod;     ans = (q*ans) % mod;     printf("%I64d\n",ans);     return 0; }       D.Block Tower   帶有YY的爆搜,滿足讓一個聯通塊內只有一個blue房子其他都是red房子     [cpp]   char map[MAX][MAX];   int vis[MAX][MAX];   struct node {       int x,y;       char dir;   } p[1000005];   int dirx[4] = {1,-1,0,0};   int diry[4] = {0,0,1,-1};   int ans = 0 ,i,j;   void dfs(int x,int y) {          p[ans].dir = 'B';       p[ans].x = x;       p[ans].y = y;       ans++;       vis[x][y] = 1;       for(int k=0; k<4; k++) {           int xx = x + dirx[k];           int yy = y + diry[k];           if(!vis[xx][yy] && map[xx][yy] == '.')               dfs(xx,yy);       }       if(x != i || j != y){           p[ans].dir = 'D';       p[ans].x = x;       p[ans].y = y;       ans++;       p[ans].dir = 'R';       p[ans].x =x;       p[ans].y = y;       ans++;       }   }      int main() {       int n,m;       scanf("%d%d",&n,&m);       for(i=0; i<n; i++) {           scanf("%s",map[i]);       }       for(i=0; i<n; i++) {           for(j=0; j<m; j++) {               if(map[i][j] == '.' && !vis[i][j]) {                   dfs(i,j);               }           }       }       printf("%d\n",ans);       for(i=0; i<ans; i++) {           printf("%c %d %d\n",p[i].dir,p[i].x+1,p[i].y+1);       }       return 0;   }     char map[MAX][MAX]; int vis[MAX][MAX]; struct node {     int x,y;     char dir; } p[1000005]; int dirx[4] = {1,-1,0,0}; int diry[4] = {0,0,1,-1}; int ans = 0 ,i,j; void dfs(int x,int y) {       p[ans].dir = 'B';     p[ans].x = x;     p[ans].y = y;     ans++;     vis[x][y] = 1;     for(int k=0; k<4; k++) {         int xx = x + dirx[k];         int yy = y + diry[k];         if(!vis[xx][yy] && map[xx][yy] == '.')             dfs(xx,yy);     }     if(x != i || j != y){         p[ans].dir = 'D';     p[ans].x = x;     p[ans].y = y;     ans++;     p[ans].dir = 'R';     p[ans].x =x;     p[ans].y = y;     ans++;     } }   int main() {     int n,m;     scanf("%d%d",&n,&m);     for(i=0; i<n; i++) {         scanf("%s",map[i]);     }     for(i=0; i<n; i++) {         for(j=0; j<m; j++) {             if(map[i][j] == '.' && !vis[i][j]) {                 dfs(i,j);             }         }     }     printf("%d\n",ans);     for(i=0; i<ans; i++) {         printf("%c %d %d\n",p[i].dir,p[i].x+1,p[i].y+1);     }     return 0; }  

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved