2014 网选 5014 Number Sequence（异或）

 1 /*
 2     题意：a, b两个序列，规定由[0, n]区间的数！
 3     求 a[i] ^ b[i] 的和最大！ 
 4     
 5     思路：如果数字 n的二进制有x位， 那么一定存在一个数字m，使得n^m的所有二进制位
 6     都是1，也就是由x位1！这样下去的到的值就是最大值！ 
 7     
 8 */ 
 9 #include<iostream>
10 #include<cstring>
11 #include<cstdio>
12 #include<algorithm>
13 #define N 100005 
14 using namespace std;
15 
16 int b[N], vis[N];
17 
18 
19 int pos[N];
20 
21 
22 int main(){
23     int n;
24     while(scanf("%d", &n)!=EOF){
25         int x, y;
26         for(int i=0; i<=n; ++i){
27             scanf("%d", &x);
28             pos[x]=i;
29         }
30         memset(vis, 0, sizeof(vis));
31         long long sum=0;
32         for(int i=n; i>=0; --i){
33              y=x=i;
34              if(vis[x]) continue;
35              int tmp=1;
36              while(y){
37                  x^=tmp;
38                  tmp<<=1;
39                  y>>=1;
40             }
41             vis[x]=vis[i]=1;
42             sum+=2*(x^i);
43             b[pos[i]]=x;
44             b[pos[x]]=i;
45         }
46         //printf("%lld
", sum);
47         cout<<sum<<endl;
48         printf("%d", b[0]);
49         for(int i=1; i<=n; ++i)
50             printf(" %d", b[i]);
51         printf("
");
52     }
53     return 0;
54 }