异或空间线性基
我终于意识到写题解有多重要了
2024 CCPC 网络赛 Problem J. 找最小
Mandy 发现了两个很好玩的长度为\(n\)的序列，记为\(a,b\),她觉得一个序列的无趣度为序列内所有元素的异或和。
现在她想要这两个序列尽可能有趣，具体来说，她希望最无趣的序列尽可能有趣。她觉得交换两个序列中对应位置的元素是无伤大雅的，可以进行任意次这样的操作。
现在她想要知道，最有趣的情况下两个序列无趣度较大者的无趣度是多少呢？
形式化地来说，你有两个长度为 \(n\) 的序列 \(a,b\) ,你可以进行若干次选择一个 \(i\left(1\leq i\leq n\right)\) ,然后交换 \(a_i,b_i\) ,希望使得 \(\max\{f(a),f(b)\}\) 最小，其中对于一个序列 \(A,f(A)=\oplus_i=1^nA_i\) (\(\oplus\)表示按位异或) 。
Output
第一行一个整数 \(T\left ( 1\leq T\leq 10^5\right )\), 表示数据组数。
对于每组数据，第一行一个整数 \(n\) \((1≤n≤10^6)\) 。
第二行 \(n\) 个整数 \(a_1,a_2,\cdots,a_n\) \((0\leq a_i<2^{31})\)。
第三行\(n\)个整数\(b_1,b_2,\cdots,b_n\) \((0\leq b_i<2^{31})\) 。
保证对于所有数据，\(\sum n\leq10^6\)。
Solution
首先有一个重要观察，如果当前两个数组的异或和分别是 \(A\) 和 \(B\)， 使得 \(a_i\) 与 \(b_i\) 交换的操作即为
$A\oplus a_i \oplus b_i $ 与 $B\oplus a_i \oplus b_i $
即 \(c_i = a_i \oplus b_i\) , 在数组 \(c\) 中选择若干个数字异或
于是可以考虑线性基，设异或出的数字为 \(X\)
问题进展到这里，我们对 \(X\) 希望是什么样子的已经可以贪心得到了，从高位到低位贪心。
而线性基刚好异或上这一个，那么这个对应的这一位就在结果中出现，不异或这一个，就不会出现。
接下来就是分类讨论了，当前位若 \(A_i = B_i\) ，则去看线性基有没有这一位再直接选择异或或者不异或，我们可以强制 \(A > B\)，不然交换位置。那么第一个出现不同的情况的时候，肯定是 \(A_i = 1 \; \; B_i = 0\) 的情况，这时候我们如果选择异或这一位的话，那么 \(B\) 求出的答案就肯定大于 \(A\) 求出的答案了，所以，之后所有的选择都得偏袒 \(B\)。 相当于（在大的情况下我偏袒了 \(A\)，那么在每一个小的情况，我都需要去补偿 \(B\)，相反也是一样的）
下面是参考代码
点击查看代码
// Created by qyy on 2024/9/9.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int, int>
#define endl "\n"
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int n;
ll a[N], b[N];
bool zero;
ll p[N];
int xxjcnt;
int Gauss(){
// 此构造线形基出的是降序排序，大小为 xxjcnt 个，编号从 1 开始
for(int i = 1; i <= n; i++){
p[i] = a[i];
}
int i, k = 1;
ll j = (ll) 1 << 62; // 注意不是 63;
for(; j; j >>= 1){
for(i = k; i <= n; i++) {
if (p[i] & j) {
break; // 找到了第 j 位上的 1
}
}
if(i > n){
continue; // 没有找到第 j 位上的 1
}
swap(p[i], p[k]);
for(i = 1; i <= n; i++){
if(i != k && p[i] & j){
p[i] ^= p[k];
}
}
k++;
}
k--;
if(k != n){
zero = true;
}else{
zero = false;
}
return k;
}
ll toj[100]; // 需要更新;
int cal(ll x){
for(int i = 62; i >= 0; i--){
if((1LL << i) & x){
return i;
}
}
}
void solve() {
cin >> n;
for(int i = 0; i < 90; i++){
toj[i] = 0;
}
ll A = 0, B = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
A ^= a[i];
}
for(int i = 1; i <= n; i++){
cin >> b[i];
B ^= b[i];
}
for(int i = 1; i <= n; i++){
a[i] ^= b[i];
}
if(A < B){
swap(A, B);
}
xxjcnt = Gauss();
for(int i = 1; i <= xxjcnt; i++){
int x = cal(p[i]);
toj[x] = p[i];
}
ll ans1 = 0, ans2 = 0;
bool flag = false;
for(int i = 62; i >= 0; i--){
ll x = (1LL << i);
if((x&A) && (!(x&B))){
// 开始分类;
if(toj[i] != 0){
if(flag){
ans2 ^= toj[i]; // 应该按照 B 小的走，因为现在 B 异或出来一定比 A 大
}else{
ans1 ^= toj[i]; // 应该按照 B 小的走，因为现在 B 异或出来一定比 A 大
}
}
flag = true;
}else if((x&A) && (x&B)){
// 需要 toj[i] 参与进来
if(toj[i] != 0){
ans1 ^= toj[i];
ans2 ^= toj[i];
}
}else if((!(A&x)) && (!(B&x))){
// 不需要任何参与
}else{
// 给两个答案都计算上
if(toj[i] != 0){
ans1 ^= toj[i];
}
}
}
ll res1 = max(A^ans1, B^ans1);
ll res2 = max(A^ans2, B^ans2);
cout << min(res1, res2) << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
2024 校赛(团队赛)
作为 xxcdsg 的舔狗，Taibo 经常邀请 xxcdsg 一起玩无聊的游戏。
有一个长度为 \(n\) 的序列 $[a_1,a_2,...,a_n] $ , Taibo 和 xxcdsg 轮流在这个序列中取一个非空子序列并删除该子序列直到序列为空，Taibo 是先手。 游戏结束后，定义游戏的得分为 Taibo 和 xxcdsg 每次所取的子序列的异或和的总和。
现在，Taibo 想要最大化这个得分，而 xxcdsg 则想要最小化该得分。如果双方都采取最佳策略的情况下，最终的得分将是多少？关于非空子序列的定义：如果正整数 \(i_1,i_2,...,i_k(k\geq1)\) 满足\(1\leq i_1<i_2<...<i_k\leq n\), 那么 \([a _{i_1},a_{i_2},...,a_{i_k}]\)是 \([a_1,a_2,...,a_n]\) 的一个非空子序列。
例如，[1,2,6],[1,3,5],[4],[1,3,5,2,4,6]是[1,3,5,2,4,6]的非空子序列，而[1,2,3],[4,5],[1,2,3,4,5,6]不是。
\(n\leq2\times10^5,0\leq a_i<2^{20}\)
solution
首先一个重要观察，不管 Taibo 第一轮选了什么，剩下的所有数 xxcdsg 一定会全部全部拿光。原因即异或是不进位加法，\(a \oplus b \leq a + b\) ，于是问题简化为在一个数组中选择若干个数异或，加上剩余的数异或，求最大结果。
观察到数据范围，线性基后，可以搜索出每一种可能，于是枚举取最大值就行了。
参考代码如下：
<details>
<summary>点击查看代码</summary>
// Created by qyy on 2024/9/9.
include <bits/stdc++.h>
using namespace std;
typedef long long ll;
define PII pair<int, int>
define endl "\n"
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
const int mod = 7;
int n;
ll a[N];
bool zero;
ll p[N];
int xxjcnt;
int Gauss(){
// 此构造线形基出的是降序排序，大小为 xxjcnt 个，编号从 1 开始
for(int i = 1; i <= n; i++){
p[i] = a[i];
}
int i, k = 1;
ll j = (ll) 1 << 62; // 注意不是 63;
for(; j; j >>= 1){
for(i = k; i <= n; i++) {
if (p[i] & j) {
break; // 找到了第 j 位上的 1
}
}
if(i > n){
continue; // 没有找到第 j 位上的 1
}
swap(p[i], p[k]);
for(i = 1; i <= n; i++){
if(i != k && p[i] & j){
p[i] ^= p[k];
}
}
k++;
}
k--;
if(k != n){
zero = true;
}else{
zero = false;
}
return k;
}
ll ans = 0, sum = 0;
void dfs(int pos, ll cur){
if(pos == xxjcnt + 1){
ans = max(ans, cur + (sum^cur));
return ;
}
dfs(pos + 1, cur);
cur ^= p[pos];
dfs(pos + 1, cur);
}
void solve() {
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
sum ^= a[i];
}
xxjcnt = Gauss();
ans = sum;
dfs(1, 0);
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
</details>