[贪心][位运算]hdoj 5014

大致题意

给出一列n个数a[n]，每个数属于0--n，切每个数字只出现一次

求出一个符合上面条件的b[n]使得a[i]^b[i]的和最大

 

大致思路

找出规律就很简单

比如a[i]=6 也就是 110  那就让b[i]为001与其配对

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int vis[100005];
__int64 num[100005],opt[100005];
__int64 cal(__int64  a){
    __int64 res=0,b,i=0;
    while(a){
        b=a^1;
        b=b%2;
        res+=b<<i;
        a/=2;
        i++;
    }
    return res;
}
int main(){
    __int64 n,i,a,ans;
    while(scanf("%I64d",&n)!=EOF){
        ans=0;
        for(i=0;i<=n;i++){
            scanf("%I64d",&num[i]);
        }
        memset(vis,0,sizeof(vis));
        for(i=n;i>=0;i--){
            if(!vis[i]){
                a=cal(i);
                if(!vis[a]){
                    ans+=2*(i^a);
                    opt[i]=a;
                    opt[a]=i;
                    vis[i]=vis[a]=1;
                }
            }
        }
        printf("%I64d\n",ans);
        for(i=0;i<n;i++){
            printf("%I64d ",opt[num[i]]);
        }
        printf("%I64d\n",opt[num[n]]);
    }
    return 0;
}