Educational Codeforces Round 24-A B C D 思维-白红宇

Educational Codeforces Round 24-A B C D 思维

阅读量：5927 次

发布时间：2019-06-19

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

　　比赛链接： https://vjudge.net/contest/179452#overview

　　　　　　A： Diplomas and Certificates 水题

　　代码：

#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))typedef long long ll;using namespace std;//const int INF = 0x3fffffff;ll n, k;int main() { cin >> n >> k; ll mw = n / 2; if( mw / (k+1) == 0 ) { cout << "0 0 " << n << endl; return 0; } else { cout << mw / (k+1) << " " << mw / (k+1) * k << " " << n-mw/(k+1)-mw/(k+1)*k << endl; } return 0;}

　　　　　　B： Permutation Game

　　题目描述：你有一组排列，做了m个操作，从某个数开始跳到a[i]就一次跳a[i]个数，问给你m组操作，是否可以推出排列

　　解题思路：由于跳的步数等于ans[i] 所以 ans[i] = a[i+1] - a[i] 这里有一些细节需要处理一下，还有就是这是一个排列，所以如果一个ans[i]已经确定了，这个ans[i]就不能再被修改，可能还会有一些数字没有跳到，这样就枚举从1 ~ n中没有出现过的数儿就行了，原来以为这里还会有填充的数字比n多这个坑的，结果没有， woc! 又犯傻比！当时要是判定这个可就真的傻逼了，本来就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))typedef long long ll;using namespace std;//const int INF = 0x3fffffff;int n, m;int a[110];int ans[110];int vis[110];int main() { cin >> n >> m; memset(a, -1, sizeof(a)); memset(ans, -1, sizeof(ans)); mem0(vis); for( int i = 1; i <= m; i++ ) { cin >> a[i]; } for( int i = 1; i < m; i++ ) { int temp = a[i+1] - a[i]; if( temp == 0 ) { temp = n; /*cout << "===" << a[i] << endl; */} if( temp > 0 ) {} if( temp < 0 ) temp += n; if( ans[a[i]] != -1 && temp != ans[a[i]] ) { cout << "-1" << endl; return 0; } ans[a[i]] = temp; } for( int i = 1; i <= n; i++ ) { if( ans[i] != -1 && vis[ans[i]] > 0 ) { cout << "-1" << endl; return 0; } else if( ans[i] != -1 && vis[ans[i]] == 0 ){ vis[ans[i]] = 1; } } int cnt = 1; for( int i = 1; i <= n; i++ ) { if( ans[i] == -1 ) { while( vis[cnt] != 0 ) { cnt++; } ans[i] = cnt; vis[cnt] = 1; } } for( int i = 1; i <= n; i++ ) { if( i == 1 ) cout << ans[i]; else cout << " " << ans[i]; } cout << endl; return 0;}

　　思考：自己在那个ans[i]已经确定但不能被改变，但是完全可以相同啊这里WA了一次，还有就是这个能不能被改变WA了一次

　　　　　　C：我操我没看C啊， C题面好长，就直接看的D，一会儿补

#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))typedef long long ll;using namespace std;//const int INF = 0x3fffffff;const int maxn = 1e6 + 100;struct node { int x1, y1, x2, y2; node() {} void init( int _x1, int _y1, int _x2, int _y2 ) { x1 = _x1, x2 = _x2, y1 = _y1, y2 = _y2; }};node a[maxn];int xl[maxn], xr[maxn], yl[maxn], yr[maxn];int main() { int d, n, m; mem0(xl), mem0(xr), mem0(yl), mem0(yr); scanf( "%d%d%d", &d, &n, &m ); for( int i = 1; i <= d; i++ ) { int t1, t2, t3, t4; scanf( "%d%d%d%d", &t1, &t2, &t3, &t4 ); a[i].init(t1, t2, t3, t4); xl[min(a[i].x1, a[i].x2)]++; xr[max(a[i].x1, a[i].x2)]++; yl[min(a[i].y1, a[i].y2)]++; yr[max(a[i].y1, a[i].y2)]++; } int cntl, cntr, cntt, cntb; scanf( "%d%d%d%d", &cntl, &cntr, &cntt, &cntb ); for( int i = 1; i <= n; i++ ) xl[i] += xl[i-1]; for( int i = 1; i <= m; i++ ) yl[i] += yl[i-1]; for( int i = n; i >= 1; i-- ) xr[i] += xr[i+1]; for( int i = m; i >= 1; i-- ) yr[i] += yr[i+1]; for( int i = 1; i <= d; i++ ) { int t = yl[max(a[i].y1, a[i].y2)-1]; int b = yr[min(a[i].y1, a[i].y2)+1]; int l = xl[max(a[i].x1, a[i].x2)-1]; int r = xr[min(a[i].x1, a[i].x2)+1]; if( a[i].x1 == a[i].x2 ) { // 不在同一行， 左包含了右， 右包含了左， 需要-- l--; r--; } if( a[i].y1 == a[i].y2 ) { t--; b--; } if( l == cntl && r == cntr && t == cntt && b == cntb ) { printf( "%d\n", i ); return 0; } } printf( "-1\n" ); return 0;}

　　挖槽，困得不行了， C有没想到l-- , r--, t--, b--那部分，一直得不到正确答案，菜的要死

　　　　　　D： Multicolors cars

　　题目描述：给你一组序列，再给你一个数，要求你选出一个在任何位置上在i位之前出现的次数都大于等于给定数的出现的次数的数

　　解题思路：如果没出现过给定数的话，随机一个数就行了，如果给定数出现在第一个的话就直接输出-1就行，在输入的同时统计各个字符出现的次数，只要有一次字符c[i]不符合条件，以后它就不用考虑了，然后第一个满足的数直接BREAK掉就可以了，我现在出了一点儿BUG，代码一会儿粘贴，总结一会儿写

　　代码：

#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))typedef long long ll;using namespace std;//const int INF = 0x3fffffff;const int maxn = 1e6+100;int a[maxn];int pre[maxn];int ans[maxn];int main() { mem0(a); mem0(pre); int n, A; scanf( "%d%d", &n, &A ); int flag = 0; mem0(ans); for( int i = 1; i <= n; i++ ) { scanf( "%d", a+i ); if( a[i] == A ) { flag = 1; } if( pre[a[i]] < pre[A] ) { ans[a[i]] = -1; } pre[a[i]]++; } if( a[1] == A ) { printf( "-1\n" ); return 0; } if( flag == 1 ) { for( int i = 1; i <= n; i++ ) { if( pre[a[i]] >= pre[A] && ans[a[i]] != -1 && a[i] != A ) { printf( "%d\n", a[i] ); return 0; } } printf( "-1\n" ); return 0; } else { printf( "%d\n", a[1] ); return 0; } }

　　思考：刚刚健身完回来写了一发，全删了重新写的，就过了，肯定之前哪儿有漏洞自己又找不到

　　总结：自己这场比赛只做出了A， B两道水题，其实D题不难，但是不知道卡在哪里了......当时不仔细啊现在把C题补了吧，今晚儿也别干别的了

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

你可能感兴趣的文章