Codeforces Round #359 div2-白红宇

Codeforces Round #359 div2

阅读量：4977 次

发布时间：2019-06-12

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

Problem_A(CodeForces 686A):

题意：

\[ 有n个输入， +\space d_i代表冰淇淋数目增加d_i个， -\space d_i表示某个孩纸需要d_i个，如果你现在手里没有\space d_i个冰淇淋，那么这个孩纸就会失望的离开。\]

你初始有x个冰淇淋。

问最后有多少个孩纸失望的离开了。

思路：

模拟就好了，判断当前的数目是否足够。

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;#define LL long long#define INF 0x3f3f3f3f#define MOD 1000000007#define eps 1e-6#define MAXN 1000000#define MAXM 100#define dd {cout<<"debug"<
                    
                     = l; i --)#define doe(i, x) for(i = 1; i <= x; i ++)int n;LL x;int main(){ LL res, child_num; scanf("%d %I64d", &n, &x); res = x; child_num = 0; LL total_num = 0; LL d; char op[2]; for(int i = 0; i < n ;i ++) { scanf("%s %I64d", op, &d); if(op[0] == '+') res += d; else if(op[0] == '-') { total_num ++; if(d <= res) { res -= d; child_num ++; } } } printf("%I64d %I64d\n", res, total_num - child_num); return 0;}

Problem_B(CodeForces 686B):

题意：

你能做如下操作：

[l, r]保证长度为偶数。

\[ 将(l, l+1), \cdots ,(r-1, r)交换。\]

你最后的目的是将其交换成一个非递减的数列。

请将交换过程中的l, r输出。

思路：

n<100, 可以很暴力的去冒泡，因为最差的情况也不会超过100*100次。

而题目给的是2W次以内。

昂，我比较傻逼的写了一个贪心。

每次去找最长的能够交换的区间，然后进行操作，一直到不能操作为止。

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;#define LL long long#define INF 0x3f3f3f3f#define MOD 1000000007#define eps 1e-6#define MAXN 110#define MAXM 100#define dd {cout<<"debug"<
                    
                     = l; i --)#define doe(i, x) for(i = 1; i <= x; i ++)int n;int a[MAXN];int find_(int l, int r, bool is_l){ if(l > r) return l - 1; for(int i = l; i + 1 <= r; i +=2) if((a[i] <= a[i + 1] && is_l == false) || (a[i] > a[i + 1] && is_l == true)) return is_l ? i : i - 1; return is_l ? -1 : ((r - l + 1) % 2 == 0 ? r : r - 1); }void move_(int l, int r){ for(int i = l; i < r; i += 2) { int temp = a[i]; a[i] = a[i + 1]; a[i + 1] = temp; }}void show(){ for(int i = 1; i <= n; i ++) printf("%d ", a[i]); printf("\n");}void deal(){ int l = 1, r; while(true) { l = find_(1, n, true); if(l == -1) { l = find_(2, n, true); if(l == -1) return ; } r = find_(l + 2, n, false); if(r == -1) return; // printf("==>%d %d\n", l, r); move_(l, r); // show(); // pa printf("%d %d\n", l, r); }} int main(){ bool flag = true; a[0] = 0; scanf("%d", &n); flag = n == 1; for(int i = 1; i <= n; i ++) { scanf("%d", &a[i]); if(a[i] > a[i - 1] && n && i > 1) flag = false; } if(!flag) deal(); return 0;}

Problem_C(CodeForces 686C):

题意：

给你n, m，将其转换成对应的7进制

然后从转换后的[0, n-1]中任选一个数，再从转换后[0,m-1]中任选一个数。

必须要保证每个数字只出现一次，即不会有重复的数字。

问你这样的组合有多少种。

思路：

因为是7进制，而且要保证每位都不一样， 7进制只有7个数而已，所以如果两个数的长度超过了7，肯定不行。

\[ 再则，要注意：转换成对应的7进制！比如8, 转换成7进制，是11, 那么这8个数就成了[00, 01, 02, \cdots , 10].而不是[0, 1, 2, 3, \cdots , 10]\]

\[ 所以可以先求出它们的长度len_n, len_m，然后判断长度。\]

枚举0~n, 0~m。将其分解成对应的7进制后判断是否出现相同数字即可。

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;#define LL long long#define INF 0x3f3f3f3f#define MOD 1000000007#define eps 1e-6#define MAXN 1000000#define MAXM 10#define dd {cout<<"debug"<
                    
                     = l; i --)#define doe(i, x) for(i = 1; i <= x; i ++)int n, m;int left_len = 0, right_len = 0;int check(int x, int y){ int used[MAXM] = {0}; for(int i = x, k = 0; k < left_len; k ++, i /= 7) used[i % 7] += 1; for(int i = y, k = 0; k < right_len; k ++, i /= 7) used[i % 7] += 1; for(int i = 0; i < 7; i ++) if(used[i] > 1) return 0; return 1;}int main(){ scanf("%d %d", &n, &m); left_len = right_len = 1; for(int i = 7; i < n; i *= 7) left_len ++; for(int i = 7; i < m; i *= 7) right_len ++; int ans = 0; if((left_len + right_len) <= 7) { for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++) ans += check(i, j); } printf("%d\n", ans); return 0;}

Orz 有点头痛，剩下的等明天再补。今天元气大伤

转载于:https://www.cnblogs.com/By-ruoyu/p/5674712.html

你可能感兴趣的文章