盒子

[codeforces289E]Polo the Penguin and XOR operation_数学/位运算

题目:CF289E
思路:从大往小扫一遍,每个数字异或上能让它变成该位数下最大的那个数字的最小的数字。
= =真是绕…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<cstdio>
#include<cstring>
using namespace std;
const int mx=1e6+5;
int a[mx],b[1005];
bool vis[mx];
int main() {
memset(vis,false,sizeof(vis));
int n,i,j,pos,x,sum;
long long ans;
scanf("%d",&n);
ans=0;
for(i=n; i>=0; i--) {
if(vis[i])continue;
x=i,pos=0;
while(x) {
b[pos++]=x&1;
x=x>>1;
}
// for(j=0; j<pos; j++)
// printf("%d\n",b[j]);
sum=0;
for(j=0; j<pos; j++) {
if(b[j]==0)sum+=(1<<j);
}
vis[sum]=vis[i]=true;
a[sum]=i;
a[i]=sum;
ans+=((sum^i)*2);
//printf("cp >> %d %d %d\n",ans,sum,i);
}
printf("%I64d\n",ans);
for(i=0;i<=n;i++)
printf("%d ",a[i]);
}