这道题一开始没有什么想法。后来队友找到了一些规律,试验了一下,发现规律成立,然后就AC了。
我们的做法是由n开始从大到小遍历,每到一个数w,就找出比它小的二次方数h(就是h=2^k),然后找到w关于h对称的数,进行组合,并且将组合过的数用vis数组标记一下,下一次遍历到的时候就不再操作。而二次方数h就和h-1进行组合。0如果没有被组合过,就是0和0组合。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #define eps 1e-6 #define LL long long #define ull unsigned long long using namespace std; int n,vis[100005]; struct point{ int val,xval,ind; }p[100005]; int a[20]; bool cmp(point a,point b) { return a.val<b.val; } bool cmp1(point a,point b) { return a.ind<b.ind; } int main() { a[0]=1; for(int i=1;i<=20;i++) { a[i]=a[i-1]*2; } while(scanf("%d",&n)!=EOF) { for(int i=0;i<=n;i++) { scanf("%I64d",&p[i].val); p[i].ind=i; vis[i]=0; } LL ans=0; sort(p,p+n+1,cmp); for(int i=n;i>=0;i--) { int tem=(upper_bound(a,a+20,p[i].val)-a)-1; if(tem<0&&!vis[p[i].val]){p[i].xval=p[i].val;vis[p[i].val]=1;continue;} if(!vis[p[i].val]&&p[i].val==a[tem]&&!vis[p[i-1].val]){ ans+=(2*(p[i].val^p[i-1].val)+0LL); vis[p[i].val]=vis[p[i-1].val]=1; p[i].xval=p[i-1].val; p[i-1].xval=p[i].val; } else if(!vis[p[i].val]&&p[i].val>a[tem]){ int temp=p[i].val-a[tem]; int x=a[tem]-temp-1; if(!vis[x]){ ans+=(2*(p[i].val^x)+0LL); vis[p[i].val]=vis[x]=1; p[i].xval=x; p[x].xval=p[i].val; } } } printf("%I64d\n",ans); sort(p,p+n+1,cmp1); for(int i=0;i<n;i++) printf("%d ",p[i].xval); printf("%d\n",p[n].xval); } return 0; }