Number Sequence（二进制）

Number Sequence

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1886    Accepted Submission(s): 561
Special Judge

Problem Description

There is a special number sequence which has n+1 integers. For each number in sequence, we have two rules:

● a_i ∈ [0,n]
● a_i ≠ a_j( i ≠ j )

For sequence a and sequence b, the integrating degree t is defined as follows(“⊕” denotes exclusive or):

t = (a₀ ⊕ b₀) + (a₁ ⊕ b₁) +···+ (a_n ⊕ b_n)

(sequence B should also satisfy the rules described above)

Now give you a number n and the sequence a. You should calculate the maximum integrating degree t and print the sequence b.

 

 

Input

There are multiple test cases. Please process till EOF.

For each case, the first line contains an integer n(1 ≤ n ≤ 10⁵), The second line contains a₀,a₁,a₂,...,a_n.

 

 

Output

For each case, output two lines.The first line contains the maximum integrating degree t. The second line contains n+1 integers b₀,b₁,b₂,...,b_n. There is exactly one space between b_i and b_i+1(0 ≤ i ≤ n - 1). Don’t ouput any spaces after b_n.

 

 

Sample Input

4

2 0 1 4 3

 

 

Sample Output

 

20

1 0 2 3 4

 

     题意：

     给出 N ，后给出 N 个数，它是一个 0 ~ N 的排列，找出一个序列对应式子异或和最大。

 

     思路：

     将数变为二进制考虑，会发现每个数都会有对应有一个 “ 使之变为该二进制位数全为 1 ” 的数。这样子就能解决问题了，总和就是化为全为 1 时候对应的十进制值，对应的数就是这个和减去这个值的得数。

 

     AC：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <cmath>

using namespace std;

typedef long long ll;

ll num[100005];
ll num1[100005];

ll Bit (ll ans) {
    ll bb = 0;
    while (ans) {
        ++bb;
        ans /= 2;
    }
    return bb;
}

int main() {

    int n;

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

        memset(num1, -1, sizeof(num1));

        ll sum = 0;
        for (ll i = n; i >= 0; --i) {
            if (num1[i] == -1) {
                ll bb = Bit(i);
                ll ans = pow(2, bb) - 1;
                sum += ans * 2;
                num1[i] = ans - i;
                num1[ans - i] = i;
            }
        }

        if (num1[0] == -1) num1[0] = 0;

        printf("%I64d\n", sum);
        for (int i = 0; i <= n; ++i) {
            printf("%I64d", num1[num[i]]);
            i == n ? printf("\n") : printf(" ");
        }
    }

    return 0;
}