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\n", 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("\n"); 52 } 53 return 0; 54 }
?
)
_oracle)
