首页 > 代码库 > HDU 5014 Number Sequence(2014 ACM/ICPC Asia Regional Xi'an Online) 题解

HDU 5014 Number Sequence(2014 ACM/ICPC Asia Regional Xi'an Online) 题解

2024-07-22 14:07:04   223人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5014

Number Sequence


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
 

HDU坑爹爆long long，换了__int64过了。想法很简单，把两个数二进制的0和1尽量补全，优先满足大的数就可以了。不过要找到区间。

代码：

#include <iostream>
#include <cstdio>
using namespace std;


__int64 n, a[100010];
struct right
{
    __int64 s, r, l;
}rt[1000];
__int64 getNear(__int64 x)
{
    __int64 z = 1;
    while(x)
    {
        x >>= 1;
        z <<= 1;
    }
    return z-1;
}
int main()
{
    while(~scanf("%I64d", &n))
    {
        __int64 m = n;
        rt[0].r = m;
        rt[0].s = getNear(m);
        rt[0].l = rt[0].s-rt[0].r;
        //cout << rt[0].l << " " << rt[0].r << " " << rt[0].s << endl;
        __int64 cnt = 0;
        while(1)
        {
            m = rt[cnt].l-1;
            if(m  < 0) break;
            cnt++;
            rt[cnt].r = m;
            rt[cnt].s = getNear(m);
            rt[cnt].l = rt[cnt].s-rt[cnt].r;
            //cout << rt[cnt].l << " " << rt[cnt].r << " " << rt[cnt].s << endl;
        }

        for(__int64 i = 0; i <= n; i++)
            scanf("%I64d", &a[i]);
            //a[i] = i;
        __int64 t = 0;

        for(__int64 i = 0; i <= n; i++)
            for(__int64 j = 0; j <= cnt; j++)
            {
                if(a[i] >= rt[j].l && a[i] <= rt[j].r)
                {
                    //cout << rt[j].l << " " << rt[j].r << " " << rt[j].s << endl;
                    //printf("%d ", rt[j].s-a[i]);
                    a[i] = rt[j].s-a[i];
                    t += rt[j].s;
                    break;
                }
            }
            printf("%I64d\n", t);
            for(__int64 i = 0; i < n; i++)
                printf("%I64d ", a[i]);
            printf("%I64d\n", a[n]);
    }

    return 0;
}


HDU 5014 Number Sequence(2014 ACM/ICPC Asia Regional Xi'an Online) 题解


联系
我们