icontofig | 发布于 2020-05-04 23:46:43 | 阅读量 232 | 线性基
发布于 2020-05-04 23:46:43 | 线性基

题目大意

玩家Little Sub和lqybzx分别有N、M个数对(xi,yi)、(x'i,y'i),且双方都知道对方的数对中的数是什么,Little Sub先从自己的N个数对中的每个数对中选取1个数z,并且ans = ans xor z,之后lqybzx会对自己的M个数对做相同的操作。

Little Sub(A)希望最终结果更大,而lqybzx(B)希望最终结果更小,且双方均采取最优策略,问最终答案是多少。

题解

对于博弈的题目来说,我们其实不是好知道双方的脑回路是怎么想的。有时候我们能猜到有时候我们猜不到。

所以不妨我们先来假设两个人每个数对都选第一个数字,先把一个答案ans算出来,然后我们来根据每个人的数对再来进行调整。

由于是二进制的运算所以我们考虑对每个答案ans的每个二进制位上是否为1来讨论两个玩家的策略。

因为我们需要对二进制位进行讨论,所以我们需要讨论两个玩家的数对(x,y)中x xor y对答案的控制能力。所以我们需要对两个玩家的数对(x,y)进行x xor y的线性基的构造。

假设构造的两个x xor y的线性基分别为A、B。

如果在某个位bit上我们取了线性基X中在bit位上的元素,我们相当于在总答案的上面对某一组数对(x,y)的选择进行改变(ans xor(x xor y),本来ans中有x或y,选择这一次相当于换成另外一个)

我们从高位到低位逐一进行扫描,对于第i位,分为以下八种情况:

ans[i] = 0,A[i] = 0,B[i] = 0,双方都对这个位无法操作

ans[i] = 0,A[i] = 0,B[i] = 1,只有B对这个位可以操作,但由于B想要答案更小,所以他不会对这一位进行操作。

ans[i] = 0,A[i] = 1,B[i] = 0,只有A对这个位可以操作,由于A想要答案更大,所以他会选择对这一位进行操作,ans ^= A[i]。

ans[i] = 0,A[i] = 1,B[i] = 1,A与B都可对这个位操作,而且如果A对这个位操作的话,B一定也会对这个位操作,所以我们可以把A[i] xor B[i]加入到线性基A中,表示A和B同时选/不选。

ans[i] = 1,A[i] = 0,B[i] = 0,双方都对这个位无法操作

ans[i] = 1,A[i] = 0,B[i] = 1,只有B对这个位可以操作,由于B想要答案更小,所以他会选择对这一位进行操作,ans ^= B[i]。

ans[i] = 1,A[i] = 1,B[i] = 0,只有A对这个位可以操作,但由于A想要答案更大,所以他不会对这一位进行操作。

ans[i] = 1,A[i] = 1,B[i] = 1,A与B都可对这个位操作,ans先异或A[i]后与上面的第四种情况相同。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll xor_a[70],xor_b[70];
ll x,y,ans;
int n,m,t;
const int maxn = 1e5+5;
ll a[maxn],b[maxn];
void insert(ll num,ll xor_table[]){
	for(ll i = 63;i >= 0;--i){
		if((1ll << i) & num){
			if(xor_table[i])
				num ^= xor_table[i];
			else{
				xor_table[i] = num;
				break;
			}
		}
	}
	return;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	while(t--){
		cin >> n >> m;
		ans = 0;
		memset(xor_a,0,sizeof(xor_a));
		memset(xor_b,0,sizeof(xor_b));
		for(int i = 1;i <= n;++i){
			cin >> x >> y;
			ans ^= x;
			a[i] = x ^ y;
			insert(a[i],xor_a);
		}
		for(int i = 1;i <= m;++i){
			cin >> x >> y;
			ans ^= x;
			b[i] = x ^ y;
			insert(b[i],xor_b);
		}
		for(ll i = 63;i >= 0;--i){
			if(ans & (1ll << i)){
				if(!xor_a[i] && !xor_b[i])
					continue;
				if(xor_a[i] && !xor_b[i])
					continue;
				if(!xor_a[i] && xor_b[i])
					ans ^= xor_b[i];
				if(xor_a[i] && xor_b[i]){
					ans ^= xor_a[i];
					insert(xor_a[i] ^ xor_b[i],xor_a);
				}
			}
			else{
				if(!xor_a[i] && !xor_b[i])
					continue;
				if(xor_a[i] && ! xor_b[i])
					ans ^= xor_a[i];
				if(!xor_a[i] && xor_b[i])
					continue;
				if(xor_a[i] && xor_b[i])
					insert(xor_a[i] ^ xor_b[i],xor_a);
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

 


内容更新于: 2020-05-04 23:46:43
链接地址: http://blog.leanote.com/post/icontofig/683a6d28354a

上一篇: Luogu P2495 [SDOI2011]消耗战 虚树+树形DP

下一篇: 2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest C. Carpet

232 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航