AtCoder Beginner Contest 448 题解

for-each2026年8月18日大约 22 分钟

AtCoder Beginner Contest 448 题解

项目	内容
比赛时间	2026-03-07
比赛链接	https://atcoder.jp/contests/abc448
题目数量	A–G 共 7 题

比赛概览

本场 A、B 是纯粹的签到题（模拟与分组求和），从 C 开始进入"想法"层面：C 是一个小巧的观察题（每次只删 5 个球，只需关注全局最小的 6 个）；D 是经典的"DFS 维护根到当前点路径信息"；E 是游程编码大数除法的取模技巧（二进制倍增求 repunit）；F 是构造题，借用 Mo 算法的"蛇形"划分证明存在长度足够短的哈密顿回路；G 则是压轴的博弈论难题，综合 minimax 定理、凸包（直线包络）与三分搜索。本场整体梯度清晰，C、D、G 三题分别代表"观察力""树上路径维护"和"博弈论 + 计算几何/凸性"三个值得重点掌握的考点。

A - chmin

题目链接：https://atcoder.jp/contests/abc448/tasks/abc448_a

题目大意

给定整数 $N, X$ 与长度为 $N$ 的数列 $A=(A_1,\dots,A_N)$ 。按 $i=1,2,\dots,N$ 的顺序处理：若 $A_i < X$ ，则更新 $X=A_i$ 并输出 1，否则输出 0。共输出 $N$ 行。

思路

这题就是最朴素的"维护当前最小值"模拟。 $X$ 扮演"历史最小记录"的角色，遍历数组时逐项判断即可。

若 $A_i < X$ ：说明出现了新的更小值，更新 $X \leftarrow A_i$ ，输出 1；
否则： $A_i \ge X$ ， $X$ 不变，输出 0。

为什么正确：过程完全照搬题目描述，判断条件 $A_i < X$ 是严格小于（注意与 $A_i = X$ 区分，相等时输出 0），每次判断使用的都是最新更新过的 $X$ 。由于更新只可能使 $X$ 变小，之后用更小的 $X$ 比较正是题目要求的"动态"行为。

易错点：比较是严格小于，不是小于等于； $X$ 要在判断之前更新（顺序不能反，更新后本轮输出 1）。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N, X;
    cin >> N >> X;
    for (int i = 0; i < N; i++) {
        int A;
        cin >> A;
        if (A < X) {
            X = A;
            cout << "1\n";
        } else {
            cout << "0\n";
        }
    }
    return 0;
}

复杂度分析

时间复杂度： $O(N)$
空间复杂度： $O(1)$

B - Pepper Addiction

题目链接：https://atcoder.jp/contests/abc448/tasks/abc448_b

题目大意

餐厅有 $M$ 种胡椒，第 $j$ 种库存 $C_j$ 克。高桥点了 $N$ 道菜，第 $i$ 道菜只能撒第 $A_i$ 种胡椒，且撒的份量上限为 $B_i$ 克。每种胡椒的总用量不能超过其库存。求能撒出的胡椒总量最大值。

思路

每种胡椒互不干扰，可以按类型分别考虑。对第 $j$ 种胡椒，把所有"只能用它"的菜的需求上限加起来：

s_j=\sum_{i:\ A_i=j} B_i

如果 $s_j \le C_j$ ，那么所有需求都能满足，最多能撒 $s_j$ 克；如果 $s_j > C_j$ ，库存不够，最多只能撒 $C_j$ 克。所以第 $j$ 种的贡献为 $\min(C_j, s_j)$ ，答案即

\sum_{j=1}^{M}\min(C_j, s_j)

为什么可行：因为不同类型的胡椒之间没有约束，把每种胡椒独立地取"需求上限"与"库存"的较小值后，一定存在一种分配达到这个总量——例如按菜编号顺序，对每道菜尽量多撒它对应类型的胡椒即可（当某类型的总需求超出库存时，会自然地在某道菜上被截断，但不影响总量上界）。

实现：先用一个计数数组 $s_j$ 累加 $B_i$ （桶排序思想），再求和。注意 $C_i, B_i \le 10^6$ 、 $N,M \le 1000$ ，答案可能达到 $10^6 \times 1000 = 10^9$ 量级，用 long long 存答案更稳妥。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N, M;
    cin >> N >> M;
    vector<long long> C(M + 1), s(M + 1, 0);
    for (int j = 1; j <= M; j++) cin >> C[j];
    for (int i = 0; i < N; i++) {
        int A;
        long long B;
        cin >> A >> B;
        s[A] += B;
    }
    long long ans = 0;
    for (int j = 1; j <= M; j++) ans += min(C[j], s[j]);
    cout << ans << "\n";
    return 0;
}

