CF1065-C1/C2·复盘——浅谈 XOR 与博弈中的最高有效位

发表于 2025-11-21 更新于 2025-11-22 分类于算法题解/复盘

前言

这一次的 CF1065 C1/C2，是一对非常具有代表性的 XOR 博弈题。

在比赛当时，这两题看上去像是在操作数组、模拟交换，但真正的本质来自一个非常稳定的结构：

一个在整个游戏过程中保持不变的整体异或 T
一个决定双方 XOR 大小关系的最高有效位（msb）
以及一个能改变局势的“最后的关键下标”

C1 是单 bit 游戏，C2 是多 bit 游戏，但二者的本质高度统一，甚至 C2 可以视为 C1 的自然推广。

文章会以“复盘 + 结构化分析”的方式来讲：

C1：理解最简 XOR 博弈（0/1）
C2：推广到 general XOR 博弈（≤10⁶）
最后给出整个 XOR 博弈体系的总结

期间也会穿插 ASCII 示意图，帮助理解关键下标、最高有效位等结构。

下面进入正文。

C1. Renako Amaori and XOR Game (Easy Version)

题面

题目翻译

给定两个长度为 n 的数组 a 与 b，其中所有元素均为 0 或 1。
游戏共进行 n 回合：

若 i 为奇数，则由 Ajisai 操作；
若 i 为偶数，则由 Mai 操作。

在第 i 回合，操作者可以选择：

交换 a[i] 与 b[i]，或
什么也不做（pass）

游戏结束后，评分如下：

Ajisai 的分数为：a[1] ⊕ a[2] ⊕ ... ⊕ a[n]
Mai 的分数为：b[1] ⊕ b[2] ⊕ ... ⊕ b[n]

若分数不同，分数大的获胜；若分数相同，则为平局。

整体异或不变量

任何一次交换都只是在同一个下标 i 位置交换 a[i] 与 b[i]。
这种操作不会改变 a 与 b 这两个序列中全部元素的集合，因此：

T = a 全体 ⊕ b 全体

在整个游戏过程中保持不变（这是整个 C1/C2 的基础结构）。

同时还成立：

T = Ajisai_score ⊕ Mai_score

这意味着最终的胜负情况只由 T 决定。

若 T = 0
→ 两人的最终 XOR 完全相同
→ 游戏必为平局
若 T = 1
→ 两人的最终 XOR 不可能相同
→ 必然分出胜负

这一步是 C1 的基础，也是后续 C2 的关键出发点。

接下来进入 C1 的错误思路复盘。

错误解法复盘：误以为“奇偶位置数量”决定胜负

比赛时我最初写出的思路，是基于“统计差异所在的奇数位和偶数位数量”来判断谁能获胜：

如果在 奇数位（Ajisai 能操作的位置）出现更多 a[i] != b[i] 的情况
→ Ajisai 更能“影响局势”，认为 Ajisai 会赢
如果在 偶数位（Mai 的回合）出现更多差异
→ Mai 会赢
如果数量相同，则认为是平局

这是一个看似合理、实际上完全错误的判断。

C1 WA code（我当时的版本）

C1 WA code

#include<bits/stdc++.h>
using namespace std;
int const maxn = 2e5 + 5;

int t, a[maxn], b[maxn];

void op(){
    int n, cnt_odd = 0, cnt_even = 0;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> b[i];
        if(a[i] != b[i]){
            if(i & 1){
                cnt_odd++;
            } else{
                cnt_even++;
            }
        }
    }
    if(cnt_odd > cnt_even){
        cout << "Ajisai" << '\n';
    } else if(cnt_odd < cnt_even){
        cout << "Mai" << '\n';
    } else{
        cout << "Tie" << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while(t--){
        op();
    }
    return 0;
}

错误原因分析

根本问题在于：
XOR 的胜负由唯一的关键下标决定，不由“数量”决定。

在 C1 中，所有元素都是 0/1，若整体异或 T = 1，说明最终两人的分数一高一低，而大小关系由“最后一个能翻转该位的下标”决定。

也就是说：

XOR 的比较不是累计效应，而是“最后一手效果”。

为了更直观地说明问题，我们加入 ASCII 示意图。

示意图（差异位置从后往前扫描）

i = 9   a=1 b=1
i = 8   a=0 b=0
i = 7   a=1 b=0   ← 最后一个差异，决定胜负
i = 6   a=0 b=0
i = 5   a=1 b=1
i = 4   a=0 b=0
...

