本文主要是介绍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;
}
这篇关于Educational Codeforces Round 157 (Rated for Div. 2) D. XOR Construction (思维题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!