B. Slice to Survive 详细题解

题目描述

决斗者 Mouf 和 Fouad 进入了一个 $n \times m$ 的网格竞技场。Fouad 的怪物起始位置在单元格 $(a, b)$，其中行的编号为 $1$ 到 $n$，列的编号为 $1$ 到 $m$。

Mouf 和 Fouad 将一直决斗，直到网格只剩下一个单元格为止。

每回合流程

每回合中：

1. Mouf 先操作：他沿着某条行线或列线将网格切成两部分，然后丢弃不含 Fouad 怪物的那一部分。注意：网格必须至少有 $2$ 个单元格，否则游戏已经结束。
2. 然后，在同一回合中，Fouad 将他的怪物移动到剩余网格中的任意单元格（可以停留在原地）。

Mouf 希望最小化回合数，而 Fouad 希望最大化回合数。如果双方都采取最优策略，这场决斗将持续多少回合？

输入格式

每个测试包含多个测试用例。
第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。
接下来每个测试用例包含四个整数 $n, m, a, b$（$2 \le n, m \le 10^9$，$1 \le a \le n$，$1 \le b \le m$）。

输出格式

对于每个测试用例，输出一个整数——双方都最优操作时，决斗将持续的回合数。

题目分析

核心观察

1. 每回合 Mouf 只能切一刀：他可以选择水平切或垂直切，去掉不含怪物的一半。

2. Fouad 可以移动怪物：在 Mouf 切完后，Fouad 会把怪物移动到剩余网格中对他最有利的位置，即让后续切割需要更多回合的位置。

3. 回合数与维度缩减的关系：

   • 假设当前网格有 $n$ 行，怪物在第 $a$ 行。Mouf 水平切时，最多能保留的行数为：$$\text{row\_remain} = \min(a, n - a + 1)$$ 这是因为 Mouf 可以选择保留上面或下面，但只能保留包含怪物的一侧。
   • 类似地，假设当前网格有 $m$ 列，怪物在第 $b$ 列。Mouf 垂直切时，最多能保留的列数为：$$\text{col\_remain} = \min(b, m - b + 1)$$

4. Fouad 的应对策略：

   • 如果 Mouf 选择水平切，Fouad 会把怪物移动到垂直方向的最中间，让后续垂直切割时需要更多回合。
   • 如果 Mouf 选择垂直切，Fouad 会把怪物移动到水平方向的最中间。

5. 维度缩减的规律：

   • 对于一个维度（行或列），每切一次，该维度的大小会减少。Fouad 会把怪物放到剩余部分的中间，因此每次只能将维度大小近似减半（向上取整）。
   • 把维度从 $x$ 减少到 $1$ 所需的最少切割次数为 $\lceil \log_2 x \rceil$。

最优策略分析

Mouf 有两种选择：

策略一：先水平切

• 第 1 回合：Mouf 水平切，保留 $\text{row\_remain} = \min(a, n - a + 1)$ 行和全部 $m$ 列。
• 第 1 回合结束后：Fouad 把怪物移动到剩余网格的中间列（使其远离边界）。
• 后续回合：
  • 水平方向：从 $\text{row\_remain}$ 行缩减到 $1$ 行，需要 $\lceil \log_2(\text{row\_remain}) \rceil$ 回合。
  • 垂直方向：从 $m$ 列缩减到 $1$ 列，需要 $\lceil \log_2 m \rceil$ 回合。
• 总回合数：$$\text{ans}_1 = 1 + \lceil \log_2(\text{row\_remain}) \rceil + \lceil \log_2 m \rceil $$

策略二：先垂直切

• 第 1 回合：Mouf 垂直切，保留 $\text{col\_remain} = \min(b, m - b + 1)$ 列和全部 $n$ 行。
• 第 1 回合结束后：Fouad 把怪物移动到剩余网格的中间行。
• 后续回合：
  • 水平方向：从 $n$ 行缩减到 $1$ 行，需要 $\lceil \log_2 n \rceil$ 回合。
  • 垂直方向：从 $\text{col\_remain}$ 列缩减到 $1$ 列，需要 $\lceil \log_2(\text{col\_remain}) \rceil$ 回合。