可以看到：

下标越靠后，越决定最终的异或结果
只要在 i = 7 这里能动手，后面已无下标能覆盖它

因此：

若 最后的差异位 是奇数 → Ajisai 操作 → Ajisai 赢（如示意图所示）
若 最后的差异位 是偶数 → Mai 操作 → Mai 赢

无论前面有多少差异位，都被这个 最后的差异位 所覆盖。

为什么统计数量会产生误导？

因为 a[i] != b[i] 是否出现多次完全不重要。
决定 XOR 大小关系的不是次数，而是：

最后一个能改变哪一位的人是谁。

在 C1 中，这个最后位置就是“最后一个差异点”。
由于 XOR 是按位运算，且 C1 只有一位（只有 0/1），因此：

若 a[i] != b[i] 在 i = k 处是最后一次出现
那么 k 的操作者可以决定自己的最终 XOR 是 1 还是 0

从而直接确定胜负。

错误点总结

XOR 的大小不累加，受最后关键位影响
C1 只有一个 bit，所以只需找“最后一个差异位置”
差异出现次数完全不影响胜负
正确策略必须基于“顺序博弈 + 最后一手控制权”

接下来进入 C1 的正确解法。

C1 正确解法：最后一个差异下标的操作者获胜

C1 的核心在于：
当整体异或 T = 1 时，最终异或的大小完全由 最后一个能翻转该位的位置 决定。

我们已经在错误分析中看到：
只要知道差异的“最后一个下标”，就能判断胜负。

现在来严格说明这一结构。

1. 当 T = 1 时，胜负由最后一个差异下标决定

在 C1 中，所有元素都是 0 或 1。
最终的分数为：

Ajisai_score = a[1] ⊕ ... ⊕ a[n]
Mai_score = b[1] ⊕ ... ⊕ b[n]

因为 T = Ajisai_score ⊕ Mai_score 且 T = 1，
两者的分数必然一为 0、一为 1。

问题变为：

谁能决定某个位置的值在最终 XOR 中是否被计为 1？

XOR 的按位独立性使得“顺序”变得关键

对于序列 a：

最终 a 的 XOR = (((a[1] ⊕ a[2]) ⊕ a[3]) ... ⊕ a[n])

如果我们从左到右分析：

一个靠后的元素，其取值变化会覆盖所有更前面元素的影响
若前面某个差异位曾试图翻转结果，只要后面存在新的差异位，就可以再次翻转回来

于是结论自然形成：

在 C1 中，最后一个 a[i] != b[i] 的位置，是唯一有决定权的位置。

2. ASCII 示意图

下面是完整示意图（同上，但放在正确解法体系中）：

i = 9   a=1 b=1
i = 8   a=0 b=0
i = 7   a=1 b=0   ← 决胜点（最末一个差异）
i = 6   a=0 b=0
i = 5   a=1 b=1
i = 4   a=0 b=0
i = 3   a=1 b=1
i = 2   a=0 b=0
i = 1   a=1 b=1

因为下标 7 是最后一个差异点
7 是奇数 → 该回合由 Ajisai 操作
Ajisai 可以通过“交换 / 不交换”来决定 a[7] 是否变为 1 或 0

从而决定最终自己的 XOR 是否为 1
→ 决定胜负。

若最后的差异下标是偶数，则由 Mai 控制。

3. 正确解法结论化

所以，在 C1 中：

扫描从后往前找最后一个 a[i] != b[i] 的下标 i
若不存在，则 T = 0 → 平局
若存在：
- i 为奇数 → Ajisai 胜
- i 为偶数 → Mai 胜

这是 C1 的完整正确解法。

4. C1 AC code

说明：

下方给出的 AC 代码是我在比赛现场写出的实现方式：
逻辑正确，但偏向个人习惯，与本文推导出的理论模型略有差异。
在后续 C2 中，我会给出完全按本文结构写出的“规范解法版本”。

C1 AC Code

#include<bits/stdc++.h>
using namespace std;
int const maxn = 2e5 + 5;

int t, a[maxn], b[maxn];

