Educational Codeforces Round 26 - A, B, C 思维-白红宇

Educational Codeforces Round 26 - A, B, C 思维

阅读量：6257 次

发布时间：2019-06-22

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

　　比赛链接： http://codeforces.com/contest/837

　　　　　　A： Text Volume 水

　　　　　　B： Flag of Berland

　　题目描述：给你一个字符矩阵，问能不能形成三条条纹

　　解题思路：纯细节题，中间因为马虎WA了几次

　　代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1#define mem0(a) memset(a,0,sizeof(a))#define meminf(a) memset(a,0x3f,sizeof(a))using namespace std;int cnt[9];char g[110][110];int main() { mem0(cnt); mem0(cnt); int n, m; cin >> n >> m; for( int i = 1; i <= n; i++ ) { for( int j = 1; j <= m; j++ ) { cin >> g[i][j]; if(g[i][j] == 'R') cnt[0]++; else if(g[i][j] == 'G') cnt[1]++; else cnt[2]++; } } if( (n%3!=0) && (m%3!=0) ) { cout<< "NO" << endl; return 0; } int flag1 = 1; int flag2 = 1; if( cnt[0] == cnt[1] && cnt[1] == cnt[2] ) { if( n % 3 == 0 ) { char temp0 = g[1][1]; for( int i = 1; i <= n / 3; i++ ) { for( int j = 1; j <= m; j++ ) { if( g[i][j] != temp0 ) { flag1 = 0; } } } char temp1 = g[n/3+1][1]; for( int i = n/3+1; i <= 2*n/3; i++ ) { for( int j = 1; j <= m; j++ ) { if(g[i][j] != temp1) { flag1 = 0; } } } } else flag1 =0; if( m % 3 == 0 ) {// cout << "=" << endl; char temp0 = g[1][1]; for( int i = 1; i <= n; i++ ) { for( int j = 1; j <= m/3; j++ ) { if(g[i][j] != temp0) { flag2 = 0; } } } char temp1 = g[1][m/3+1]; for( int i = 1; i <= n; i++ ) { for( int j = m/3+1; j <= 2*m/3; j++ ) { if(g[i][j] != temp1) { flag2 = 0; } } } } else flag2 = 0; if(flag1 + flag2 > 0) {// cout << flag1 << " " << flag2 << endl; cout << "YES" << endl; return 0; } else { cout << "NO" << endl; return 0; } } else { cout << "NO" << endl; } return 0;}

　　思考：自己还是不够细心，这题本来是不应该WA的

　　　　　　C： Two seals

　　题目描述：在一块长为a * b的矩形中放置两个矩形，所选的矩形从输入的N个矩形中选，要求必须放两个而且不能重叠，不能超边界

　　解题思路：这题我傻逼了.....暴力就行，开一个2 * n的数组，将旋转后的矩形也放进去，这样可以方便一点，然后判断两个矩形能不能放在一起， (a-y[i], b) 或者 (a, b-x[i]) 在这两个任意一个区间就可以，一步步更新最大值即可

　　代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1#define mem0(a) memset(a,0,sizeof(a))#define meminf(a) memset(a,0x3f,sizeof(a))using namespace std;int dp[220][220][4];int x[220];int y[220];int main() { int n; int a, b; cin >> n >> a >> b; for( int i = 1; i <= 2*n; i+=2 ) { cin >> x[i] >> y[i]; x[i+1] = y[i], y[i+1] = x[i]; } int ans = 0; for( int i = 1; i <= 2*n; i++ ) { for( int j = 1; j <= 2*n; j++ ) { if( i != j && !((i&1)&&j==i+1) && !(!(i&1)&&j==i-1) ) { int temp1 = a-y[i]; int temp2 = b-x[i]; if( x[j] <= temp1 && y[j] <= b && temp2 >= 0 ) { ans = max( ans, x[i]*y[i]+x[j]*y[j] ); } if( x[j] <= a && y[j] <= temp2 && temp1 >= 0 ) { ans = max( ans, x[i]*y[i]+x[j]*y[j] ); } } } } cout << ans << endl; return 0;}

　　思考：一开始傻逼了......去向用DP做，状态转移方程半天没有想出来，原因就是DP的时候如果是当前是第j个，就必须知道上一个是放了一个还是没放，很复杂，再说n这么小不暴力傻逼啊

　　比赛总结：只做出了A, B , C 剩下的也是可以补的题，今天要补补了........

转载于:https://www.cnblogs.com/FriskyPuppy/p/7358681.html

你可能感兴趣的文章