首页 > 代码库 > HDU 5014 Number Sequence(贪心）

HDU 5014 Number Sequence(贪心）

2024-07-22 18:24:34   228人阅读

当时想到了贪心，但是不知为何举出了反列。。。。我是逗比，看了点击打开链接。才发现我是逗比。

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
 

Source
2014 ACM/ICPC Asia Regional Xi‘an Online

枚举贪心即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<map>
using namespace std;
typedef long long LL;
const int maxn=1e5+100;
LL a[maxn];
LL d[maxn];
int main()
{
    LL n;
    while(~scanf("%I64d",&n))
    {
        for(LL i=0;i<=n;i++)
            scanf("%I64d",&a[i]);
        memset(d,-1,sizeof(d));
        LL ans=0;
        for(LL i=n;i>=0;i--)
        {
            LL t=0;
            if(d[i]==-1)
            {
                for(LL j=0;;j++)
                {
                    if(!(i&(1<<j)))  t+=(1<<j);
                    if(t>=i)
                    {
                        t-=(1<<j);
                        break;
                    }
                }
                ans+=(i^t)*2;
                d[i]=t;
                d[t]=i;
            }
        }
        printf("%I64d\n",ans);
        for(LL i=0;i<=n;i++)
        printf(i==n?"%I64d\n":"%I64d ",d[a[i]]);
    }
    return 0;
}


HDU 5014 Number Sequence(贪心）


联系
我们