专栏文章

CF2115D 题解

DDaiRuiChen007
CF2115D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minnxphk
此快照首次捕获于
2025/12/02 05:30
3 个月前
此快照最后确认于
2025/12/02 05:30
3 个月前
查看原文
Problem Link
可以看成从 ⊕ai\oplus a_i 开始每次选择是否异或上 vi=ai⊕biv_i=a_i\oplus b_i。
从高到低确定每一位的取值，首先最高位 kk 的取值只和最后一个包含 2k2^k 的 viv_i 对应的 cic_i 有关。
然后考虑 k−1k-1，如果最后一个包含 2k−12^{k-1} 的 vjv_j 满足 j≠ij\ne i，那么只要考虑 cjc_j，否则玩家 cic_i 应该尽可能让异或和的 k,k−1k,k-1 位相同。
所以从 jj 继续往前找一个 k,k−1k,k-1 位不同的即可，继续类推 k−2,k−3,…k-2,k-3,\dots 的情况，可以发现最终每个位置的决策都形如 fi,gif_i,g_i，即当前的异或和 SS 若 popcount(fiAND⁡S) mod 2≠gi\mathrm{popcount}(f_i\operatorname{AND}S)\bmod 2\ne g_i 就异或上 aia_i。
维护 fi,gif_i,g_i 只要从后往前维护玩家 00 的目标 (w,h)(w,h) 表示尽可能让 popcount(wAND⁡S) mod 2=h\mathrm{popcount}(w\operatorname{AND}S)\bmod 2= h。
时间复杂度 O(nlog⁡V)\mathcal O(n\log V)。
代码：
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5;
ll a[MAXN],b[MAXN],f[MAXN];
bool c[MAXN],g[MAXN];
bool mul(ll x,ll y) { return __builtin_popcountll(x&y)&1; }
void solve() {
	int n; ll z=0,S=0;
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i],S^=a[i],f[i]=g[i]=0;
	for(int i=1;i<=n;++i) cin>>b[i],a[i]^=b[i];
	for(int i=1;i<=n;++i) { char o; cin>>o,c[i]=o-'0'; }
	for(int k=59;~k;--k) {
		int x=n; ll w=1ll<<k; bool h=0;
		for(;;--x) {
			for(;x&&!mul(a[x],w);--x);
			if(!x) { z|=(mul(S,w)^h)*(1ll<<k); break; }
			h^=c[x]^g[x],w^=f[x];
			if(!f[x]) { f[x]=w,g[x]=h^c[x],z|=c[x]*(1ll<<k); break; }
		}
	}
	cout<<z<<"\n";
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _; cin>>_;
	while(_--) solve();
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...