void op() {
    int n, cnt_odd = 0, cnt_even = 0, cnt_1 = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        cnt_1 += a[i] ? 1 : 0;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        cnt_1 += b[i] ? 1 : 0;
        if (!(cnt_1 & 1)) {
            cout << "Tie" << '\n';
            return;
        }
        bool last_person; //1->odd 0->even
        for (int i = n; i >= 1; --i) {
            if (a[i] != b[i]) {
                last_person = (i & 1);
                break;
            }
        }
        if (last_person) {
            cout << "Ajisai" << '\n';
        } else {
            cout << "Mai" << '\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--) {
        op();
    }
    return 0;
}

C2. Renako Amaori and XOR Game (hard version)

题面

题目翻译

这一题是 C1 的加强版。
给定两个长度为 n 的数组 a 与 b，满足 0 ≤ a[i], b[i] ≤ 10^6。

游戏仍然进行 n 回合：

若 i 为奇数，则该回合由 Ajisai 操作；
若 i 为偶数，则该回合由 Mai 操作。

在第 i 回合，轮到的玩家可以选择：

交换 a[i] 与 b[i]，或者
什么也不做（pass）

游戏结束后，得分为：

Ajisai 的分数：a[1] ⊕ a[2] ⊕ ... ⊕ a[n]
Mai 的分数：b[1] ⊕ b[2] ⊕ ... ⊕ b[n]

分数更大者获胜，若分数相同则为平局。

与 C1 不同之处在于，这里 a[i] 和 b[i] 不再局限于 0/1，而是可以达到 10^6，也就是包含了更多二进制位，T 不再只可能是 0 或 1，而是一个多 bit 的整数。

整体异或不变量（与 C1 相同的骨架）

和 C1 完全一样，所有操作只在同一位置的 a[i] 与 b[i] 之间做交换，不会引入新数或删除旧数，因此：

T = a 全体 ⊕ b 全体

在整个游戏过程中仍然是一个不变量。

并且依然有：

T = Ajisai_score ⊕ Mai_score

所以：

若 T = 0
→ 两人的最终得分完全相同
→ 游戏必为 Tie
若 T ≠ 0
→ 两人的最终得分一定不同
→ 必分胜负

到这里为止，C2 与 C1 的结构是同一套骨架：
只要整体异或为 0，游戏就没有悬念，直接平局。
当整体异或不为 0，问题就变成：谁能把最终的数值拉大到对自己有利。

区别在于：C1 中我们只需要处理一个 bit（0/1），而 C2 中要面对的是一个多 bit 整数。

为什么只看最高有效位（msb）

当 T ≠ 0 时，T 是一个多 bit 的整数，例如：

T = 0010 1000 0100₂

这意味着在多个 bit 上，Ajisai 与 Mai 的最终结果存在差异。

但是，对于两个整数的比较，有一个非常重要的事实：

两个整数的大小，只由它们在“最高一个不同的二进制位”上的值决定。

也就是说：

找到 Ajisai_score 与 Mai_score 在最高一个不同的 bit
在这个 bit 上谁是 1、谁是 0，谁就赢
在此之下的所有更低位，统一统统不重要

而由于：

Ajisai_score ⊕ Mai_score = T

那么 T 在某一 bit 上为 1，就说明双方在这一位上必然不同。
特别地，在 T 的最高有效位（记作 msb）上，两人的得分在该位必然一高一低，并且这一位决定最终大小。

用一个 ASCII 示意图表示 T 的 bit 分布（示意）：

bit11 bit10 bit9 ... bit3 bit2 bit1 bit0
  1     0    1        0    1    0    0
  ↑
  msb（最高有效位）

在 bit11 这个位置上，T 为 1，代表：

Ajisai_score 与 Mai_score 在 bit11 这一位上不相同
并且 bit11 是它们“从高到低第一个不相同的位”

因此：

谁能控制最终在 bit11 上取 1，谁就拥有整个数值比较上的优势
低位的翻转（bit10 以下）不会推翻这条结论

换句话说，C2 虽然是多 bit 情况，但在博弈结构上 仍然退化成对 msb 这一位的控制问题：

C2 的本质是：在最高有效位 msb 上进行一场 C1 风格的博弈。

后面的分析要做的，就是精确刻画：
谁拥有对这一位的“最后一次操作权”，也就是谁能在这一位上做出最终决策。

寻找能影响 msb 的最大下标 `i_max`

我们已经知道：

胜负由 T 的最高有效位 msb 决定
双方的 XOR 在这一位上必然不同
谁能控制最终这一位取值为 1，谁就赢

现在的问题是：