复杂度分析

时间复杂度： $O(N+M)$
空间复杂度： $O(M)$

C - Except and Min

题目链接：https://atcoder.jp/contests/abc448/tasks/abc448_c

题目大意

袋子里有 $N$ 个球，第 $i$ 个球上写着整数 $A_i$ 。有 $Q$ 个查询，每个查询给一个长度为 $K$ （ $1\le K\le 5$ ）的互不相同、且递增的下标序列 $B_1,\dots,B_K$ ，先移除这些球，输出剩余球上数值的最小值，再把这 $K$ 个球放回。保证每次移除后袋子非空。

思路

关键观察：每次至多移除 5 个球，而袋子里"数值最小的 6 个球"中必然至少有一个没有被移除。因为若要 6 个球全被移除，需要一次删除 6 个不同的球，这与 $K\le 5$ 矛盾。

因此做法是：

将 $(A_i, i)$ 按 $A_i$ 升序排序，取出前 6 个（题目保证 $N \ge 6$ ）；
对每个查询，从这 6 个里从小到大找第一个"下标不在被移除集合中"的球，它的 $A$ 值就是答案。

为什么正确：设排序后的前 6 个球为 $G_1,\dots,G_6$ （ $A$ 值升序）。剩余球的最小值 $m$ 一定等于某个 $G_t$ 的 $A$ 值：如果 $m$ 对应的球不在前 6 个里，那么前 6 个球全被移除了（因为任何比 $m$ 小的球都不存在，而 $G_1,\dots,G_6$ 的所有值都 $\le m$ 且如果没被移除它们就是 $m$ 或更小），矛盾。于是 $m$ 就是前 6 个中第一个未被移除的球的值。

实现细节： $K\le 5$ 很小，查询时把 $B$ 排序后对每个候选球二分查找即可；或用哈希集合判存在。每个查询的检查次数至多 6 次。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<pair<int, int>> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i].first;
        A[i].second = i + 1;  // 球的下标
    }
    sort(A.begin(), A.end());
    while (Q--) {
        int K;
        cin >> K;
        vector<int> B(K);
        for (auto& b : B) cin >> b;
        sort(B.begin(), B.end());
        for (int i = 0; i < 6; i++) {
            if (!binary_search(B.begin(), B.end(), A[i].second)) {
                cout << A[i].first << "\n";
                break;
            }
        }
    }
    return 0;
}

复杂度分析

时间复杂度： $O(N \log N + \sum K \log K)$ （其中 $\sum K \le 4\times 10^5$ ）
空间复杂度： $O(N)$

D - Integer-duplicated Path

题目链接：https://atcoder.jp/contests/abc448/tasks/abc448_d

题目大意

给定一棵 $N$ 个点的树，每个点 $i$ 上有整数 $A_i$ 。对每个 $k=1,\dots,N$ ，判断从点 $1$ 到点 $k$ 的简单路径上是否存在两个不同的点写有相同的整数：若存在输出 Yes，否则 No。

思路

对每个 $k$ 单独从 $1$ 走到 $k$ 扫描路径是 $O(N^2)$ 的，不可行。需要一种批量处理所有根到点的路径的方法。

经典做法：从根 $1$ 做一次 DFS，并维护"当前根到当前点的路径"的信息。进入一个点 $v$ 时把 $v$ 的信息加入，离开时把它移除——于是 DFS 进入 $v$ 的瞬间，维护的信息恰好就是路径 $1\to v$ 上的信息。

具体地，维护一个集合 $S$ （当前路径上出现过的 $A$ 值）和一个计数器 $cnt$ （当前路径上"与某个祖先同值"的点的个数）：

进入 $v$ $v$ 时：
- 若 $A_v$ 已在 $S$ 中，说明 $v$ 与路径上的某个祖先写有相同整数，令 $del=1$ ， $cnt \leftarrow cnt+1$ （此时重复对增加了一对）；
- 否则把 $A_v$ 插入 $S$ ，令 $del=0$ （ $v$ 是它这个值在路径上的首个出现点）。
- 若 $cnt>0$ 则 $v$ 的答案为 Yes，否则 No。
离开 $v$ 时回滚：若 $del=1$ ，令 $cnt \leftarrow cnt-1$ （撤销 $v$ 带来的重复触发）；若 $del=0$ ，从 $S$ 中删除 $A_v$ 。

