hdu5014：number sequence对称思想

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

题目大意：给定数组 a[]={0,1,2......n} 求一个数组b[] 元素也为0.....n 但顺序与a[]不同

使得 sum(ai ^ bi)最大

注意到2^k =100000(k个0) 2^k-1 =11111(k个1)

那么 (2^k) ^ (2^k-1)=111111(k+1个1)等于 2^(k+1)-1 同样的有 (2^k+1) ^ (2^k-2)=2^(k+1)-1；

此时显然元素中的"1"得到了最为充分的利用，所得结果即为最大值

所以只需要考虑每一个小于等于n的 2的整数次方，对称的进行分配即可

代码如下

#include <iostream>

#include <stdio.h>

#include <memory.h>

#include<string.h>

#include<algorithm>

#include<string>

#include<ctype.h>

using namespace std;

#define MAXN 10000

int p[]={, , , , ,, , , ,  ,, ,  , , ,,};

bool vi[];

int a[];

int b[];

int ans[];

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        memset(vi,,sizeof(vi));

        long long res=;

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

            scanf("%d",a+i);

        int k;

        for(k=;k>=&&p[k]>n;k--);

        while(k>=)

        {

            int i=p[k]-;

            int j=p[k];

            for(;i>=&&j<=n;i--,j++)

            {

                if(vi[i]||vi[j])

                    break;

                res+=*(j^i);

                ans[i]=j;

                ans[j]=i;

                vi[i]=;

                vi[j]=;

            }

            k--;

        }

        if(vi[]==)

            ans[]=;

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

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

        {

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

            if(i==n)

                printf("\n");

            else

                printf(" ");

        }

    }

    return ;

}

巴特西

hdu5014：number sequence对称思想

最新文章

热门文章