http://acm.hust.edu.cn/vjudge/contest/122814#problem/H
这道题就是求异或之和
知识点： a^b = c 等价于 b^c =a 和 a^c = b
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define MAXN 100000 + 10 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f int n,m; int a[MAXN],b[MAXN]; int main() { int i,j; while(~sf("%d",&n)) { mem(a,0); mem(b,-1); long long sum = 0; for(i=0;i<=n;i++) sf("%d",&a[i]); for(i=n;i>=0;i--) { int s = i; if(b[i] == -1) { int cnt = 0; while(s) { s>>=1; cnt++; } int tmp = (1<<cnt) -1; b[i] = i^tmp; b[i^tmp] = i; } } //for(i=0;i<=n;i++) pf("%d ",b[i]); for(i=0;i<=n;i++) sum+= i^b[i]; pf("%I64d ",sum); for(i=0;i<n;i++) { pf("%d ",b[a[i]]); } pf("%d ",b[a[n]]); } return 0; }