为什么正确： $S$ 与 $cnt$ 描述的是"从根到当前点的路径"这一集合。 $cnt$ 统计的正是路径上那些"其值已在祖先中出现过"的点的个数，它大于 0 当且仅当路径上存在两个同值点（一对同值点会且只会被后出现的那一个点记一次）。由于 DFS 的进入/离开与路径一一对应，每个点的答案都在进入时被正确记录。

易错点：删除/回滚的顺序必须与插入完全对称；根节点进入时 $S$ 为空，答案必为 No。另外 $A_i$ 可达 $10^9$ ，用 set 或 unordered_set 均可；若用 set 复杂度 $O(N\log N)$ 。也可以先对 $A$ 离散化，改用数组维护每个值在当前路径上的出现次数：进入时计数从 1 变 2 则 $cnt+1$ 、从 0 变 1 则无变化，离开时对称回滚，达到 $O(N)$ 。

参考代码

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

int N;
vector<int> A;
vector<vector<int>> g;
vector<char> ans;
int cnt = 0;
set<int> S;

void dfs(int v, int pv) {
    int del = 0;
    if (S.count(A[v])) del = 1;   // A_v 已出现在当前路径上
    else S.insert(A[v]);
    cnt += del;
    ans[v] = (cnt > 0);
    for (int nx : g[v]) {
        if (nx == pv) continue;
        dfs(nx, v);
    }
    cnt -= del;
    if (del == 0) S.erase(A[v]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    A.resize(N);
    for (auto& a : A) cin >> a;
    g.resize(N);
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ans.resize(N);
    dfs(0, -1);
    for (int i = 0; i < N; i++) cout << (ans[i] ? "Yes" : "No") << "\n";
    return 0;
}

复杂度分析

时间复杂度： $O(N \log N)$ （用 set；离散化后用数组可做到 $O(N)$ ）
空间复杂度： $O(N)$

E - Simple Division

题目链接：https://atcoder.jp/contests/abc448/tasks/abc448_e

题目大意

求 $\left\lfloor \dfrac{N}{M} \right\rfloor \bmod 10007$ 。其中 $N$ 没有直接给出，而是以游程编码形式给出： $K$ 个二元组 $(c_i, l_i)$ 表示把数字 $c_i$ 重复 $l_i$ 次拼成十进制串 $S$ ， $N$ 就是 $S$ 代表的整数。保证 $c_1\ne 0$ ， $M \le 10^4$ ， $K\le 10^5$ ， $l_i\le 10^9$ ， $N$ 可能极其巨大。

思路

第一步：把问题转成"求 N 对一个模数的余数"。

设 $X = M \times 10007$ 。若 $N = qX + r$ （ $0\le r < X$ ），则

\left\lfloor \frac{N}{M}\right\rfloor = \left\lfloor \frac{qM\cdot 10007 + r}{M}\right\rfloor = q\cdot 10007 + \left\lfloor \frac{r}{M}\right\rfloor

于是 $\left\lfloor N/M \right\rfloor \equiv \left\lfloor r/M \right\rfloor \pmod{10007}$ 。也就是说，只需要求出 $r = N \bmod (M\times 10007)$ ，答案就是 $r/M$ 的整数部分。由于 $M\le 10^4$ ， $X \le 1.0007\times 10^8$ ，全程 64 位整数即可容纳（乘法只需两个小于 $X$ 的数相乘）。

第二步：把游程编码的 N 展开成和式。

设 $R_k$ 表示由 $k$ 个 1 组成的数（repunit，即 $111\cdots 1$ ）。逐段拼接时，第 $i$ 段贡献的数值为"数字 $c_i$ 重复 $l_i$ 次"，等价于 $c_i \times R_{l_i}$ ，再乘上它后面所有数字的位数所对应的 $10$ 的幂。因此

N = \sum_{i=1}^{K} c_i \cdot R_{l_i} \cdot 10^{\sum_{j=i+1}^{K} l_j}

第三步：模 $X$ 下求 $R_{l_i}$ （关键）。

$R_k$ 有公式 $R_k = \dfrac{10^k-1}{9}$ ，但 $9$ 在模 $X$ 下不一定存在逆元（例如 $M$ 是 3 的倍数时 $\gcd(9,X)>1$ ），不能直接除。改用二进制倍增（binary lifting）：

预处理 $P_d = 10^{2^d} \bmod X$ ： $P_0=10$ ， $P_d = P_{d-1}^2 \bmod X$ ；
预处理 $Q_d = R_{2^d} \bmod X$ ： $Q_0 = R_1 = 1$ ，且

R_{2^d} = R_{2^{d-1}}\cdot 10^{2^{d-1}} + R_{2^{d-1}} \quad\Longrightarrow\quad Q_d = Q_{d-1}\cdot P_{d-1} + Q_{d-1} \pmod{X}

对任意 $l$ ，把 $l$ 写成二进制 $l=2^{a_1}+2^{a_2}+\cdots$ ，从高位到低位合并：若已知 $R_s$ ，则

R_{s+2^d} = R_s \cdot 10^{2^d} + R_{2^d}

即循环里维护 r，遇到置位的 $d$ 就执行 r = (r * P[d] + Q[d]) % X。由于 $l_i \le 10^9 < 2^{30}$ ，预处理到 $d=30$ 即可。

第四步：倒序累加。

从 $i=K$ 往 $i=1$ 倒着扫，维护 dgt 表示第 $i$ 段后面已有的位数。对每一段：

\text{贡献} = c_i \cdot R_{l_i} \cdot 10^{dgt} \bmod X

累加进 res，然后 dgt += l_i。最终 res 就是 $r=N\bmod X$ ，输出 res / M。

正确性要点：所有中间量都在模 $X$ 下计算，加法、乘法、求幂都是标准的取模运算；逆元从头到尾没有被使用，规避了 $\gcd(9,X)>1$ 的问题。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int K;
    ll M;
    cin >> K >> M;
    vector<ll> c(K), l(K);
    for (int i = 0; i < K; i++) cin >> c[i] >> l[i];

    ll mod = M * 10007LL;
    const int D = 31;                      // 2^30 > 1e9
    vector<ll> pow10(D), rep(D);
    pow10[0] = 10 % mod;
    rep[0] = 1 % mod;                      // R_1
    for (int d = 1; d < D; d++) {
        pow10[d] = pow10[d - 1] * pow10[d - 1] % mod;              // 10^{2^d}
        rep[d] = (rep[d - 1] * pow10[d - 1] + rep[d - 1]) % mod;   // R_{2^d}
    }

    auto modpow = [&](ll base, ll e) {     // base^e mod mod
        ll r = 1;
        while (e > 0) {
            if (e & 1) r = r * base % mod;
            base = base * base % mod;
            e >>= 1;
        }
        return r;
    };

    auto repunit = [&](ll n) {             // R_n mod mod
        ll r = 0;
        for (int d = D - 1; d >= 0; d--) {
            if (n & (1LL << d)) {
                r = (r * pow10[d] + rep[d]) % mod;
            }
        }
        return r;
    };

    ll res = 0;
    ll dgt = 0;                            // 当前段后面已有的位数
    for (int i = K - 1; i >= 0; i--) {
        ll ce = c[i] * modpow(10, dgt) % mod;
        ll R = repunit(l[i]);
        res = (res + ce * R) % mod;
        dgt += l[i];
    }
    cout << res / M << "\n";
    return 0;
}

