Number Sequence
Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
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 0 ⊕ b 0 ) + (a 1 ⊕ b 1 ) +···+ (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 5 ), The second line contains a 0 ,a 1 ,a 2 ,...,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 0 ,b 1 ,b 2 ,...,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
题解：
要使xor值最大，那么应该是xor的结果每一位上全部为1，例如n=3,00与11,01与10,10与01,11与00， 贪心算法，从最大的那个数匹配开始，尽量满足大的数字。
i从n开始， 所以1不断左移，直到匹配的数比不比i小为止。判断某一位上是0还是1，需要用到&运算符，若i的第k位上是0，那么i&(1<<k)的值就是0。
以下是代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <algorithm>#include <cctype>#include <sstream>#include <queue>#include <stack>#include <stack>#include <map>using namespace std;#define F(i,s,e) for(int i = s;i<e;i++)#define FA(i,s,e) for(int i=s;i>e;i--)#define ss(x) scanf("%d",&x)#define s64(x) scanf("%I64d",&x)#define write() freopen("1.in","r",stdin)#define W(x) while(x)typedef long long LL;LL a[100005];LL b[100005];int main(){ write(); LL sum,n; W(s64(n)!=EOF){ sum=0; for(LL i=0;i<=n;i++)s64(a[i]); for(LL i=0;i<=n;i++)b[i]=-1; for(LL i=n;i>=0;i--){ if(b[i]!=-1)continue; LL t=0,k=0; W(1){ if((i&(1<<k))==0)t+=1<<k;//依次按位取反 if(t>=i){ //直到比i大 t-=1<<k; break; } k++; } b[i]=t; b[t]=i; sum+=(t^i)*2; } printf("%I64d\n",sum); for(LL i=0;i<n;i++) printf("%I64d ",b[a[i]]);//输出对应位置的值 printf("%I64d\n",b[a[n]]); }} |
Spring-1-H Number Sequence（HDU 5014）解题报告及测试数据
原文：http://www.cnblogs.com/gzdaijie/p/4312061.html