Moscow Pre-Finals Workshop 2020 - Legilimens+Coffee Chicken Contest A. Everyone Loves Playing Games
题意
Alice和Bob玩游戏，两人分别有(n)对数和(m)对数((x_i,y_i))
初始分数(X = 0)
操作可以选择数对中的一个数，最终把这些数异或起来构成最终分数，Alice希望(X)尽量大，Bob希望(X)小
Alice会先用完所有操作，然后Bob再用所有操作，两人都知道对方的数对
[1 leq N,M leq 10000\
1 leq x_i,y_i leq 10^{18}
]
分析
考虑先简化问题，两个数中选择一个数，可以先假定选择所有的(x_i)，并将(x_i oplus y_i)代替(x_i,y_i) 插入原序列，这样相当于对于序列中的数选还是不选的问题
对于集合中的数可以任意选择，我们可以考虑使用线性基，线性基大概就是说 我们可以找到一些基，这些基能够张成出原有数能张成的所有数
这样就把规模压缩到了(O(logn)) ，下面考虑两人的策略
对于每一位分别考虑，局面可以归纳为三元组（X当前位是否为1，Alice当前为是否有1，Bob当前位是否有1）
对于((x,0,0)) 两人都无法操作，对于((1,0,1)) ,Bob一定会操作，对于((0,1,0))Alice一定会操作
对于((1,1,1))若Alice操作，Bob就不会操作，若Alice不操作，Bob就会操作，((0,1,1))同理，这个时候可以再用类似上面的方法，先操作并插入他们的异或，如不更优，可以反悔
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> VI;
const int maxn=20005,MAX_BASE=60;
struct Linear_Bases {
ll b[MAX_BASE+5];
Linear_Bases() {
fill(b,b+MAX_BASE+1,0);
}
void clear(){
fill(b,b+MAX_BASE+1,0);
}
void add(ll num) {
for(int j=MAX_BASE; j>=0; j--)
if(num>>j&1) {
if(b[j]) { //该位存在基
num^=b[j];
continue;
}
b[j]=num;
for(int k=j-1; k>=0; k--)if(b[j]>>k&1)b[j]^=b[k];
for(int k=j+1; k<=MAX_BASE; k++)if(b[k]>>j&1)b[k]^=b[j];
break;
}
}
void build(vector<int>a) {
for(int num:a)add(num);
}
}A,B;
inline ll rd(){
ll x;
scanf("%lld",&x);
return x;
}
int main(){
int T = rd();
while(T--){
int n = rd();
int m = rd();
A.clear();
B.clear();
ll xors = 0;
for(int i = 0;i < n;i++){
ll a = rd();
ll b = rd();
xors ^= a;
A.add(a ^ b);
}
for(int i = 0;i < m;i++){
ll a = rd();
ll b = rd();
xors ^= a;
B.add(a ^ b);
}
for(ll now = 1ll << 61,i = 61;i >= 0;now >>= 1,i--){
if(xors & now) {
if(A.b[i]) {
if(B.b[i]) {
xors ^= A.b[i];
A.add(A.b[i] ^ B.b[i]);
}
}
else if(B.b[i]) xors ^= B.b[i];
}
else{
if(A.b[i]) {
if(B.b[i]) {
A.add(A.b[i] ^ B.b[i]);
}
else xors ^= A.b[i];
}
}
}
printf("%lld
",xors);
}
}