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
        
        ;
}