复杂度分析

时间复杂度： $O(K \log(\max l_i))$ ，即 $O(K \cdot 31)$ ，快速幂部分约 $O(K \log(\text{dgt}))$
空间复杂度： $O(K + \log(\max l_i))$

F - Authentic Traveling Salesman Problem

题目链接：https://atcoder.jp/contests/abc448/tasks/abc448_f

题目大意

平面上有 $N$ 个点，点 $i$ 坐标为 $(X_i, Y_i)$ （ $0\le X_i,Y_i\le 2\times 10^7$ ）。从点 1 出发，每个点恰好访问一次并回到点 1，移动 $(X_i,Y_i)\to(X_j,Y_j)$ 花费曼哈顿距离 $|X_i-X_j|+|Y_i-Y_j|$ 秒。请给出一条总用时不超过 $10^{10}$ 秒的回路。题目保证在给定约束下存在这样的回路（任意合法答案均可）。

思路

这是一道构造题，不需要求出精确的最短哈密顿回路，只需构造一条总长上界能证明不超过 $10^{10}$ 的回路。官方题解给出了一种与 Mo 算法同构的"蛇形"构造。

设坐标范围为 $W = 2\times 10^7$ 。选定一个宽度参数 $B$ ，把 $[0,W]\times[0,W]$ 的区域按 $x$ 切成 $\approx W/B$ 个宽度为 $B$ 的竖条：