• 总回合数：$$\text{ans}_2 = 1 + \lceil \log_2 n \rceil + \lceil \log_2(\text{col\_remain}) \rceil $$

最终答案

Mouf 会选择两种策略中较小的回合数：

$$\text{ans} = \min(\text{ans}_1, \text{ans}_2)$$

算法实现

辅助函数：计算 $\lceil \log_2 x \rceil$

对于 $x \ge 1$：

• 如果 $x = 1$，则 $\lceil \log_2 1 \rceil = 0$
• 否则，可以使用内置函数 __lg 或位运算：$$\lceil \log_2 x \rceil = \text{bit\_width}(x) - 1 $$

其中 $\text{bit\_width}(x)$ 表示 $x$ 的二进制位数。

时间复杂度

• 每个测试用例 $O(1)$
• 总复杂度 $O(t)$，满足 $t \le 10^4$ 的要求

标程

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

// 计算 ceil(log2(x))
int ceil_log2(long long x) {
    if (x <= 1) return 0;
    // bit_width(x) = floor(log2(x)) + 1
    // ceil(log2(x)) = bit_width(x - 1)
    return 64 - __builtin_clzll(x - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        long long n, m, a, b;
        cin >> n >> m >> a >> b;
        
        // 计算第一次切割后能保留的最大行数和列数
        long long row_remain = min(a, n - a + 1);
        long long col_remain = min(b, m - b + 1);
        
        // 策略一：先水平切
        long long ans1 = 1 + ceil_log2(row_remain) + ceil_log2(m);
        
        // 策略二：先垂直切
        long long ans2 = 1 + ceil_log2(n) + ceil_log2(col_remain);
        
        // 取较小值
        cout << min(ans1, ans2) << "\n";
    }
    
    return 0;
}

样例验证

样例 1：$n=2, m=2, a=1, b=1$

• $\text{row\_remain} = \min(1, 2-1+1=2) = 1$
• $\text{col\_remain} = \min(1, 2-1+1=2) = 1$
• $\text{ans}_1 = 1 + \lceil \log_2 1 \rceil + \lceil \log_2 2 \rceil = 1 + 0 + 1 = 2$
• $\text{ans}_2 = 1 + \lceil \log_2 2 \rceil + \lceil \log_2 1 \rceil = 1 + 1 + 0 = 2$
• $\text{ans} = \min(2, 2) = 2$ ✅

样例 2：$n=3, m=3, a=2, b=2$

• $\text{row\_remain} = \min(2, 3-2+1=2) = 2$
• $\text{col\_remain} = \min(2, 3-2+1=2) = 2$
• $\text{ans}_1 = 1 + \lceil \log_2 2 \rceil + \lceil \log_2 3 \rceil = 1 + 1 + 2 = 4$
• $\text{ans}_2 = 1 + \lceil \log_2 3 \rceil + \lceil \log_2 2 \rceil = 1 + 2 + 1 = 4$
• $\text{ans} = \min(4, 4) = 4$ ✅

样例 4：$n=2, m=7, a=2, b=2$

• $\text{row\_remain} = \min(2, 2-2+1=1) = 1$
• $\text{col\_remain} = \min(2, 7-2+1=6) = 2$
• $\text{ans}_1 = 1 + \lceil \log_2 1 \rceil + \lceil \log_2 7 \rceil = 1 + 0 + 3 = 4$
• $\text{ans}_2 = 1 + \lceil \log_2 2 \rceil + \lceil \log_2 2 \rceil = 1 + 1 + 1 = 3$
• $\text{ans} = \min(4, 3) = 3$ ✅

所有样例均通过验证。

数学公式总结

设：

• $u = a - 1$（到上边距离）
• $d = n - a$（到下边距离）
• $l = b - 1$（到左边距离）
• $r = m - b$（到右边距离）

则：

$$\text{row\_remain} = \min(u, d) + 1$$ $$\text{col\_remain} = \min(l, r) + 1$$

最终答案为：

$$\text{ans} = \min\left(1 + \lceil \log_2(\min(u, d) + 1) \rceil + \lceil \log_2 m \rceil,\ 1 + \lceil \log_2 n \rceil + \lceil \log_2(\min(l, r) + 1) \rceil\right) $$

其中 $\lceil \log_2 x \rceil$ 可通过位运算快速计算。