异或运算（2014西安网络赛H题）

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

题意：给出范围N，给出0-N的一个排列a。让你求出另外一个排列b，使 t = a1 ^ b1 + a2 ^ b2 + ...+an ^ bn（^表示异或）最大。并求出最大的t。

思路：首先，我们要注意到的是，一定存在解，且解不唯一。同时，因为是异或操作，要想得到最大值，我们必须让ai,bi对应的二进制表示，0和1错开，这样才不会使值减少。

这样，我们要构造出错开的0和1的二进制表达即可。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

const int maxn=100100;

long long a[maxn],ans[maxn];

int main()

{

    int n;

    while(cin>>n)

    {

        memset(ans,-1,sizeof(ans));

        for(int i=0;i<=n;i++)

            scanf("%d",&a[i]);

        long long maxnum,xornum;

        long long masnum=0;

        for(int i=n;i>=0;i--)

            if(ans[i]==-1)

        {

            long long x=log2(i)+1;

            maxnum=(1<<x)-1;

            xornum=maxnum^i;

            if(ans[xornum]==-1)

            {

                ans[i]=xornum;

                ans[xornum]=i;

                masnum+=2*maxnum;

            }

        }

        printf("%I64d\n",masnum);

        for(int i=0;i<=n;i++)

            printf("%I64d ",ans[a[i]]);

        printf("\n");

    }

    return 0;

}

巴特西

异或运算（2014西安网络赛H题）

最新文章

热门文章