哪些下标 i 能影响 msb 这一位？
谁是最后一个能影响它的人？

关键判定条件

在下标 i，交换与否会造成 msb 这一位的翻转，当且仅当：

((a[i] ⊕ b[i]) >> msb) & 1 == 1

这句话的含义是：

a[i] ⊕ b[i] 在 msb 位上为 1
表示如果交换 a[i] 与 b[i]，那么这一位的贡献会发生改变
因此该下标可以真实影响最终比分的最高位

我们称这样的下标为：

“影响 msb 的有效下标”

为什么必须找“最大”的这样的下标？

因为游戏从 1 到 n 顺序进行，越靠后的回合越晚出现。
假设有下面五个可能影响 msb 的下标：

i = 2, 5, 8, 11, 14

真正能决定胜负的只有：

最后一个（即 14）
因为它会覆盖前面所有的决策效果
前面的影响都会被“后继修改”覆盖掉（同 C1）

换句话说：

i_max = 最后一个能影响 msb 的下标
是本题的唯一关键点。

ASCII 示意图（图示 #3）

下面以一个示例说明：

i = 12   (a⊕b 在 msb 位为 1)
i = 11   (a⊕b 在 msb 位为 0)
i = 10   (a⊕b 在 msb 位为 1)
i =  9   (a⊕b 在 msb 位为 1)   ← i_max（最后一个能影响 msb 的位置）
i =  8   (a⊕b 在 msb 位为 0)
...

即使 i = 12 和 i = 10 也能影响 msb 位，
但它们最终都被 i = 9 的操作“覆盖”了：

游戏在第 9 回合有最后一次能够改变 msb 的机会
之后再没有任何下标能影响 msb
所以 i = 9 的操作者可以决定胜负

与 C1 的对应关系

到这里可以看到，C2 的结构与 C1 完全对应：

C1 （0/1）	C2（多 bit）
最后一个 `a[i] != b[i]`	最后一个 `(a[i] ⊕ b[i])` 在 `msb` 位上为 1
决定 XOR 的唯一位置	决定最高有效位的唯一位置
该位置的操作者获胜	该位置的操作者获胜

可以理解为：

C1 是一个“一维博弈”
C2 是一个“按 bit 拆开的多维博弈”，但胜负只看最高一维

如何根据 `i_max` 决定胜负

规则非常简单：

若 i_max 为奇数
→ Ajisai 操作
→ Ajisai 可以控制 msb 位置取 1
→ Ajisai 获胜
若 i_max 为偶数
→ Mai 操作
→ Mai 可以控制 msb 位置取 1
→ Mai 获胜

这就是 C2 的最终结论。

C2 算法流程与复杂度分析

把前面的分析收束成一个完整的实现流程，大致可以写成如下步骤：

读入 n，以及数组 a、b
计算整体异或 T：
- T ^= a[i]
- T ^= b[i]
若 T = 0：
- 直接输出 Tie，因为此时两人的最终分数必然相等
若 T ≠ 0：
- 在 0 ~ 20 的 bit 范围内，找到 T 的最高有效位 msb
- 这一位是唯一决定胜负的关键 bit
从后往前扫下标 i = n ... 1：
- 判断 (a[i] ⊕ b[i]) 的 msb 位是否为 1
- 若是，则记录该 i 为 i_max，并停止扫描
根据 i_max 的奇偶性输出胜负：
- 若 i_max 为奇数 → Ajisai
- 若 i_max 为偶数 → Mai

复杂度分析

计算整体异或 T：O(n)
找 msb：bit 扫描，O(log T)，在本题中约为常数（约 20）
从后往前找 i_max：O(n)
总体时间复杂度：O(n)
空间复杂度：O(n)（存下 a、b）

在 n 最多 2 * 10^5 的条件下，这个复杂度完全可以通过所有测试。

C2 AC code

C2 AC Code

#include<bits/stdc++.h>
using namespace std;

int t;

