首页 > 代码库 > hdu5014：number sequence对称思想

hdu5014：number sequence对称思想

2024-07-22 15:08:02   229人阅读

题目链接: 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 10000int p[17]={1,2 ,4 ,8 ,16 ,32, 64, 128, 256, 512 ,1024, 2048, 4096 ,8192 ,16384 ,32768,65536};bool vi[100010];int a[100010];int b[100010];int ans[100010];int main(){    int n;    while(scanf("%d",&n)!=EOF)    {        memset(vi,0,sizeof(vi));        long long res=0;        for(int i=0;i<=n;i++)            scanf("%d",a+i);        int k;        for(k=16;k>=0&&p[k]>n;k--);        while(k>=0)        {            int i=p[k]-1;            int j=p[k];            for(;i>=0&&j<=n;i--,j++)            {                if(vi[i]||vi[j])                    break;                res+=2*(j^i);                ans[i]=j;                ans[j]=i;                vi[i]=1;                vi[j]=1;            }            k--;        }        if(vi[0]==0)            ans[0]=0;        printf("%I64d\n",res);        for(int i=0;i<=n;i++)        {            printf("%d",ans[a[i]]);            if(i==n)                printf("\n");            else                printf(" ");        }    }    return 0;}

 

hdu5014：number sequence对称思想


联系
我们