题解：CF2171C2 Renako Amaori and XOR Game (hard version)

思路：

先解析操作，每次操作后把两个数互换，其对应的异或和也会重新计算。设第

i

次操作时统计数组

a

的异或和为

ans

，交换的两个数为

a_i

和

b_i

，那么进行交换操作后相当于是：

ans \oplus a_i \oplus b_i

。

贪心获取最大异或和。首先考虑输赢规则，是根据谁的异或和大决定输赢，那么可以有两种竞争方案：

通过增大自己的和达到比对手的和大的目的
通过减少对手的和达到比对手的和大的目的

那么把自己带入玩家，每次轮到我操作时：

若这次操作能使我的和增大我就换，显然过于片面，因此交换后可能我的和增大了对手的和也会增大且增大的值比我多，因此需要考虑这一点，设自己的数组为 $a$ ，和为 $ans_1$ ，对手的数组为 $b$ ，和为 $ans_2$ 。那么当 $ans_1 \oplus a_i \oplus b_i - ans_1 > ans_2 \oplus b_i \oplus a_i - ans_2$ 时才会进行交换。
若这次操作能使对手的和减少，同样需要考虑对自己的和的影响情况：若交换后对手减少的和比我减少的多，就交换。设自己的数组为 $a$ ，和为 $ans_1$ ，对手的数组为 $b$ ，和为 $ans_2$ 。那么当 $ans_1 - ans_1 \oplus a_i \oplus b_i < ans_2 - ans_2 \oplus b_i \oplus a_i$ 时才进行交换，判断两种情况容易报错，考虑简化公式。我们在小学数学中学过，不等式两边同乘 $-1$ 不等号要变号，那么可以得到： $ans_1 \oplus a_i \oplus b_i - ans_1 > ans_2 \oplus b_i \oplus a_i - ans_2$ 。可以发现和上面推导出的公式相同。因此每次只需要判断是否满足 $ans_1 \oplus a_i \oplus b_i - ans_1 > ans_2 \oplus b_i \oplus a_i - ans_2$ ，再决定是否进行交换。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define q1 a[i] ^ b[i]//宏定义一下 方便使用
#define q2 b[i] ^ a[i]
const int N = 2e5 + 10;
int a[N],b[N];
void solve(){
	int n;
	int ans1 = 0;
	int ans2 = 0;
	cin >> n;
	for(int i = 1;i <= n;i ++){cin >> a[i];ans1 ^= a[i];}
	for(int i = 1;i <= n;i ++){cin >> b[i];ans2 ^= b[i];}
	for(int i = 1;i <= n;i ++){
		if(a[i] == b[i])continue;//若两个数相同 那么交不交换没区别
		if(i % 2){//判断轮到谁操作了
			int p1 = ans1,p2 = ans2;
			if((ans1 ^ q1) - p1 > (ans2 ^ q2) - p2){
				ans1 ^= q1;
				ans2 ^= q2;
			}
		}else{
			int p1 = ans1,p2 = ans2;
			if((ans2 ^ q2) - p2 > (ans1 ^ q1) - p1){
				ans1 ^= q1;
				ans2 ^= q2;
			}
		}
	}
	if(ans1 == ans2)puts("Tie");
	if(ans1 > ans2)puts("Ajisai");
	if(ans1 < ans2)puts("Mai");
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t;
	cin >> t;
	while(t --){
		solve();
	}
	return 0;
}

题解：CF2171C2 Renako Amaori and XOR Game (hard version)

文章操作

思路：

代码：

相关推荐

评论

题解：CF2171C2 Renako Amaori and XOR Game (hard version)