void op() {
    int n, xor_sum = 0, msb;
    cin >> n;
    vector<int> a(n + 5), b(n + 5);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        xor_sum ^= a[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        xor_sum ^= b[i];
    }
    if (!xor_sum) {
        cout << "Tie" << '\n';
        return;
    }
    for (int i = 20; i >= 0; --i) {
        if (1 & (xor_sum >> i)) {
            msb = i;
            break;
        }
    }
    for (int i = n; i > 0; --i) {
        if (((a[i] ^ b[i]) >> msb) & 1) {
            cout << ((i & 1) ? "Ajisai" : "Mai") << '\n';
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--) {
        op();
    }
    return 0;
}

XOR 小结与博弈结构回顾（总结）

整篇文章从 C1（0/1 情况）到 C2（多 bit 情况），实际上围绕的是同一个中心主题：

XOR 的结构性 —— 不变量、按位独立性、最高有效位的决定性
以及顺序博弈中“最后一个能改变关键位的人获胜”。

下面将这套结构完整收束，作为本文的最终总结。

1. XOR 的三个核心性质

在这两题中，真正起作用的只有 XOR 的三个基础性质：

按位独立性：高位与低位互不影响
异或不变量：只交换位置不改变整体 XOR
整数大小由最高不同位决定：这保证了 C2 只需处理 msb 一个 bit

其中最关键的，是第三条：
只要最高有效位差异已定，低位就无法影响最终大小。

因此，XOR 博弈的核心往往是：

找到决定关键 bit 的最后一个位置。

2. C1：单 bit 游戏的“最后一手控制权”

在 C1 中：

所有元素均为 0 或 1
最终 XOR 只有一位
胜负完全由最后一个 a[i] != b[i] 的下标决定

这是典型的“顺序博弈 + 最后一手胜”的结构。

3. C2：多 bit 游戏，但仍然只需处理最高 bit

在 C2 中：

元素的 bit 数更多
整体 XOR T 是一个多 bit 整数
但最终大小仍然只由 T 的最高有效位 msb 决定

因此 C2 的实质是：

在 msb 位上跑一遍 C1 的逻辑。

具体表现为：

寻找 (a[i] ⊕ b[i]) 在 msb 位上为 1 的最后一个 i
该 i 的操作者拥有决定权
奇数位 → Ajisai
偶数位 → Mai

和 C1 完全平行。

4. 一类 XOR 博弈题的通用做法

通过这两题，我们可以抽象出一类常见 XOR 博弈题的解法框架：

找不变量：整体 XOR 是否为固定？
判断平局条件：如果整体 XOR 为 0，一般直接平局
找关键 bit：通常是 msb
定位关键下标：最后一个能影响关键 bit 的地方
按回合归属输出胜负

许多看似复杂的 XOR 博弈，其实都可以被拆解成这种结构。

5. 本文的意义与后续思考

这篇文章不仅解决了 C1 / C2，也为之后处理此类问题奠定了统一视角：

遇到异或类博弈时，先看是否有“不变量”
再看是否能按 bit 拆分
若能拆分，最高有效位通常是核心
判断回合顺序是否决定胜负
是否存在“最后一个能翻转关键位的位置”

XOR 本身的逻辑并不复杂，但要真正理解它在博弈中的作用，需要对
“按位独立 + 顺序控制” 有清晰认识。

以上便是本篇的全部内容。

前言

C1. Renako Amaori and XOR Game (Easy Version)

题面

题目翻译

整体异或不变量

错误解法复盘：误以为“奇偶位置数量”决定胜负

C1 WA code（我当时的版本）

错误原因分析

示意图（差异位置从后往前扫描）

为什么统计数量会产生误导？

错误点总结

C1 正确解法：最后一个差异下标的操作者获胜

1. 当 T = 1 时，胜负由最后一个差异下标决定

XOR 的按位独立性使得“顺序”变得关键

2. ASCII 示意图

3. 正确解法结论化

4. C1 AC code

C2. Renako Amaori and XOR Game (hard version)

题面

题目翻译

整体异或不变量（与 C1 相同的骨架）

为什么只看最高有效位（msb）

寻找能影响 msb 的最大下标 i_max

关键判定条件

为什么必须找“最大”的这样的下标？

ASCII 示意图（图示 #3）

与 C1 的对应关系

如何根据 i_max 决定胜负

C2 算法流程与复杂度分析

复杂度分析

C2 AC code

XOR 小结与博弈结构回顾（总结）

1. XOR 的三个核心性质

2. C1：单 bit 游戏的“最后一手控制权”

3. C2：多 bit 游戏，但仍然只需处理最高 bit

4. 一类 XOR 博弈题的通用做法

5. 本文的意义与后续思考

寻找能影响 msb 的最大下标 `i_max`

如何根据 `i_max` 决定胜负