每次遇到找规律的提题都极其智硬,喵的看了别人的题解才知道。
这里是每个小区间内分别匹配,以2^k为划分
例如
0 000
1 001
2 010
3 011
4 100
4和3,2和1匹配。
WA了十几次最后发现是因为10^5后面写了四个0。。。
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include <ctype.h> using namespace std; //hdu 5014 int n; const int maxn=100010; int a[maxn]; int mp[maxn]; int l; int r; int get(int bit) { int ans=1; for(int i=1;i<=bit;i++) { ans*=2; } return ans; } void input() { for(int i=0;i<=n;i++) { scanf("%d",&a[i]); } l=0; r=0; } void run() { memset(mp,0,sizeof(mp)); // int t=0; for(int i=18;i>=0;i--) { if(get(i)<=n) { // t=i; l=get(i); break; } } // l=get(t);//从后往前找,找到第一个2^k的数 r=n; while(l>0)// when index>0, not the number, { // cout<<l<<" "<<r<<endl; //for(int j=get(l),i=get(l)-1;i>=max(2*get(l)-r-1,0)&&j<=r;i--,j++) //for(int j=r,i=l-(r-l+1);i<=l-1;i++,j--) for(int j=l,i=l-1;i>=max(2*l-r-1,0)&&j<=r;i--,j++) { mp[i]=j; mp[j]=i; } // r=2*get(l)-r-2; r=2*l-r-2; if(r<=0) break; for(int i=18;i>=0;i--) { //if(get(i)<l&&get(i)<=r) if(get(i)<=r) { l=get(i); // l=i; break; } } } long long ans=0; for(int i=0;i<=n;i++) { ans+=a[i]^mp[a[i]]; } printf("%I64d\n",ans); for(int i=0;i<=n;i++) { printf("%d%c",mp[a[i]],i==n?'\n':' '); } } int main() { freopen("input.txt","r",stdin); // freopen("data.txt","r",stdin); // freopen("out1.txt","w",stdout); while(scanf("%d",&n)!=EOF) { input(); run(); } return 0; }