CF1987H Fumo Temple 题解

题意简述

交互题。有一个 $n \times m$ 的隐藏矩阵 $a$，$a_{i,j} \in \{-1,0,1\}$；评测机选定一个目标格子 $(i_0, j_0)$。

每次你可以询问一个格子 $(i,j)$，评测机返回：

• 若 $(i,j) = (i_0, j_0)$，返回 $0$；
• 否则，设 $S$ 为以 $(i,j)$ 与 $(i_0,j_0)$ 为对角的矩形内所有 $a$ 的和，返回 $|i-i_0| + |j-j_0| + |S|$。

要求在不超过 $n+225$ 次询问内求出 $(i_0, j_0)$。$n\le m\le 5000$，$\sum n\cdot m\le 2.5\times 10^7$。评测机是非自适应的。

核心观察

设询问 $(i,j)$ 得到的答案为 $r$，令 $x=|i-i_0|$，$y=|j-j_0|$。

矩形内的格子数为 $(x+1)(y+1)$，每个格子的值在 $\{-1,0,1\}$ 之间，因此 $|S|\le (x+1)(y+1)$。

于是：

这意味着矩阵 $a$ 的具体值并不重要——我们只需要利用 $r$ 所属的区间来筛掉不可能的位置。

随机化算法

算法流程

1. 维护当前所有可能的候选格子集合 $C$，初始 $C = \{(i,j)\mid 1\le i\le n,\;1\le j\le m\}$。
2. 从 $C$ 中均匀随机选取一个格子 $p$，询问 $p$，得到回答 $r$。
3. 若 $r=0$，则 $p$ 即为答案，输出并结束。
4. 否则，遍历 $C$ 中所有格子 $q$，计算 $x=|q_x-p_x|,\;y=|q_y-p_y|$，若 $x+y\le r\le x+y+(x+1)(y+1)$ 则保留，否则剔除。
5. 重复步骤 2~4。

为什么期望询问次数很少

每次随机选取的 $p$ 会对候选集产生约束。虽然最坏情况下一次只能剔掉很少的点，但由于矩阵 $a$ 的值「打乱」了 $|S|$ 的分布，使得 $r$ 在合法区间内的分布相当均匀。

实际效果是：每轮期望将候选集大小缩小一个常数因子，因此期望 $\Theta(\log(nm))$ 次询问即可找到答案。在题目限制下远小于 $n+225$。

这个随机化做法的精妙之处在于：它根本不关心 $a$ 的具体值，只依赖返回值的范围约束。基于 $a$ 数组来卡这个做法非常困难。

复杂度分析

• 空间复杂度：若直接存储所有候选点，需要 $\Theta(nm)$ 的空间（最大约 $200$ MB）。可以通过「按行存区间」的方式将空间优化到和剩余候选点数量成正比（通常远小于 $nm$）。
• 时间复杂度：每轮遍历候选集，期望轮数 $O(\log(nm))$，总复杂度 $O(nm\log(nm))$，在 $\sum nm\le 2.5\times10^7$ 下可通过。
• 询问次数：期望 $O(\log(nm))$，实际在本题数据范围内通常不超过几十次。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define MP make_pair

mt19937 rnd(time(0));

void solve() {
    int n, m;
    cin >> n >> m;

    vector<pii> a, b;
    a.reserve(n * m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a.emplace_back(i, j);

    while (!a.empty()) {
        b.clear();
        pii p = a[rnd() % a.size()];
        int res;
        cout << "? " << p.first << ' ' << p.second << endl;
        cin >> res;

        if (res == 0) {
            cout << "! " << p.first << ' ' << p.second << '\n';
            return;
        }

        for (auto &c : a) {
            int x = abs(c.first - p.first);
            int y = abs(c.second - p.second);
            int l = x + y;
            int r = x + y + (x + 1) * (y + 1);
            if (l <= res && res <= r)
                b.push_back(c);
        }
        a.swap(b);
    }
}

int main() {
    ios::sync_with_stdio(false);
    int _;
    cin >> _;
    while (_--) solve();
    return 0;
}