专栏文章

七濑悠月

冷冷却心月明かり
CF2115D题解参与者 2已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@mip3utcl
此快照首次捕获于
2025/12/03 05:43
3 个月前
此快照最后确认于
2025/12/03 05:43
3 个月前
查看原文
赛后过的，但感觉难度 2900* 高了，为啥我场上不会做。
二选一异或有点复杂，我们不妨记 ci=ai⊕bic_i=a_i \oplus b_i，这样如果让答案一开始为所有 aia_i 异或和，那么就是每次可以选择是否异或 cic_i，使最终答案最大或最小。
我们经典地从高位往低位考虑，设 dd 为所有 cic_i 中最高位的位置，那么此时不论前面怎么决策，最后一个最高位为 dd 的位置总能使得这一位变成决策者希望的最大或最小。形式化地，我们记下标集合 SS 表示最高位为 dd 的 cic_i 的位置集合，记 t=max⁡St=\max S，那么如果 S∖{t}S\setminus \{t\} 这个集合中最终操作得到答案的第 dd 位和 ctc_t 的决策者想要的不同，那么 ctc_t 就会异或进入答案，否则不变。于是我们先判断当前答案的第 dd 位是否需要 ctc_t 异或，然后把全部 cic_i 中最高位是 dd 的位置全部异或上 ctc_t，表示如果这一位选进答案，那么 ctc_t 是否选择的状态就要改变。容易发现这样操作一次最高位会降低，并且后面的操作不会改变更高的位置，所以最优。
时间复杂度 O(nlog⁡V)\mathcal O(n\log V)。
CPP
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 10;
int n; LL A[N]; char S[N];

int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int _; cin >> _;
	while (_ --) {
		cin >> n; LL Ans = 0, x;
		for (int i = 1; i <= n; i ++) cin >> A[i], Ans ^= A[i];
		for (int i = 1; i <= n; i ++) cin >> x, A[i] ^= x;
		cin >> (S + 1);
		for (int i = 59; i >= 0; i --) {
			int t = n; while (t && !((A[t] >> i) & 1)) t --;
			if (!t) continue;
			if (((Ans >> i) & 1) ^ (S[t] == '1')) Ans ^= A[t];
			for (int j = 1; j <= n; j ++) if ((A[j] >> i) & 1) A[j] ^= A[t];
		} cout << Ans << "\n";
	}
	return 0;
}

评论

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

正在加载评论...