竖条从 0 开始编号，在偶数编号的竖条内按 $y$ 升序访问其中的点；
在奇数编号的竖条内按 $y$ 降序访问；
条与条之间自然衔接（一条扫完从顶部/底部进入相邻条），最后从末尾点回到起点。

总时间可以这样估计：

条内纵向移动：每个条内上下最坏各约 $W$ ，共 $\dfrac{W}{B}$ 个条，总计 $\dfrac{W^2}{B}$ ；
条内横向移动：共 $N$ 次相邻点之间的移动，每次横向最多 $B$ ，总计 $NB$ ；
条间衔接：约 $\dfrac{W}{B}$ 次，每次约 $2B$ ，总计 $2W$ ；
最后回到起点：最多 $2W$ 。

于是总长

T(B) \le \frac{W^2}{B} + NB + 4W

由 AM-GM 不等式，取 $B=\dfrac{W}{\sqrt{N}}$ 时两项均衡，得 $T \approx 2W\sqrt{N} + 4W$ 。代入 $N=6\times 10^4,\ W=2\times 10^7$ ：

2W\sqrt{N}+4W \approx 2\times 2\times 10^7 \times 244.9 + 8\times 10^7 \approx 9.87\times 10^9 < 10^{10}

满足要求。

实现：按 $(X_i/B)$ 分组（X[i]/B 作为条号），组内奇数条按 $Y$ 降序、偶数条按 $Y$ 升序排序，得到一个"蛇形"顺序，然后用 rotate 把点 1 转到开头。排序本身 $O(N\log N)$ 。注意用整数除法取条号即可，宽度 $B$ 取 (int)(W / sqrt(N))。

说明：题解讨论中还提到，若换成 Hilbert 曲线、Z-order 曲线等空间填充曲线也能得到 $O(W\sqrt{N})$ 量级的构造；另外 noshi91 证明了该构造的最坏情形总长可改进到 $\sqrt2\,W\sqrt{N}+O(W)$ ，并且存在任意回路总长都至少为 $\sqrt2\,W\sqrt{N}$ 的实例，因此 $O(W\sqrt N)$ 量级在相差常数项的意义下已经是最优。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; i++) cin >> X[i] >> Y[i];

    const int W = 20000000;
    int B = max(1, (int)(W / sqrt((double)N)));

    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        int bi = X[i] / B, bj = X[j] / B;
        if (bi != bj) return bi < bj;
        if (bi & 1) return Y[i] > Y[j];   // 奇数条：y 降序
        return Y[i] < Y[j];               // 偶数条：y 升序
    });

    // 把点 1（下标 0）旋转到开头
    int pos0 = 0;
    while (ord[pos0] != 0) pos0++;
    rotate(ord.begin(), ord.begin() + pos0, ord.end());

    for (int i = 0; i < N; i++)
        cout << ord[i] + 1 << (i + 1 == N ? "\n" : " ");
    return 0;
}

复杂度分析

时间复杂度： $O(N\log N)$ （排序）
空间复杂度： $O(N)$

G - Conquest

题目链接：https://atcoder.jp/contests/abc448/tasks/abc448_g

题目大意

高桥和青木玩一个卡牌游戏。高桥有 $N$ 副牌 $A_1,\dots,A_N$ ，青木有 3 副牌 $B_1,B_2,B_3$ 。两人同时各自禁掉对方的一副牌（高桥禁一副 $B$ ，青木禁一副 $A$ ），然后同时从自己未被禁的牌中声明一副使用并战斗一次。已知 $X_{i,j}$ ，且 $p_{i,j}=X_{i,j}/10^6$ 为高桥用 $A_i$ 、青木用 $B_j$ 时高桥的胜率。双方都知道全部 $p_{i,j}$ ，且都以"最大化对方使坏后的最小胜率"（maximin 策略）行动，可以使用混合策略。求高桥最终的胜率（已证明无论具体策略如何选取，该值是唯一的）。共 $T$ 组测试。

思路

1. 博弈论基础：为什么答案是唯一确定的

