admin管理员组文章数量:1602098
题面:
解法:
由于b[i]^b[i+1]=a[i]
因此只要b[i]确定,那么b[i+1]=b[i]^a[i], 即b[i+1]也能确定。
因此只要我们确定了某个b[i]的值,就能推算出整个b数组.
不妨考虑确定b[1]的值.
对于位运算问题,考虑对没一个二进制位单独考虑:
首先,由于答案数组一定是[0,n-1]因此每一位中1的个数是固定的.
假设b[i]的第j位为0,那么b数组中所有数的第j位就都是确定的.
我们可以计算第j位的总个数是否与[0,n-1]中第j位的总个数相同,
如果相同,则说明b[1]的第j位可以为0.
如果不相同,由于题目保证一定有解,那么b[1]的第j位取1一定有解.
计算出b[1]的所有位之后,我们理所当然的知道了b[1]的值,
之后只要推算出b数组中的其他值,这题就做完了。
Code:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI pair<int, int>
const int maxm = 2e5 + 5;
int n;
int a[maxm];
int b[maxm];
void solve() {
cin>>n;
for(int i=1;i<=n-1;i++){
cin>>a[i];
}
// 计算[0,n-1]的排列, 每个bit出现了多少次
int cnt[33]{0};
for(int i=0;i<n;i++){
for(int j=0;j<=30;j++){
cnt[j]+=(i>>j&1);
}
}
// 计算b[1]的每一位
int b1[33]{0};
for(int j=0;j<=30;j++){
// 考虑b1的第j位为0
int c1=0;
int last=0;
for(int i=2;i<=n;i++){
int v=(a[i-1]>>j&1);
last^=v;
if(last)c1++;
}
if(c1==cnt[j]){
b1[j]=0;
}else{
// 因为题目保证一定有解
// 所以如果0不行的话,1就一定可以
b1[j]=1;
}
}
// output
// 1.构造b[1]
for(int j=0;j<=30;j++){
if(b1[j]){
b[1]|=(1<<j);
}
}
// 2.构造b[2,n]
for(int i=2;i<=n;i++){
b[i]=b[i-1]^a[i-1];
}
for(int i=1;i<=n;i++){
cout<<b[i]<<' ';
}
cout<<endl;
}
signed main() {
// #define MULTI_CASE
ios::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("../in.txt", "r", stdin);
freopen("../out.txt", "w", stdout);
#endif
#ifdef MULTI_CASE
int T;
cin >> T;
while (T--)
#endif
solve();
return 0;
}
本文标签: 思维xorconstruction
版权声明:本文标题:Codeforces1895 D. XOR Construction(异或,位运算思维) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728397075a1157134.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论