Educational Codeforces Round 157 (Rated for Div. 2) D. XOR Construction (思维题)

题目

给定长为n-1(n<=2e5)的整数序列a，第i个数a[i](0<=a[i]<=2n)

构造一个长为n的整数序列b，满足：

1. 0到n-1在b数组中每个数恰好出现一次

2. 对于，

题目保证一定有解，有多组时可以输出任意一组

思路来源

cfAC代码

题解

首先，如果对左侧前i项做一个前缀的异或和，

即可得到

再钦定b[1]=0，即可得到一组b值，满足第二个条件

但是，这组数并不一定是[0,n-1]连续的，如第二个样例：

6

1 6 4 6 1

ans:0 1 7 6 2 3

发现并不连续，然后就不会做了，最终写了个分治的O(nlogn)的乱搞

事实上，按每位考虑[0,n-1]时，0的数量一定是>=1的数量的

所以，如果0的数量小于1的数量，就将这一位翻转即可

如果右起第i位出现0的数量等于1的数量的情形，说明低位也一定都是相等的情况

即的数都出现过一遍，此时可以任意两两交换，那么不翻转即可

例如，i=0时，表示一半奇数一半偶数，

表示此时i和i^1是成对出现的，

是否翻转都不会改变当前连号的状态

代码1（性质）

// Problem: D. XOR Construction
// Contest: Codeforces - Educational Codeforces Round 157 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1895/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int t,n,a[N],xo;
void sol(){sci(n);//printf("m:%d\n",m);rep(i,1,n-1){sci(a[i]);a[i]^=a[i-1];}per(j,20,0){int cnt=0;rep(i,0,n-1){cnt+=(a[i]>>j&1);}if(cnt>n-cnt)xo|=(1<<j);}
}
int main(){t=1;//(t); // t=1while(t--){sol();		rep(i,0,n-1){printf("%d%c",a[i]^xo," \n"[i==n-1]);}}return 0;
}

代码2（赛中乱搞）

// Problem: D. XOR Construction
// Contest: Codeforces - Educational Codeforces Round 157 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1895/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int t,n,a[N],xo;
vector<int>b,c;
bool dfs(int b,vector<int>l,vector<int>r){if(SZ(l)!=SZ(r))return 0;if(!SZ(l) && !SZ(r))return 1;if(b<0)return 1;if(!SZ(l) || !SZ(r))return 0;vector<int>LL,LR,RL,RR;for(auto &v:l){if(v>>b&1)LL.pb(v);else LR.pb(v);}for(auto &v:r){if(v>>b&1)RL.pb(v);else RR.pb(v);}if(xo>>b&1){return dfs(b-1,LR,RL) && dfs(b-1,LL,RR);}if(dfs(b-1,LL,RL) && dfs(b-1,LR,RR))return 1;xo|=1<<b;return dfs(b-1,LR,RL) && dfs(b-1,LL,RR);
}
void sol(){sci(n);b.pb(0);c.pb(0);//printf("m:%d\n",m);rep(i,1,n-1){sci(a[i]);a[i]^=a[i-1];b.pb(a[i]);c.pb(i);}dfs(18,b,c);
}
int main(){t=1;//(t); // t=1while(t--){sol();		rep(i,0,n-1){printf("%d%c",a[i]^xo," \n"[i==n-1]);}}return 0;
}