这是一个常数和博弈（双方胜率之和恒为 1），可视为零和博弈。设高桥选择（混合）策略 $x$ 、青木选择 $y$ 时高桥的期望胜率为 $E(x,y)=x^T A y$ （ $A$ 为收益矩阵）。"maximin"策略即高桥取

\arg\max_x \min_y E(x,y),

青木取 $\arg\min_y \max_x E(x,y)$ 。Minimax 定理（可通过线性规划对偶证明，有限零和博弈总是成立）断言

\max_x \min_y E(x,y) = \min_y \max_x E(x,y) =: V

而 $V$ 与具体最优策略的选取无关（对任意最优对 $(x^*,y^*)$ ， $E(x^*,y^*)=V$ ），这就是"结果唯一确定"的原因。同时这一策略对恰好构成混合策略意义下的 Nash 均衡：给定对方策略，任何一方单方面改变策略都不会增加自己的期望收益。

2. 倒推：把两阶段博弈拆成两个零和博弈

禁令阶段与选牌阶段都是"同时行动"，因此可以从后往前倒推：

选牌阶段：对每一对"被禁的牌" $(A_i, B_j)$ ，剩下的博弈是一个 $(N-1)\times 2$ 的矩阵博弈（高桥剩 $N-1$ 副、青木剩 2 副），其值记为 $V_{i,j}$ 。
禁令阶段：高桥选择禁哪张 $B$ （3 种），青木选择禁哪张 $A$ （ $N$ 种），对应的收益就是 $V_{i,j}$ 。这是一个 $3\times N$ 的矩阵博弈，其值就是最终答案。

3. 选牌阶段子博弈：把 $V_{i,j}$ 一次算完

固定 $j$ ，设剩下的两列（青木的牌）为 $B_{c_1}, B_{c_2}$ 。青木的混合策略只需一个参数：以概率 $x$ 用 $B_{c_1}$ 、以概率 $1-x$ 用 $B_{c_2}$ 。若青木选了 $x$ ，高桥会挑对自己最有利的行，得到

\max_{k\neq i}\Big(p_{k,c_1}x + p_{k,c_2}(1-x)\Big) = \max_{k\neq i} L_k(x)

其中 $L_k(x)=(p_{k,c_1}-p_{k,c_2})\,x + p_{k,c_2}$ 是一条直线（斜率为 $p_{k,c_1}-p_{k,c_2}$ ，截距为 $p_{k,c_2}$ ）。青木想最小化它，故

V_{i,j} = \min_{0\le x\le 1}\ \max_{k\neq i} L_k(x)

即：去掉直线 $L_i$ 后，其余 $N-1$ 条直线的上包络在 $[0,1]$ 上的最小值。

直接对每个 $i$ 重新求是 $O(N^2\log N)$ 的，太慢。利用一个关键事实可以批量处理：

设所有 $N$ 条直线的上包络 $E(x)=\max_k L_k(x)$ 在 $[0,1]$ 上于 $(x_0,y_0)$ 处取得最小值，那么对除至多 2 条"关键直线"外的所有 $i$ ，都有 $V_{i,j}=y_0$ 。

原因是：只有那些在 $x_0$ 处构成上包络的直线（即在 $x_0$ 处取值达到 $y_0$ 的包络直线）在被删除后才会改变包络的最小值。而上包络是分段线性凸函数，其最小值点 $x_0$ 处至多由两条直线相交决定（若三条及以上直线共点，删掉其中任何一条包络都不变；若最小值在端点 $x=0$ 或 $x=1$ 取得，也只需一条直线）。于是：

用"凸包 trick"（斜率排序 + 单调栈）建出上包络，在 $[0,1]$ 上三分求 $(x_0,y_0)$ ；
找出关键直线集合 $S$ （ $|S|\le 2$ ）；
对 $i\notin S$ ，令 $V_{i,j}=y_0$ ；对 $i\in S$ ，删掉 $L_i$ 重建上包络再三分求最小值。

注意一个细节：若有多行对应完全相同的直线，删除其中一行后相同直线仍在，包络不变，因此只有当某关键直线被唯一的一行拥有时，那一行才需要重算。

4. 禁令阶段：求解 $3\times N$ 的矩阵博弈

现在拿到矩阵 $V$ （行 = 高桥禁 $B_j$ 的选择， $j=1,2,3$ ；列 = 青木禁 $A_i$ 的选择， $i=1,\dots,N$ ；元素 $V_{i,j}$ ）。高桥选混合策略 $x\in\Delta_3$ ，青木针对地选择使其期望最小的一列，所以最终值

