[欲張り][ビット演算]hdoj 5014

1482 ワード

おおよその意味
列の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
",ans); for(i=0;i<n;i++){ printf("%I64d ",opt[num[i]]); } printf("%I64d
",opt[num[n]]); } return 0; }