首页 > 代码库 > hdu-5014-Number Sequence-XiAn网络赛1008-水题

hdu-5014-Number Sequence-XiAn网络赛1008-水题

思路:既然是求两个数的异或运算之和,且由于数字不重复,那么肯定两个数异或的结果数字越大越好,即异或后从ai二进制的最高位后全是1。

具体思路看代码:

AC代码:

 1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <vector> 5 #include <algorithm> 6 using namespace std; 7 int bit[17]; 8 int brr[100005]; 9 int n;10 void init()11 {12     bit[0] = 1;13     for(int i = 0; i <= 16; i++) {14         bit[i+1] = 2<<i;15     }16 }17 int arr[100005];18 void deal(int x)19 {20     for(int i = 0; i < n+10; i++) arr[i] = -1;21     arr[0] = 0;22     int k, le, xx;23     while(x != 0){24         if(x <= 0) return;25         int pos = upper_bound(bit, bit+18, x) - bit - 1;26         if(pos == 0) {27             arr[0] = 1; arr[1] = 0;28             return;29         }30         xx = x;31         if(pos == 1) k = 0x00000003 ^ x;32         else if(pos == 2) k = 0x00000007 ^ x;33         else if(pos == 3) k = 0x0000000f ^ x;34         else if(pos == 4) k = 0x0000001f ^ x;35         else if(pos == 5) k = 0x0000003f ^ x;36         else if(pos == 6) k = 0x0000007f ^ x;37         else if(pos == 7) k = 0x000000ff ^ x;38         else if(pos == 8) k = 0x000001ff ^ x;39         else if(pos == 9) k = 0x000003ff ^ x;40         else if(pos == 10) k = 0x000007ff ^ x;41         else if(pos == 11) k = 0x00000fff ^ x;42         else if(pos == 12) k = 0x00001fff ^ x;43         else if(pos == 13) k = 0x00003fff ^ x;44         else if(pos == 14) k = 0x00007fff ^ x;45         else if(pos == 15) k = 0x0000ffff ^ x;46         else if(pos == 16) k = 0x0001ffff ^ x;47         le = k;48         x = k - 1;49         for(int i = xx; i >= k; i--) arr[i] = le++;50     }51 }52 int main()53 {54     init();55     while(scanf("%d", &n) != EOF) {56         deal(n);57         long long ans = 0;58         for(int i = 0; i <= n; i++) {59             int a; scanf("%d", &a);60             brr[i] = arr[a];61             ans += a ^ arr[a];62         }63         printf("%I64d\n%d", ans, brr[0]);64         for(int i = 1; i <= n; i++) {65             printf(" %d", brr[i]);66         }67         printf("\n");68     }69     return 0;70 }
View Code

总结:QAQ比赛的时候看错题意了。。。。忽略了数字不重复的条件,导致想了好久。。。。

hdu-5014-Number Sequence-XiAn网络赛1008-水题