HDU5014Number Sequence(贪心)

题目链接

题目大意：
给出n，然后给出一个数字串，长度为n + 1， 范围在[0, n - 1].然后要求你找出另外一个序列B，满足上述的要求，而且使得t = A0^B0 + Ai + 1 ^ Bi + 1 + ... + An ^ Bn 最大。

解题思路：
对于一个数字进行异或，要求结果最大的话，那么取这个数字的二进制互补数字是最好的情况，而且能够发现每次找到一个数字和相应的互补的数字都会是一段区间。就这样一段一段区间的去寻找每一个点相应的最好的匹配点。

代码：

      
        
          #
          
            include
          
           <cstdio>
        
        
          #
          
            include
          
           <cstring>
        
        
          typedef
        
        
          long
        
        
          long
        
         ll;

        
          const
        
        
          int
        
         N = 
        
          1e5
        
         + 
        
          5
        
        ;

        
          const
        
        
          int
        
         M = 
        
          20
        
        ;


        
          int
        
         num[N];

        
          int
        
         Map[N];

        
          int
        
         n;
ll t[M];


        
          void
        
         init () {

    t[
        
          0
        
        ] = 
        
          1
        
        ;
    
        
          for
        
         (
        
          int
        
         i = 
        
          1
        
        ; i <= M; i++)
        t[i] = t[i - 
        
          1
        
        ] * 
        
          2
        
        ;
}


        
          int
        
         main () {

    init();
    
        
          while
        
         (
        
          scanf
        
         (
        
          "%d"
        
        , &n) == 
        
          1
        
        ) {

        
        
          for
        
         (
        
          int
        
         i = 
        
          0
        
        ; i <= n; i++)
            
        
          scanf
        
         (
        
          "%d"
        
        , &num[i]);

        
        
          int
        
         rear = n;
        
        
          int
        
         front;
        ll ans = 
        
          0
        
        ;

        
          // printf ("%lld\n", t[M - 1]);
        
        
          while
        
         (rear >= 
        
          0
        
        ) {

            
        
          for
        
         (
        
          int
        
         i = 
        
          0
        
        ; i < M; i++)
                
        
          if
        
         (t[i] > rear) {
                    front = t[i] - rear - 
        
          1
        
        ;
                    
        
          break
        
        ;        
                }

            
        
          for
        
         (
        
          int
        
         i = 
        
          0
        
        ; i < (rear - front + 
        
          1
        
        ) / 
        
          2
        
        ; i++) {

                Map[rear - i] = front + i;
                Map[front + i] = rear - i;
            }

            
        
          if
        
         (rear == front)
                Map[rear] = front;
            rear = front - 
        
          1
        
        ;
        }

        
        
          for
        
         (
        
          int
        
         i = 
        
          0
        
        ; i <= n; i++)
            ans += num[i] ^ Map[num[i]];
        
        
          printf
        
         (
        
          "%lld\n"
        
        , ans);
        
        
          for
        
         (
        
          int
        
         i = 
        
          0
        
        ; i < n; i++)
            
        
          printf
        
        (
        
          "%d "
        
        , Map[num[i]]);
        
        
          printf
        
         (
        
          "%d\n"
        
        , Map[num[n]]);
    }
    
        
          return
        
        
          0
        
        ;
}