[欲張り][ビット演算]hdoj 5014
1482 ワード
おおよその意味
列のn個の数a[n]を与えて、各数は0-nに属して、各数字を切るのは一回だけ現れます
上の条件に合致するb[n]を求めてa[i]^b[i]の和を最大にする
大まかな考え方.
法則を見つけ出すのは簡単だ
例えばa[i]=6つまり110ならb[i]を001とペアにする
列の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;
}