首页 > 代码库 > HDU 5014

HDU 5014

2024-07-22 13:51:45   220人阅读

Number Sequence

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

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

● ai ∈ [0,n] 
● ai ≠ aj( i ≠ j )

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

t = (a0 ⊕ b0) + (a1 ⊕ b1) +···+ (an ⊕ bn)


(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 ≤ 105), The second line contains a0,a1,a2,...,an.
 

 

Output
For each case, output two lines.The first line contains the maximum integrating degree t. The second line contains n+1 integers b0,b1,b2,...,bn. There is exactly one space between bi and bi+1(0 ≤ i ≤ n - 1). Don’t ouput any spaces after bn.
 

 

Sample Input
4
2 0 1 4 3
 

 

Sample Output
20
1 0 2 3 4
 
 
题目意思：
给出a序列，求使t最大的b序列。
 
思路：
为使t最大，a和b的数两两互补。  所以咱们需要找0-n的每项的互补数，然后hash匹配记录下来，输入a的时候就输出对应的b.
怎么找互补数呢？  
假设n为9, 0----9的数和二进制数如下：
0    0
1    1
2    10
3    11
4    100
5    101
6    110
7    111
8    1000
9    1001
 
发现了没  ，从后向前  当一个数为2^k，且这个数位置为 l 处，设最后面没有匹配的数位置在r处，   那么位于 [l,r]的数与[2*l-r-1,l-1]内的数成镜面对称匹配即  l与 l-1匹配, l+1与 l-2匹配。。。r与2*l-r-1匹配。
那么从后向前for一下一一hash匹配就行了。
 
代码：
#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;#define N 100005int suan(int n){    int ans=1;    for(int i=1;i<=n;i++) ans*=2;    return ans;}main(){    int ha[N], n, a[N];    int i, j, k;    while(scanf("%d",&n)==1){        memset(ha,0,sizeof(ha));        for(i=18;i>=0;i--){   //寻找2^k中的k   因为以2^k所在位置为l进行匹配操作的，i=18时就已经超过n的最大值了            if(suan(i)<=n){                j=i;break;            }        }        int l=j, r=n;                long long ans=0;        while(l>0){   把0---n所有数字进行匹配            int ll;            for(ll=r,i=suan(l)-(r-suan(l)+1);i<=suan(l)-1;i++){                ha[i]=ll;                ha[ll]=i;                ll--;            }            r=suan(l)-(r-suan(l)+1)-1;            if(r<=0) break;            for(i=18;i>=0;i--){            if(suan(i)<=r){                l=i;break;            }          }        }        if(ha[0]==ha[1]&&ha[0]==0) ha[0]=1,ha[1]=0;  //上面while可能跳过1了。。。其实while改一下就行了..懒得改就加上了这个        for(i=0;i<=n;i++){            scanf("%d",&a[i]);        }        for(i=0;i<=n;i++){            ans+=(ha[i]^i);        }        printf("%I64d\n",ans);        printf("%d",ha[a[0]]);        for(i=1;i<=n;i++){            printf(" %d",ha[a[i]]);        }        cout<<endl;    }}

 

HDU 5014


联系
我们