\text{ans} = \max_{x\in\Delta_3}\ \min_{i}\ \sum_{j=1}^{3} x_j\, V_{i,j}

由第 3 步的结论，对每个 $j$ 只有至多 2 个 $i$ 使 $V_{i,j}$ 偏离基准值 $y_0^{(j)}$ ，因此列向量 $(V_{i,1},V_{i,2},V_{i,3})$ 至多只有 $O(1)$ 种不同取值，去重后列数变成常数。剩下的问题是一个 3 变量 LP：

\max_{x_1+x_2+x_3=1,\ x_j\ge 0}\ \min_{i\in\text{去重后的列}}\ \big(x_1 V_{i,1}+x_2 V_{i,2}+x_3 V_{i,3}\big)

被优化的函数是若干仿射函数的逐点最小值，因而是凹的；把其中一个变量（比如 $x_1$ ）固定后，对 $x_2$ 的限制仍凹，而"对凹函数先取内层最大值"得到的外层函数也保持凹性（可证）。因此可以用双重嵌套三分求解：外层三分 $x_1\in[0,1]$ ，内层三分 $x_2\in[0,1-x_1]$ ， $x_3=1-x_1-x_2$ 。每次对列求 $\min$ 的代价是常数（列数 $O(1)$ ）。

数值注意： $p_{i,j}=X_{i,j}/10^6$ ，用 long double 存储；三分迭代 150 次精度足够达到 $10^{-6}$ 的误差要求。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ld = long double;

struct Line {
    ld a, b;  // y = a*x + b
};

// 两条直线交点横坐标（斜率不同）
ld interX(Line l1, Line l2) {
    return (l2.b - l1.b) / (l1.a - l2.a);
}

// 若干直线 y = a*x + b 的上包络（最大值），斜率按升序排序
struct Hull {
    vector<Line> lines;
    vector<ld> startX;  // lines[k] 在 [startX[k], startX[k+1]) 上最优
    void build(vector<Line> in) {
        sort(in.begin(), in.end(), [](const Line& u, const Line& v) {
            if (u.a != v.a) return u.a < v.a;
            return u.b > v.b;
        });
        lines.clear();
        for (auto& L : in) {
            if (!lines.empty() && lines.back().a == L.a) continue;  // 同斜率只留截距最大的
            while (lines.size() >= 2) {
                int sz = (int)lines.size();
                if (interX(lines[sz - 2], lines[sz - 1]) >= interX(lines[sz - 1], L))
                    lines.pop_back();
                else
                    break;
            }
            lines.push_back(L);
        }
        startX.assign(lines.size(), -1e30L);
        for (int i = 1; i < (int)lines.size(); i++)
            startX[i] = interX(lines[i - 1], lines[i]);
    }
    ld eval(ld x) const {
        int k = (int)(upper_bound(startX.begin(), startX.end(), x) - startX.begin()) - 1;
        k = max(0, min((int)lines.size() - 1, k));
        return lines[k].a * x + lines[k].b;
    }
};

// 上包络（凸函数）在 [0,1] 上的最小值
ld minEnvelope(const Hull& hull) {
    ld lo = 0, hi = 1;
    for (int it = 0; it < 150; it++) {
        ld m1 = lo + (hi - lo) / 3;
        ld m2 = hi - (hi - lo) / 3;
        if (hull.eval(m1) < hull.eval(m2)) hi = m2;
        else lo = m1;
    }
    return hull.eval((lo + hi) / 2);
}

