B. Games 题解

---

一、题意理解

爱丽丝和鲍勃各有一份自己喜欢的游戏列表，且保证至少有一款游戏两人都喜欢。选择游戏的流程为：

• 两人轮流提议游戏，爱丽丝先手；
• 每次提议的游戏必须是提议者喜欢、且之前未被提议过的游戏；
• 一旦某人提议的游戏对方也喜欢，游戏结束，他们玩那一款。

目标是最大化提议次数，即让这个过程尽可能长。

---

二、核心思路

为了让提议次数尽可能多，双方应该先提议那些只有自己喜欢、对方不喜欢的游戏（即"独享游戏"），把两人都喜欢的游戏留到最后。

设：

• $k$ = 两人都喜欢的游戏数量（即交集大小 $|a \cap b|$）；
• $x = n - k$：只有爱丽丝喜欢的游戏数量；
• $y = m - k$：只有鲍勃喜欢的游戏数量。

游戏过程如下：

1. 爱丽丝先提议一款只有她喜欢的游戏（消耗 $x$ 中的一个，$x \gets x - 1$），鲍勃不喜欢，继续；
2. 鲍勃提议一款只有他喜欢的游戏（消耗 $y$ 中的一个，$y \gets y - 1$），爱丽丝不喜欢，继续；
3. 如此交替，直到某一方的独享游戏耗尽。

当一方的独享游戏用完后，该方只能提议两人都喜欢的游戏。一旦提议，对方也喜欢，游戏立刻结束。

---

三、公式推导

轮流消耗 $x$ 和 $y$，每次消耗一个，爱丽丝先手。

情况一：$x > y$

爱丽丝先手，轮流消耗：

• 爱丽丝消耗 $1$ 个 $x$ → 鲍勃消耗 $1$ 个 $y$ → 爱丽丝消耗 $1$ 个 $x$ → 鲍勃消耗 $1$ 个 $y$ → …

因为 $x > y$，鲍勃的 $y$ 会先耗尽。

当 $y = 0$ 时，鲍勃无独享游戏可提议，此时轮到他提议（因为每轮两人各一次，鲍勃在爱丽丝之后），他只能提议共同游戏，游戏结束。

期间：

• 鲍勃消耗了全部 $y$ 个独享游戏；
• 爱丽丝在鲍勃每次消耗之前都消耗一个 $x$，且多消耗一次（先手优势），共消耗 $y + 1$ 个 $x$；
• 总提议次数 = 爱丽丝的 $y + 1$ 次 + 鲍勃的 $y$ 次 + 鲍勃最后的共同游戏提议 $1$ 次（结束回合）= $(y + 1) + y + 1 = 2y + 2$。

由于 $y = \min(x, y)$，所以：

$$\text{答案} = 2 \cdot \min(x, y) + 2$$

情况二：$x \leq y$

类似地，轮流消耗。当 $x = 0$ 时，爱丽丝无独享游戏可提议，轮到她提议时只能提议共同游戏，游戏结束。

• 爱丽丝消耗了全部 $x$ 个独享游戏；
• 鲍勃消耗了 $x$ 个独享游戏（与爱丽丝配对消耗）；
• 爱丽丝最后提议共同游戏，结束。

总提议次数 = $x$（爱丽丝独享）+ $x$（鲍勃独享）+ $1$（爱丽丝最后提议共同游戏）= $2x + 1$。

即：

$$\text{答案} = 2 \cdot \min(x, y) + 1$$

---

四、最终公式

结合两种情况，得到统一的分段公式：

$$\boxed{ \text{答案} = \begin{cases} 2 \cdot \min(x, y) + 2, & \text{若 } x > y \\[4pt] 2 \cdot \min(x, y) + 1, & \text{若 } x \leq y \end{cases} } $$

其中：

$$k = |a \cap b|,\quad x = n - k,\quad y = m - k$$

等价地，也可以用 n 和 m 的大小关系判断：

$$\text{答案} = 2 \cdot \min(n - k,\ m - k) + \begin{cases} 2, & n > m \\ 1, & n \leq m \end{cases} $$

---

五、标程解析

fun main() = repeat(readln().toInt()) {
  val (n, m) = readln().split(" ").map { it.toInt() }
  val a = readln().split(" ").map { it.toInt() }
  val b = readln().split(" ").map { it.toInt() }
  val k = a.intersect(b).size
  println(2 * minOf(n - k, m - k) + if (n > m) 2 else 1)
}

步骤：

1. 读取 $n, m$ 以及两个已排序列表 $a, b$；
2. 用 intersect 计算交集大小 $k$；
3. 计算 $x = n - k$，$y = m - k$；
4. 用条件 n > m 判断 $x$ 与 $y$ 的关系（因为 $x - y = (n - k) - (m - k) = n - m$，所以 $n > m \iff x > y$）；
5. 代入公式输出答案。

---

六、样例验证

样例 1

输入：

2 3
1 2
2 3 5

• $k = |\{1, 2\} \cap \{2, 3, 5\}| = 1$
• $x = 2 - 1 = 1$，$y = 3 - 1 = 2$
• $x \leq y$，答案 $= 2 \cdot 1 + 1 = 3$ ✅

样例 2

输入：

1 1
5
5

• $k = 1$，$x = 0$，$y = 0$
• $x \leq y$，答案 $= 2 \cdot 0 + 1 = 1$ ✅

样例 3

输入：

4 2
1 3 4 7
4 6

• $k = |\{1, 3, 4, 7\} \cap \{4, 6\}| = 1$
• $x = 4 - 1 = 3$，$y = 2 - 1 = 1$
• $x > y$，答案 $= 2 \cdot 1 + 2 = 4$ ✅

---

七、代码实现（C++）

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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    
    // 计算交集大小 k
    set<int> sa(a.begin(), a.end());
    int k = 0;
    for (int x : b) {
        if (sa.count(x)) k++;
    }
    
    int x = n - k;  // 只有爱丽丝喜欢的游戏数
    int y = m - k;  // 只有鲍勃喜欢的游戏数
    
    int ans = 2 * min(x, y) + (x > y ? 2 : 1);
    cout << ans << "\n";
}

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

---

八、复杂度分析

• 每个测试用例需计算交集，可使用 set 或双指针，时间复杂度 $O(n + m)$ 或 $O((n+m) \log n)$。
• $n, m \leq 100$，$t \leq 1000$，完全可行。
• 空间复杂度 $O(n + m)$。