Codeforces Round #186 (Div. 2)A、B、C、D、E

A.Ilya and Bank Account

Ilya得到了一个礼物，可以在删掉银行账户最后和倒数第二位的数字（账户有可能是负的），也可以不做任何处理。

  

   

    

     

    
    

     

      //codeforces 313A 
     
    
   

    

     

    
    

     

      //2013-05-31-13.47
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          int n;
     
    
   

    

     

    
    

     

          scanf("%d", &n);
     
    
   

    

     

    
    

     

          if (n)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              if (n >= 0)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  printf("%d\n", n);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

              else
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  n = -n;
     
    
   

    

     

    
    

     

                  int a = n/10;
     
    
   

    

     

    
    

     

                  int b = n/100 * 10 + n%10;
     
    
   

    

     

    
    

     

                  printf("%d\n", -min(a, b));
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

          return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

B.Ilya and Queries

给你一个字符串，然后有M个询问，寻问的是从l到r之间有多少对字符串满足 s[i] == s[i+1]。

简单的树状数组题目

  

   

    

     

    
    

     

      //codeforces 313 B
     
    
   

    

     

    
    

     

      //2013-05-31-14.15
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      const int maxn = 100005;
     
    
   

    

     

    
    

     

      char s[maxn];
     
    
   

    

     

    
    

     

      int a[maxn];
     
    
   

    

     

    
    

     

      int n;
     
    
   

    

     

    
    

     

      inline int lowbit(int x)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          return x&-x;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void update(int x)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          while (x <= n)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              a[x] += 1;
     
    
   

    

     

    
    

     

              x += lowbit(x);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int getsum(int x)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          int sum = 0;
     
    
   

    

     

    
    

     

          while (x)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              sum += a[x];
     
    
   

    

     

    
    

     

              x -= lowbit(x);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

          return sum;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          while (scanf("%s", s) != EOF)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              int m, l, r;
     
    
   

    

     

    
    

     

              n = strlen(s);
     
    
   

    

     

    
    

     

              memset(a, 0, sizeof(a));
     
    
   

    

     

    
    

     

              for (int i = 0; i < n-1; i++)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  if (s[i] == s[i+1])
     
    
   

    

     

    
    

     

                      update(i+1);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

              scanf("%d", &m);
     
    
   

    

     

    
    

     

              while (m--)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  scanf("%d %d", &l, &r);
     
    
   

    

     

    
    

     

                  printf("%d\n", getsum(r-1) - getsum(l-1));
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

          return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

C.Ilya and Matrix

给你4^n个数，让你放进那个2^n * 2^n的矩阵里让这个矩阵beauty值最大，beauty值的计算方法题里说了。。。

The beauty of a 2n × 2n-sized matrix is an integer, obtained by the following algorithm:

Find the maximum element in the matrix. Let's denote it as m.
If n = 0, then the beauty of the matrix equals m. Otherwise, a matrix can be split into 4 non-intersecting 2n - 1 × 2n - 1-sized submatrices, then the beauty of the matrix equals the sum of number m and other four beauties of the described submatrices.

As you can see, the algorithm is recursive

贪心吧，贪心就行，排个序解决了

  

   

    

     

    
    

     

      //codeforces 313c
     
    
   

    

     

    
    

     

      //2013-06-03-15.55
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      const int maxn = 2*1000006;
     
    
   

    

     

    
    

     

      __int64 a[maxn];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      bool cmp(int x, int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          return x > y;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          int n;
     
    
   

    

     

    
    

     

          while (scanf("%d", &n) != EOF)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              for (int i = 1; i <= n; i++)
     
    
   

    

     

    
    

     

                  scanf("%I64d", &a[i]);
     
    
   

    

     

    
    

     

              sort(a+1, a+n+1, cmp);
     
    
   

    

     

    
    

     

              int x = n;
     
    
   

    

     

    
    

     

              __int64 ans = 0;
     
    
   

    

     

    
    

     

              while (x)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  for (int i = 1; i <= x; i++)
     
    
   

    

     

    
    

     

                      ans += a[i];
     
    
   

    

     

    
    

     

                  x /= 4;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

              printf("%I64d\n", ans);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

          return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

D.Ilya and Roads

E.Ilya and Two Numbers

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/9000153