// v[i] = min_{x in [0,1]} max_{k != i} (a_k x + b_k)
vector<ld> computeVi(const vector<Line>& lines) {
    int N = (int)lines.size();
    vector<ld> v(N);
    Hull hull;
    hull.build(lines);

    ld lo = 0, hi = 1;
    for (int it = 0; it < 150; it++) {
        ld m1 = lo + (hi - lo) / 3;
        ld m2 = hi - (hi - lo) / 3;
        if (hull.eval(m1) < hull.eval(m2)) hi = m2;
        else lo = m1;
    }
    ld x0 = (lo + hi) / 2;
    ld y0 = hull.eval(x0);

    // 在 x0 处构成上包络的关键直线（至多两条）
    set<int> essential;
    int k = (int)(upper_bound(hull.startX.begin(), hull.startX.end(), x0) - hull.startX.begin()) - 1;
    k = max(0, min((int)hull.lines.size() - 1, k));
    for (int idx : {k - 1, k, k + 1}) {
        if (idx < 0 || idx >= (int)hull.lines.size()) continue;
        if (fabsl(hull.lines[idx].a * x0 + hull.lines[idx].b - y0) < 1e-10L)
            essential.insert(idx);
    }

    // 只有"唯一拥有该关键直线"的行才是特殊的
    set<int> special;
    for (int idx : essential) {
        Line L = hull.lines[idx];
        int cnt = 0, which = -1;
        for (int r = 0; r < N; r++) {
            if (fabsl(lines[r].a - L.a) < 1e-10L && fabsl(lines[r].b - L.b) < 1e-10L) {
                cnt++;
                which = r;
            }
        }
        if (cnt == 1) special.insert(which);
    }

    for (int r = 0; r < N; r++) v[r] = y0;
    for (int r : special) {
        vector<Line> sub;
        for (int rr = 0; rr < N; rr++)
            if (rr != r) sub.push_back(lines[rr]);
        Hull h2;
        h2.build(sub);
        v[r] = minEnvelope(h2);
    }
    return v;
}

ld evaluate(const vector<array<ld, 3>>& cols, ld x0, ld x1, ld x2) {
    ld best = 1e18L;
    for (auto& c : cols)
        best = min(best, x0 * c[0] + x1 * c[1] + x2 * c[2]);
    return best;
}

// 求解 3 行 × C 列的零和博弈（高桥最大化）
ld solve3N(const vector<array<ld, 3>>& cols) {
    auto innerMax = [&](ld x0) {
        ld lo = 0, hi = 1 - x0;
        for (int it = 0; it < 150; it++) {
            ld m1 = lo + (hi - lo) / 3;
            ld m2 = hi - (hi - lo) / 3;
            if (evaluate(cols, x0, m1, 1 - x0 - m1) < evaluate(cols, x0, m2, 1 - x0 - m2))
                lo = m1;
            else
                hi = m2;
        }
        return evaluate(cols, x0, (lo + hi) / 2, 1 - x0 - (lo + hi) / 2);
    };
    ld lo = 0, hi = 1;
    for (int it = 0; it < 150; it++) {
        ld m1 = lo + (hi - lo) / 3;
        ld m2 = hi - (hi - lo) / 3;
        if (innerMax(m1) < innerMax(m2)) lo = m1;
        else hi = m2;
    }
    return innerMax((lo + hi) / 2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    cout << fixed << setprecision(15);
    while (T--) {
        int N;
        cin >> N;
        vector<array<ld, 3>> p(N);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++) {
                int x;
                cin >> x;
                p[i][j] = (ld)x / 1000000.0L;
            }

        // V[i][j]：A_i 与 B_j 都被禁时的子博弈值
        vector<vector<ld>> V(N, vector<ld>(3));
        for (int j = 0; j < 3; j++) {
            int c1 = -1, c2 = -1;
            for (int t = 0; t < 3; t++)
                if (t != j) {
                    if (c1 == -1) c1 = t;
                    else c2 = t;
                }
            vector<Line> lines(N);
            for (int i = 0; i < N; i++) {
                lines[i].a = p[i][c1] - p[i][c2];
                lines[i].b = p[i][c2];
            }
            auto vi = computeVi(lines);
            for (int i = 0; i < N; i++) V[i][j] = vi[i];
        }

        // 青木的 N 列中至多有 O(1) 种不同的列，去重
        vector<array<ld, 3>> cols;
        for (int i = 0; i < N; i++) {
            array<ld, 3> c = {V[i][0], V[i][1], V[i][2]};
            bool dup = false;
            for (auto& cc : cols)
                if (fabsl(cc[0] - c[0]) < 1e-12L && fabsl(cc[1] - c[1]) < 1e-12L &&
                    fabsl(cc[2] - c[2]) < 1e-12L) {
                    dup = true;
                    break;
                }
            if (!dup) cols.push_back(c);
        }

        cout << (double)solve3N(cols) << "\n";
    }
    return 0;
}

复杂度分析

时间复杂度：每个测试点 $O(N\log N + S^2)$ ，其中 $S$ 为三分搜索的迭代次数（常数 $S\approx 150$ ）。主要开销来自对每个 $j$ （共 3 次）建一次上包络并至多重算 2 次特殊行。
空间复杂度： $O(N)$