Znzryb's Blog
0%

Posted on

题目大意

n 个灯泡，每次选择一个灯泡，它会等概率变成 r/g/b 三种颜色之一。求在最优策略下，让所有灯泡最终同色的最小期望操作次数。

思路讲解

状态压缩为什么不会偏小

这里的状态写成 dp[a][b][c]，其中 a ≥ b ≥ c，只保留三种颜色数量的有序三元组，不再记录哪个数量对应 r/g/b。乍一看，这像是把颜色标签抹掉了，会不会让策略空间变大，从而让期望被算小。

💡 Note: 不会。原因是这道题的颜色标签本身完全对称：r/g/b 只是一组三个名字，操作概率、目标条件、代价都不依赖具体颜色名。

换句话说，任意两个状态只要颜色数量的多重集相同，比如 (5,3,2) 对应红多一点，或者绿多一点，它们只是把颜色名字重命名了一下。最优策略也可以跟着颜色重命名，所以期望值必须相同。

所以排序不是在额外合并“不等价”的状态，而是在把一整类只差颜色命名的等价状态合并。终态也同样忽略颜色：(n,0,0) 表示全红、全绿、全蓝这三个终态的共同代表，它们的期望都为 0。初态和终态都按同一套颜色对称性取商，因此不会影响答案。

真正需要小心的是：排序后做转移时，每次后继状态也必须重新排序；这样才是在等价类之间转移。

1
2
3
4
5
6
7
auto norm = [&](array<int, 3> x) {
    sort(x.begin(), x.end(), greater<int>());
    return x;
};

// 从当前有序状态转移后，必须再次 norm
nxt = norm(nxt);

额外坑：排序压缩后，不能只把“颜色没有变化”当自环；只要转移后的计数重新排序后仍等于当前 (a,b,c)，它就是同一个压缩状态，也要计入自环概率。

1
2
3
4
5
6
7
8
9
cur = (1, 1, 0);
pos = 1;

// b -> a: (2, 0, 0)
// b -> b: (1, 1, 0) self
// b -> c: (1, 0, 1) -> sort -> (1, 1, 0) self

// 所以 self = 2，不能固定乘 3/2；应使用：
E = (known + 1) / (1 - self / 3.0);

反向推导的定位

期望 DP 的建模仍然是正向的：站在当前状态写 “1 + 后继期望的平均”。按 max(a,b,c) 从大到小求值，只是为了让部分后继状态已经算过；这是实现技巧，不是思考方法本身。

正向写期望方程，按层倒序求值只是实现细节。

push / pull 与倒序枚举的判断

push 和 pull 不是写法喜好，而是依赖方向问题。判断标准是：处理到当前状态时，它的值是否已经完整确定；以及当前状态要读取的依赖是否已经算过。

写法 核心判断 适合场景 这题里的结论
push 处理到 cur 时，dp[cur] 已经完整确定，可以放心把贡献分发给 nxt。 DAG 拓扑序、前缀 DP、路径计数、概率分布传播。 排序压缩后有同层和自环，贡献可能推到已经处理过的位置，写起来容易漏。
pull 处理到 cur 时，cur 要读取的 dp[nxt] 都已经算好，然后由方程合成 dp[cur]。 min/max 转移、期望方程、自环移项、同层依赖比较绕的 DP。 本题期望式天然是 E(cur)=1+average(E(nxt))，自环和同层都能在当前方程里统一处理。
  • push：当前 dp[cur] 已经完整确定，把贡献分发给后继。适合 DAG 拓扑序、前缀 DP、路径计数、概率分布传播等场景。
1
2
3
4
// push: dp[u] 已经确定，向外分发贡献
for (auto v : nxt[u]) {
    dp[v] += dp[u] * w;
}
  • pull：当前 dp[cur] 要由若干已知状态合成。适合 min/max 转移、期望方程、自环移项、同层依赖方向复杂的场景。
1
2
3
4
5
// pull: 站在 u，读取已知状态来计算自己
dp[u] = init;
for (auto v : next(u)) {
    dp[u] = combine(dp[u], dp[v]);
}

这题更适合 pull，因为期望式天然是 E(cur) = 1 + average(E(nxt))。如果用 push，必须保证被推到的状态还没处理；但排序后的同层转移会让贡献方向变得麻烦，容易出现“加晚”。pull 则是先看完整当前方程，统计自环，再读取已经算好的后继。

倒序枚举的判断也不是看心理上从哪里出发，而是看依赖谁：算当前状态时，它依赖的状态必须已经算过。依赖更小下标就正序，依赖更大下标或更接近终点的状态就倒序。

枚举方向 判断标准 典型代码 本题对应
正序 dp[cur] 依赖更小的状态，比如 dp[i-1]、更短前缀、更少物品。 for (int i = 1; i <= n; ++i) 如果当前值依赖的是 a 更小 / b 更小的状态，才会正序。
倒序 dp[cur] 依赖更大的状态，或者更接近终点的状态，比如 dp[i+1]。 for (int i = n - 1; i >= 0; --i) 本题 dp[a][b][c] 依赖 a 更大，或同 a 下 b 更大的后继，所以 a、b 都倒序。 
1
2
3
4
5
6
7
8
9
// 正序：dp[i] 依赖 dp[i - 1]
for (int i = 1; i <= n; ++i) {
    dp[i] = f(dp[i - 1]);
}

// 倒序：dp[i] 依赖 dp[i + 1]
for (int i = n - 1; i >= 0; --i) {
    dp[i] = f(dp[i + 1]);
}

对本题的 c > 0 状态，摸 c 后的非自环后继通常是 (a+1, b, c-1) 或同层的 sort(a, b+1, c-1)，也就是 a 更大，或同 a 下 b 更大。因此求值顺序选 a 倒序、b 倒序，让右边 dp[nxt] 先被算好。

1
2
3
4
5
6
for (int a = n - 1; a >= 0; --a) {
    for (int b = a; b >= 0; --b) {
        int c = n - a - b;
        // 计算 dp[a][b][c]
    }
}

一句话：这题是正向建模，反向求值；选择倒序不是因为从终态“反推过程”，而是因为当前状态的期望依赖更接近终态的后继状态。

AC 代码

待补。

心路历程

  • 一开始容易把“倒序求值”误解成“从终态反推期望”。正确区分是：式子按当前状态正向建，代码按层倒序算。

  • 另一个容易卡住的点是排序状态是否会压小答案；本质原因是颜色完全对称，所以这是合法的等价类压缩。

附件

待补 mentor.pdf / 源码附件。

Posted on Edited on

题目大意

原题（CF 2229F） · editorial · jiangly AC

题面

给定长度 nn 的序列 aa 和整数 kk 。可以先任意重排 aa 的元素，然后定义 f(a)f(a) 如下：

  • 令 bb 是长度 kk 的全零数组。

  • 对每个 1≤i≤n1 \le i \le n ，把 aia_i 加到 bb 的任意一个最小元素上。

  • 最终 f(a)=max⁡(b)f(a) = \max(b) 。

求所有重排中 f(a)f(a) 的最大值。

关键自由度：(1) aa 的顺序由我们选；(2) 每步若 bb 里多个元素并列最小，加到哪个由我们选。

数据范围

  • 1≤k≤n≤181 \le k \le n \le 18

  • 1≤ai≤1091 \le a_i \le 10^9

  • ∑2n≤218\sum 2^n \le 2^{18} （所有 testcase 加起来）

  • 时限 1.5 s （“unusually low time limit”）

  • t≤104t \le 10^4 testcase

样例

样例 1（ n=4,k=2,a=[1,2,4,5]n=4, k=2, a=[1,2,4,5] → 8）：题面给的最优重排是 [1,4,2,5][1, 4, 2, 5] ， bb 演化 [0,0]→[1,0]→[1,4]→[3,4]→[8,4][0,0] \to [1,0] \to [1,4] \to [3,4] \to [8,4] ， max⁡(b)=8\max(b) = 8 。

样例 2（ n=8,k=3,a=[3,4,1,3,2,4,5,3]n=8, k=3, a=[3,4,1,3,2,4,5,3] → 11）；样例 3（ n=3,k=1,a=[109,109,109]n=3, k=1, a=[10^9,10^9,10^9] → 3×1093 \times 10^9 ）。

思路讲解

一句话

kk 桶等价， max⁡(a)\max(a) 必能放末位（exchange argument），扔掉它后剩下 n−1n-1 个元素装 kk 桶最大化 min⁡(b′)\min(b') ；这是教科书 “max-min partition”，二分答案 + 状压 DP 贪心凑 ≥k\ge k 个不相交子集每组 sum≥v\mathrm{sum} \ge v 。

第 1 步：复杂度预算反推算法

∑2n≤218\sum 2^n \le 2^{18} 几乎就是 bitmask DP 的明牌信号。每个 mask 一次 O(n)O(n) 转移： 218⋅18≈5×1062^{18} \cdot 18 \approx 5 \times 10^6 ，外层套二分 log⁡A\log A 系数 ≈35\approx 35 倍还在 10810^8 以内，1.5 s 紧但能过（“unusually low time limit” 就是预算线索）。

第 2 步：把 bb multiset 压成标量——但 simulate 不通

直觉上 dp 状态要追踪当前 bb （长度 kk 的 multiset），但 bb 是 kk 维大整数 tuple， ∑a≤1.8×1010\sum a \le 1.8 \times 10^{10} ，装不进 dp 下标。

min⁡(b)\min(b) 是"每步加 aia_i 的动作锚点"，但单独追踪它不够——加完后新 min 是谁还要看其它桶。死磕 “naive simulate” 路线状压压不下来。

关键扭转：我们不需要 sufficient state 来 simulate。只关心最终的 max⁡(b)\max(b) 这一个数，从这个数倒推就豁然开朗。

第 3 步：Observation 1 —— max⁡(a)\max(a) 必能放末位

设序列里最后处理的元素是 alasta_{\text{last}} ，最后一步把它加到某个 min 桶上。最终：

max⁡(b)final=max⁡(max⁡(bbefore), min⁡(bbefore)+alast)\max(b)_{\text{final}} = \max\bigl(\max(b_{\text{before}}),\ \min(b_{\text{before}}) + a_{\text{last}}\bigr)

直觉：右项 alasta_{\text{last}} 越大越占便宜。严格证明用 exchange argument——若最优重排里 max⁡(a)\max(a) 不在末位，把它换到末位可证 max⁡(bfinal)≥ans\max(b_{\text{final}}) \ge \text{ans} 。两 case 分类（ yy 原桶仍是 min / xx 原桶变成 min）见 editorial 与配套 HTML 演示（下方"动画与源码"节）。

结论：从一开始就锁定 alast=max⁡(a)a_{\text{last}} = \max(a) 。

第 4 步：Observation 2 —— 子问题转化为 max-min partition

记 x=max⁡(a)x = \max(a) ， a′=a∖{x}a' = a \setminus \{x\} ， b′b' = 用 a′a' 处理完后的 bb 状态。

引理： max⁡(b′)−min⁡(b′)≤max⁡(a′)≤x\max(b') - \min(b') \le \max(a') \le x （归纳易得：每步加 aia_i 到 min 桶，差要么不增、要么变成 ≤ai\le a_i ）。

→ min⁡(b′)+x≥max⁡(b′)\min(b') + x \ge \max(b') 恒成立。所以：

max⁡(b)final=max⁡(max⁡(b′), min⁡(b′)+x)=min⁡(b′)+x\max(b)_{\text{final}} = \max\bigl(\max(b'),\ \min(b') + x\bigr) = \min(b') + x

原问题完全等价于：用 n−1n-1 个元素 a′a' 装 kk 桶，最大化最终 min⁡(b′)\min(b') 。

更进一步（editorial 给的 greedy 构造）：过程约束可以丢。任意一种把 a′a' 划分成子集的分法 {Sj}\{S_j\} （每个 sum(Sj)≥v\mathrm{sum}(S_j) \ge v ），都能找到合法重排 + tie-breaking 使最终每桶恰好是 SjS_j （每次从 SjS_j 里挑剩余最大的元素加）。所以划分本身就是充要条件：

check( vv ) = 能否把 a′a' 划分成 ≥k\ge k 个不相交子集，每个 sum≥v\mathrm{sum} \ge v ？

第 5 步：bitmask DP 的关键 trick —— kk 桶等价 + 贪心凑子集

新手一看 check( vv ) 容易想成"每个物品 kk 种状态"（分到哪个桶），状态空间 knk^n 爆。

关键观察：题目里 kk 个桶是匿名等价的（不区分 id，只看 multiset）。所以 check( vv ) 等价于"贪心一个一个凑子集"——把"凑子集"想成线性流水线：开始 → 凑组 1 → 凑组 2 → … → 凑 ≥k\ge k 组 → ✓。

任意时刻状态就两个标量：

  • 已封口的合格组数 cnt\text{cnt} —— 已经凑出几个 sum≥v\mathrm{sum} \ge v 的不相交组。

  • 当前未封口组的累加和 cur\text{cur} —— 还差 v−curv - \text{cur} 就能再封一组（ cur<v\text{cur} < v ）。

加上 mask（哪些元素已用）， dp[mask]=(cnt,cur)dp[\text{mask}] = (\text{cnt}, \text{cur}) 就够了。

第 6 步：DP 转移

push 风格（jiangly 写法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (int s = 0; s < (1 << n); s++) {
    auto [cur, sum] = dp[s];
    for (int i = 0; i < n; i++) {
        if (~s >> i & 1) {                  // i 不在 s 里
            int t = s | 1 << i;
            int ncur = cur;
            i64 nsum = sum + a[i];          // 把 a[i] 塞进未封口组
            if (nsum >= x) {
                ncur++;
                nsum = 0;                   // 封一个组, leftover 归 0
            }
            dp[t] = std::max(dp[t], std::make_pair(ncur, nsum));
        }
    }
}
return dp.back().first >= k;                // 全集 mask 上至少 k 个组

字典序取 max：先比 cnt 后比 sum 。为什么不只比 cnt？ 同 cnt 下更大 sum 意味着未封口组更接近封口，未来加 1 个元素可能再封一组 → 保留更大 sum 更优（这是经典 max-min partition DP 的字典序套路）。

第 7 步：二分 + 答案

  • 二分上界： min⁡(b′)≤∑a′/k≤∑a\min(b') \le \sum a' / k \le \sum a ， U≈2×1010U \approx 2 \times 10^{10} ， log⁡≈35\log \approx 35 。

  • check 一次 O(2n−1⋅(n−1))O(2^{n-1} \cdot (n-1)) 。

  • 总： O(2n−1⋅(n−1)⋅log⁡U)O(2^{n-1} \cdot (n-1) \cdot \log U) ， n=18n=18 时 ≈217⋅17⋅35≈7.8×107\approx 2^{17} \cdot 17 \cdot 35 \approx 7.8 \times 10^7 。

  • 答案 = vmax⁡+max⁡(a)v_{\max} + \max(a) 。

退化 case 校验

  • n=1,k=1n = 1, k = 1 ：弹出 max⁡\max 后 a′a' 空，dp 全 0， check 恒 false → ans=0+a0=a0\text{ans} = 0 + a_0 = a_0 ✓

  • k=1k = 1 ：全部元素装一桶，答案 = ∑a\sum a ✓（check( ∑a′\sum a' ) 时整个 a′a' 一组凑成）

  • n=kn = k ：每桶恰一元素，答案 = max⁡(a)\max(a) ✓

📎 动画与源码

附在末尾「附件」节：

  • exchange-argument.html —— 交互式可视化。上半 4 个 preset 数值 demo 看 swap 前后桶演化；下半 Case A / B 抽象代数证明配图（柱高只标 a,b,c,ans,ans-ya, b, c, \text{ans}, \text{ans-y} 等代数符号，5 步分步动画）。

  • mentor.pdf —— 完整带教对话录（从复杂度预算反推 → Observation 1/2 → bitmask DP 状态设计每一步的引导问题 + me/Claude 气泡留底）。

  • 2229F.cpp.txt —— 用户的 AC 实现（push DP，含调试日志宏 + Gosper hack 枚举子集）。

AC 代码

AC 提交链接（jiangly 写法参考）

展开完整 C++ 源码（jiangly 风格 push DP） 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using i64 = long long;
namespace rgs = std::ranges;

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) std::cin >> a[i];
    rgs::sort(a);

    n--;
    int last = a[n];
    a.resize(n);

    auto check = [&](i64 x) {
        std::vector<std::pair<int, i64>> dp(1 << n);
        for (int s = 0; s < (1 << n); s++) {
            auto [cur, sum] = dp[s];
            for (int i = 0; i < n; i++) {
                if (~s >> i & 1) {
                    int t = s | 1 << i;
                    int ncur = cur;
                    i64 nsum = sum + a[i];
                    if (nsum >= x) {
                        ncur++;
                        nsum = 0;
                    }
                    dp[t] = std::max(dp[t], std::make_pair(ncur, nsum));
                }
            }
        }
        return dp.back().first >= k;
    };

    i64 lo = 0, hi = 2E10;
    while (lo < hi) {
        i64 x = (lo + hi + 1) / 2;
        if (check(x)) lo = x;
        else          hi = x - 1;
    }
    std::cout << lo + last << "\n";
}

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

心路历程

写自己的版本时（pull DP + Gosper hack 枚举固定 popcount 的 sta）一上来踩了两个 bug，自己 debug 出来的：

Bug 1：外层 use 从 1 起，跳过了 use=0 这一层

1
2
3
4
5
6
for (int use = 1; use <= N_1; ++use) {
    long long sta = (1LL << use) - 1;
    while (sta < (1LL << N_1)) {
        // ...
    }
}

use = 当前 source mask sta 的 popcount。从 use=1 起，意思是从 popcount=1 的 mask 出发往外推。唯一显式 init 的只有 dp[0] = {0, 0} 这一格， dp[1] / dp[2] / dp[4] (popcount=1) 这些从未被 dp[0] 推出过，直接拿来当 source 时读到的是 vector default 的 (0,0)——丢了 A[0]A[0] 这个元素。

跳 use=0 的真原因：Gosper’s hack 在 sta=0 时 c = sta & -sta = 0 除零崩。正确做法：要么外层 for use = 0 ，要么手动展开 use=0 那一层从 dp[0] 推到所有 dp[1<<i] 。

Bug 2：vis[sta] 跟踪的是 source，但应该跟踪 target

1
2
3
4
5
6
if (vis[sta] == tim) {
    dp[sta | (1ll << i)] = max(now, dp[sta | (1ll << i)]);
} else {
    vis[sta] = tim;
    dp[sta | (1ll << i)] = now;
}

想做"延迟清空 dp"——多次 check 复用 dp 数组，靠 vis[?] == tim 判断"本次 check 是否已 init"。但 vis 应该追踪 target sta | (1<<i) 是否被本次 init 过，写成了 source sta 。后果：

  • sta=1, i=1 推 dp[3] ： vis[1] != tim → else， dp[3]=(0,2) 直接覆盖（OK）。

  • sta=2, i=0 推 dp[3] ： vis[2] != tim → else， dp[3]=(0,1) 又一次直接覆盖前面的 (0,2) ，没走 max。

每个新 source 第一次进 else 时都会"无条件覆盖"它推出的所有 target——把别的 source 已经 init 过的 dp[target] 丢掉。

正确写法：

1
2
3
int t = sta | (1ll << i);
if (vis[t] == tim) dp[t] = max(now, dp[t]);
else { vis[t] = tim; dp[t] = now; }

验证

两个 bug 都让 check(3) 对样例 1 错返 false，二分塌到 lo=0 ，输出 0 + max(a) = 5 ，期望 8 。修完两条后 sample 全过。

附件

exchange-argument.html 关键帧（Case A 抽象代数证明）

step 0：4 个桶 P, Q₂, Q₃, Q₄（P 是当前最大桶），还未画 y 段 / 虚线 / 关系标签

step 2：P 顶 y 段 hatch 出现 + 顶部 ans 标线 —— 现在能看到 P 是最大桶、顶段是 y

step 4：其它桶 a, b, c 全标出 + ans−y 横虚线 —— 几何上能直接读出 a, b, c ≥ ans−y

完整 5 步动画（含 Case B 抽象证明）见下方 exchange-argument.html.txt（下载后改回 .html 用浏览器打开 = 可点 Step 看每一帧）。

mentor.pdf — 完整带教对话录

从复杂度预算反推 → Observation 1/2 → bitmask DP 状态设计的全过程引导问答 + me/Claude 气泡留底

源码 & HTML 本体

2229F.cpp.txt

exchange-argument.html.txt

Posted on Edited on

题目大意

牛客 NC15086「向左走」。多组数据（不超过 10 组）。每组给 nn 根杆子（ 1≤n≤10001\le n\le 1000 ），坐标范围 [1,1000][1,1000] 且互不重合。

你拿着绳子从某根杆子出发，规则有四条：只能向左转或直行（绝不右拐）、只能走直线、走过的路不能与自己相交、每根杆子最多经过一次。起点固定为 yy 最小、 yy 相同取 xx 最小 的那根杆子。

目标：经过尽量多的杆子（其实可以全部经过），输出经过杆子的编号顺序。

样例

4 根杆子 1(3,1) 2(7,1) 3(5,3) 4(5,5)1(3,1)\,2(7,1)\,3(5,3)\,4(5,5) ，输出 1 2 4 3 。从最低点 11 出发，外圈是三角形 {1,2,4}\{1,2,4\} 逆时针描一遍，剩下的 33 在最里面，最后串上。

思路讲解

一句话

洋葱剥皮（onion peeling）螺旋：从最低点出发，沿点集的凸包逆时针描一圈；描完把这一圈的点剥掉，剩下的点又是一个点集，对它再描一圈，像蚊香一样越绕越往里。难点全在两层之间怎么衔接——内层的入口不能随便选，否则会右转或自交。

「只能向左转」= 朝向角单调逆时针旋转

你每到一根杆子要么直行要么左拐、永远不右拐，等价于说：你的前进方向（朝向角）只会朝一个方向累积旋转，绝不回头。这是个很强的约束——它把"路径"逼成一条逆时针卷进去的螺旋。

沿最外圈 = 逆时针描凸包

站在最低点、朝向只能左转，那么"贴着最外圈走出来的轨迹"恰好就是把点集的凸包按逆时针描一遍：第一步沿凸包下边迈出去（朝最贴右的方向，使其余所有点都在你左手边），之后每到一个顶点左拐，逆时针绕完外圈。所以第一步方向就被钉死了。

关键不变量：起点是全局最低点，外层凸包按逆时针（CCW）输出，第一条边朝向使所有点在左手侧。

钻进内层 = 递归同类子问题

外圈只串起了边界上的杆子，里面还有没碰到的。绕完一圈快回到起点时往里钻一层——而内部剩下的杆子本身又是一个点集，面对的规则一模一样（从它的最外层开始、只能左转、不自交）。所以整个算法就是反复做同一个动作：

  1. 对当前剩余点求凸包（CCW），输出这一层；

  2. 把这层的点删掉，对剩点重复。

关键①：内层入口怎么选（续接式入口，不是重置最低点）

这是本题最容易写错、也是我这次真栽进去的地方。一个自然但错误的写法是：对每一层都调用"找该层字典序最小点、旋转到开头"（即 reorder_polygon）。第一层这么做对（全局最低点就是螺旋起点），但内层这么做就错了——内层会从它自己的最低点起头，而那个点未必接得上上一层的螺旋，会在层边界右转或让连接边穿过内层造成自交。

正确做法是续接式入口：设上一层走完停在末顶点 ee ，进入 ee 时的前进方向是 d→\overrightarrow{d} 。对内层这个 CCW 多边形，入口顶点 ww 取使 d→\overrightarrow{d} 逆时针转到 w−e→\overrightarrow{w-e} 的转角最小的那一个，再从 ww 起按 CCW 走完内层。直觉就是：朝向只能继续逆时针转，那就贴着当前方向最小幅度地左转钻进去，绳子贴着自己往里收，绝不会右拐、也不会去穿别的边。

w=arg⁡min⁡v∈L ccwAngle(d→, v−e→)w = \arg\min_{v \in L}\ \mathrm{ccwAngle}(\overrightarrow{d},\ \overrightarrow{v - e})

红色结论：内层入口必须续接上一层的前进方向（极角基准 = 上一层末顶点 ee ），绝不能重置成内层自己的最低点。后者就是 WA 的来源。

这条规则在 5000 组随机点集上 100% 产出"全程左转 + 无自交"的合法路径，样例也吻合。

关键②：共线层的退化处理

剥到某一层时，如果剩下的点恰好全共线，凸包退化成一条线段。此时弱凸包（保留共线点）的 Andrew 扫描会折返：上行扫一遍再下行扫回来，输出形如 A B C B 的重复序列——同一个点被走两遍，输出就不是全排列，直接 WA。

处理：对一层的凸包用有向面积判退化（面积为 0 即全共线），退化时这层的点已经按排序顺序排好且互不重复，直接当一条线"单程"返回即可，不折返。这一步是 O(n)O(n) 的，不要写成两两比对的 O(n2)O(n^2) 去重。

复杂度

每层一次凸包 O(nlog⁡n)O(n\log n) ，最多 O(n)O(n) 层，整体 O(n2log⁡n)O(n^2\log n) 。 n≤1000n\le 1000 、不超过 10 组，稳过。

📎 动画与源码

我做了一个交互式 HTML 演示，可以一步步点 Step 看每个拐点的转向叉积，对比"修正前 vs 修正后"内层入口的差别（右转/自交怎么发生、续接式入口怎么修好）。本体和关键帧截图见附件节。

AC 代码

AC 提交（vjudge）

完整源码较长（含整套几何模板），折叠如下：

心路历程（本题真实 debug 链）

这道题本地样例过、提交却 WA，挖出来是一条挺长的链：

  • 层边界右转：最早用 reorder_polygon 对每层重排到"该层最低点"。第一层对，内层错——构造出 n=5 反例 1(11,9) 2(1,11) 3(10,2) 4(9,8) 5(5,9)1(11,9)\,2(1,11)\,3(10,2)\,4(9,8)\,5(5,9) ，外层 {3,1,2}\{3,1,2\} 描完，内层从自己最低点 44 进，路径 2→4→52\to4\to5 在 44 处右转（叉积 −4-4 ）。随机测 4 万组，约 15% 非法（右转 + 自交两种症状）。

  • 续接式入口：改成"从上一层前进方向逆时针扫，第一个扫到的内层顶点当入口"（ ccwAngle\mathrm{ccwAngle} 最小），右转和自交都消失。

  • 两个实现 bug：(1) 取 argmin 时 mn_angle = angle 写反成 angle = mn_angle ，导致永远选最后一个；(2) rotate 转错容器（转了已拼好的答案 ans ，应该转新层 convex_poly ）。

  • 共线层折返：修完上面随机测仍有约 0.7% WA，全是"剩余点共线 → 弱凸包折返出重复点 → 非全排列"。加有向面积判退化后，2 万随机 + 2 千全共线专测 100% 通过。

教训：几何题"本地样例过 ≠\ne 对"，对拍要主动覆盖共线 / 退化 / 多层嵌套形状，光靠样例和近圆形点集测不出来。

附件

下方挂了交互式演示 HTML 本体（下载后改回 .html 用浏览器打开，可一步步点 Step）、几个关键帧截图，以及完整带教对话录 PDF。

演示初始：从最低点 3 出发，外层凸包 {3,1,2} 逆时针描

逆时针走完外层到末顶点 2

修正前：内层从自己最低点 4 进入，路径 2→4→5 在顶点 4 处右转（cross=-4）违规——这就是 bug。修正后改从 5 进入则全程左转

reorder_polygon_bug.html.txt

完整带教对话录（PDF 版）

Posted on

题目大意

给定三角形三个顶点 A(Xa,Ya)A(X_a,Y_a)、B(Xb,Yb)B(X_b,Y_b)、C(Xc,Yc)C(X_c,Y_c) 的整数坐标，求三件事：

  • 三角形面积（保留 1 位小数）

  • 三角形内部的整点个数

  • 边 ABAB、BCBC、ACAC 上的整点个数（都不含三角形顶点）

输入输出与数据范围

多组输入，每组三行各两个整数（依次是 A、B、C 的坐标），读到 -1 结束。0≤X,Y≤1060 \le X,Y \le 10^6。

每组输出一行：先一个保留 1 位小数的面积，再依次输出 4 个整数——内部整点数、ABAB、BCBC、ACAC 边上的整点数，空格隔开。

样例

1
2
3
4
5
6
7
8
9
10
11
12
输入
0 0
2 0
0 2
0 0
3 0
0 3
-1

输出
2.0 0 1 1 1
4.5 1 2 2 2

思路讲解

一句话

整道题就是 Pick 定理 套一个 线段格点数公式，没有任何数据结构，纯数论 + 一次叉积。三件事：

  • 面积 = 叉积绝对值的一半；

  • 一条边上的整点数（不含端点） =gcd⁡(∣dx∣,∣dy∣)−1= \gcd(|dx|,|dy|) - 1；

  • 内部整点数走 Pick 定理反解。

边上的整点数 = gcd − 1

把边的方向 (dx,dy)(dx,dy) 除掉公因子 g=gcd⁡(∣dx∣,∣dy∣)g = \gcd(|dx|,|dy|)，得到 本原向量 (dx/g, dy/g)(dx/g,\,dy/g)——它两个分量互质，是这条方向上「最短的整点步长」。整段恰好等于走 gg 个本原向量。

关键不变量：每跳一个本原向量正好落在一个整点上，跳 gg 步到终点。于是线段上一共 g+1g+1 个整点（含两端），掐掉两个端点就是 g−1g-1 个。

为什么不多也不少，分两个方向（就像证等式要证两边）：

  • 存在性：第 kk 个等分点坐标是 (k⋅dx/g, k⋅dy/g)(k \cdot dx/g,\, k \cdot dy/g)，因为 dx/g,dy/gdx/g, dy/g 是整数，乘整数还是整数，所以这 g+1g+1 个点全是整点。

  • 唯一性：相邻两个等分点之间正好是一个本原向量（互质）。设其内部还有整点，则它满足 x/a=y/b=t∈(0,1)x/a = y/b = t \in (0,1)，把 tt 写成最简分数 p/qp/q，需要 q∣aq \mid a 且 q∣bq \mid b，于是 q∣gcd⁡(a,b)=1q \mid \gcd(a,b) = 1，逼出 q=1q = 1、tt 是整数，与 t∈(0,1)t \in (0,1) 矛盾。所以一个本原步内部挖不出整点。

主演示：拖蓝点 B 改线段，点 Step 沿本原向量一步步走。图中 (9,6)、g=3、本原向量 (3,2)，线段内部有 g-1=2 个整点（绿点）。

Pick 定理求内部点

Pick 定理：面积 S=I+B2−1S = I + \frac{B}{2} - 1，其中 II 是内部整点数、BB 是边界整点数。反解出内部点：

I=2S−B2+1I = \frac{2S - B}{2} + 1

  • 2S2S 直接用叉积绝对值，是整数，全程不碰浮点；

  • BB = 三条边的 gcd⁡\gcd 之和（含顶点，见下一节）。

边界点 B 含不含顶点？含。

这是最容易混的地方，要分清两个量：

  • 输出给题目的「边上点数」：用 gcd⁡−1\gcd - 1，不含顶点（题目明确要求）；

  • Pick 用的边界点 BB：用 ∑gcd⁡\sum \gcd，含顶点。

绕多边形一圈，每条边的 gcd⁡\gcd 恰好把它的「一个端点」算进来，三条边加起来每个顶点不重不漏算一次：

B=∑gcd⁡=(顶点数)+(各边内部点数)B = \sum \gcd = (\text{顶点数}) + (\text{各边内部点数})

代码里我存的是 gcd - 1 这种「不含端点」的值，所以补回 3 个顶点：B=(dotAb+dotAc+dotBc)+3B = (dotAb + dotAc + dotBc) + 3。两个量差的正好是 3 个顶点，千万别混用。

三角形 + Pick 联动：拖顶点看三边 gcd-1、边界 B、面积 S、内部点 I 怎么变。图中 2S=47、B=3（即三个顶点）、I=23。

📎 动画与源码

下方附了一个交互式 HTML 演示：可以拖线段、点 Step 一步步看本原向量怎么把线段切成 gg 等份，还能拖三角形顶点看 Pick 各量联动。几张关键帧也截在这一节里。

AC 代码

牛客已 AC。核心全在 Solve()：面积走几何模板的 polygonArea，边上点数用 __gcd，内部点 Pick 反解；输出顺序按题目要求是 AB,BC,ACAB, BC, AC。

心路历程

调这道签到题反而栽了两个一模一样隐蔽的 off-by-one，而且两个样例都因为是「等腰直角三角形」太对称、把 bug 全藏住了：

  • Pick 反解少加 1：一开始写成 I = (2S - B + 1) / 2，正确是 I = (2S - B)/2 + 1 = (2S - B + 2)/2。少加的那个 1 在样例 1 里因为整数除法 -1/2 向零截断碰巧得 0、蒙混过关；样例 2 的 1/2 = 0 才露馅（期望是 1）。

  • 输出顺序 AC / BC 写反：题目要 AB,BC,ACAB, BC, AC，我手滑写成了 AB,AC,BCAB, AC, BC。两个样例三条边整点数全相等，交换看不出来；一旦数据是不规则三角形（AC≠BCAC \ne BC）立刻 WA。

教训：对称样例是 off-by-one 的天然伪装。这种题最好自己手造一个三边都不等、内部点也不为 0 的三角形（比如 A(1,1),B(8,2),C(3,8)A(1,1), B(8,2), C(3,8)，2S=472S = 47、B=3B = 3、I=23I = 23）验一遍再交。

附件

segment_lattice_gcd.html.txt

Posted on Edited on

题目大意

CF gym 105231 I - Neuvillette Circling | rating 2100 | 2024 (ICPC) 江西省赛 武大 WHU 命题组 | n≤100n \le 100 ，时限 2 秒

给 NN 个宝藏在平面上 (xi,yi)(x_i, y_i) ，任意两个宝藏之间有一条线段（路径），每条路径上有一个丘丘人——它可能出现在线段上的任意一点（位置对抗性）。Neuvillette 画一个圆（圆心任选、半径要最小），圆上或圆内的丘丘人被秒。

要求：无论这些丘丘人具体站在各自线段的哪个位置，他都能至少干掉 mm 个。对 m=1,2,…,(n2)m = 1, 2, \dots, \binom{n}{2} 分别输出最小半径。

数据范围

  • 2≤n≤1002 \le n \le 100

  • −103≤xi,yi≤103-10^3 \le x_i, y_i \le 10^3 ，坐标全是整数

  • 保证无两点重合 / 无三点共线

  • 答案精度 10−610^{-6}

样例 ( n=5n = 5 )

输入：

1
2
3
4
5
6
5
-6 -9
2 4
9 2
1 -1
-4 -5

输出（10 行）：

1
2
3
4
5
6
7
8
9
10
2.23606798
4.28602124
4.28602124
7.38241153
7.38241153
7.38241153
9.30053762
9.30053762
9.30053762
9.30053762

思路讲解

一句话

对抗性建模 →\to 「包住整段」等价于「包住两端点」（圆盘是凸集） →\to 圆里有 kk 个原始点就保证 (k2)\binom{k}{2} 条边的丘丘人都被秒 →\to 题目变成 对每个 kk 求最小 kk 点覆盖圆。MEC 定理给出候选圆只有 O(n3)O(n^3) 个：两点直径 + 三点外接。总复杂度 O(n4)O(n^4) ， n=100n = 100 下宽松到不用卡常。

Step 1：对抗性建模——把「覆盖一条边」翻译成「包住两个点」

题目说丘丘人可能出现在线段任意一点，又要求无论它在哪都得能杀掉。这是经典对抗设定：玩家先确定圆，丘丘人才挑位置。

「保证这条边上的丘丘人被秒」 ⟺\Longleftrightarrow 「整条线段在圆盘内」

否则对手把丘丘人放在圆外那一点。

再用「圆盘是凸集」收一刀——圆盘内任意两点的连线段仍在圆盘内：

整条线段在圆盘内 ⟺\Longleftrightarrow 线段两端点都在圆盘内

这一步把「覆盖一条边」降级为「包住它的两个端点」，几何复杂度直接塌一档。

Step 2：从覆盖边到覆盖点—— (k2)\binom{k}{2} 平台结构

承接上一步。如果圆盘里有 kk 个原始点，这 kk 个点两两之间共 (k2)\binom{k}{2} 条边、其两端点都在圆内 ⇒\Rightarrow 这 (k2)\binom{k}{2} 条边上的丘丘人全保证被秒。

所以题目等价为：

对每个 k=2,3,…,nk = 2, 3, \dots, n ，求「至少包住 kk 个原始点的最小圆」的半径 ansk[k]\mathrm{ans}_k[k] 。

输出时，给定 mm 找最小的 kmk_m 满足 (km2)≥m\binom{k_m}{2} \ge m ，那个槽的最小半径就是答案。代码里更优雅的写法：把每个候选圆按 (in_cir_cnt2)\binom{\text{in\_cir\_cnt}}{2} 直接落到 mn_rad[ans] 槽，最后做一遍 suffix-min 把「更大 mm 的最优半径」向左 propagate 到小 mm 上——殊途同归，省一步反查。

样例的 4 个圆刚好对应 k=2,3,4,5k = 2, 3, 4, 5 四个平台：

| kk | 圆 | 半径 ( ansk[k]\mathrm{ans}_k[k] ) | 管的 mm |

| — | — | — | — |

| 2 | 紫（最近对直径） | 2.236 | 1 |

| 3 | 红（3 点外接） | 4.286 | 2, 3 |

| 4 | 蓝（4 点 MEC） | 7.382 | 4, 5, 6 |

| 5 | 绿（全 5 点 MEC） | 9.301 | 7, 8, 9, 10 |

每个 kk 管 (k2)−(k−12)=k−1\binom{k}{2} - \binom{k-1}{2} = k - 1 个 mm ，正是三角形数 1, 2, 3, 4, ……

Step 3：MEC 定理迁移——候选圆只有 O(n3)O(n^3) 个

MEC（minimum enclosing circle）的关键结构性事实：

MEC 定理： nn 个点的 MEC ，边界圆周上恰好经过 2 或 3 个原始点。

这是 Welzl 随机增量算法的依据。

  • 「至少 2」：反证。如果边界上 0 或 1 个原始点，可以把圆心稍微挪一挪 ++ 半径稍减，所有包含点继续在内 ⇒\Rightarrow 半径更小，矛盾。

  • 「至多 3」：平面上不共线 3 点决定唯一外接圆，题面保证「无三点共线」就是为了避开退化。

关键迁移：本题最优圆 R∗R^* （最小 kk 点覆盖圆）也满足这条结构性质——同样的 shrink/move 论证：若 R∗R^* 边界 b≤1b \le 1 个原始点，可以缩小并保持「含 ≥k\ge k 个点」不变 ⇒\Rightarrow 与最优矛盾。所以 R∗R^* 必定是某个 ∣S∣≥k|S| \ge k 的子集的 MEC，由 2 或 3 个原始点决定。

这一刀把「枚举对象」从点的子集翻转成了圆。

候选圆集合：

  • (n2)\binom{n}{2} 个 两点直径圆（任选两点作直径）

  • (n3)\binom{n}{3} 个 三点外接圆（任选三点的 circumcircle）

规模 O(n3)O(n^3) ，对每个圆 O(n)O(n) 数它包了多少个原始点 →\to 总 O(n4)O(n^4) 。

Step 4：复杂度算账

n=100n = 100 时：

(1002)+(1003)=4 950+161 700≈1.67×105 候选圆\binom{100}{2} + \binom{100}{3} = 4\,950 + 161\,700 \approx 1.67 \times 10^5 \text{ 候选圆}

每圆 ×100\times 100 次数点 →\to 约 1.67×1071.67 \times 10^7 次基本运算。2 秒时限内相当宽松，连卡常都不需要。

Step 5：FP 精度坑——这题的 WA 点

枚举候选圆时，圆的 2 或 3 个定义点本应在边界上（数学上 ∣p−c∣2=r2|p - c|^2 = r^2 恰好相等）。但 circle_from_diameter / outcircle_triangle 算出来的 r = sqrt(d) / 2 后，squared(r) = r * r 经过 sqrt 一来再 square 一回的 round trip，得到的不再是精确的 d/4d/4 ，会有 ULP 级误差：

1
2
3
4
5
d  =  5: r*r = 1.2500000000000002,  d/4 = 1.25
d  = 13: r*r = 3.2499999999999996,  d/4 = 3.25   ← r*r < d/4，边界被判到圆外
d  = 20: r*r = 5.000000000000001,   d/4 = 5.0
d  = 50: r*r = 12.500000000000002,  d/4 = 12.5
d  =113: r*r = 28.250000000000004,  d/4 = 28.25

如果用 dist² <= r² 严格比较，当 r² 偶尔比真值小时，定义点被判到圆外（dist² > r²），漏算 →\to in_cir_cnt 不对 →\to mn_rad[m] 拿不到本该的候选半径 →\to WA。

样例 d=20d = 20 那个紫圆恰好走在 +ε+\varepsilon 一侧（<= 成立、定义点被算入），样例侥幸过；但测试数据里只要撞一个 d=13d = 13 这类形状，定义这个 diameter circle 的 2 个原点就漏算，整个候选圆失效。

修法：用 sgn(dist² - r²) <= 0 容差判定。

1
2
3
4
5
// AC https://vjudge.net/solution/69993234 使用 sgn 避免精度问题
template<class U>
bool is_point_in_circle(const Point<U> &p) {
    return sgn(distancePPNorm(p, c) - squared(r)) <= 0;
}

sgn 把 ∣x∣<ε|x| < \varepsilon 当作 0，吸收 sqrt →\to square 的 ULP 抖动。这个 patch 顺手同步到了 ICPC 几何模板 + espanso :Circle snippet，以后展开就自带正确版。

📎 动画与源码

完整带教对话录 PDF（mentor.tex 编译产物，含 6 步推导 + 我画的 4 个圆草图 + 全过程问答）在末尾附件区，可下载查看。

AC 代码

AC 提交链接（vjudge / Gym-105231I）

核心 Solve() 函数：枚举 (n3)\binom{n}{3} 个外接圆 + (n2)\binom{n}{2} 个直径圆，每个圆 O(n)O(n) 数包含点数，按 (in_cir_cnt2)\binom{\text{in\_cir\_cnt}}{2} 落到 mn_rad 槽，最后 suffix-min 把大 mm 的最优半径向左 propagate。

心路历程（WA → AC）

  • 第一次提交：大数据 WA，样例 AC。算法骨架完全对，suffix-min 也对，输入输出格式也对。

  • 卡点诊断思路：「样例 AC + 大数据 WA + 几何题」三联立基本就是 FP 精度在 boundary 上吞 byte。

  • 定位到 is_point_in_circle 的 dist² <= r² 严格比较——r = sqrt(d)/2 再 squared(r) 跑了一趟 sqrt → square 的 round trip，对 ll 整数输入精度只够覆盖大约半数 dd 值。

  • 样例 d=20d = 20 那个紫圆（直径 (−6,−9)↔(−4,−5)(-6,-9) \leftrightarrow (-4,-5) ）正好走在 +ε+\varepsilon 一侧，所以样例没暴露这个 bug；测试数据撞 d=13d = 13 类形状才漏算。

  • 修法：return sgn(distancePPNorm(p, c) - squared(r)) <= 0; 把硬比较改成 sgn 容差判定，一行改完 AC。

  • 顺便把这个 patch 同步到 ICPC 几何模板 的 Circle struct + espanso :Circle snippet，以后再做几何题展开模板就自带正确版，省一次踩同一个坑。

附件

完整带教对话录（mentor.tex 编译产物 PDF，含 6 步推导）+ AC C++ 源码（.cpp.txt）直接附在下方，可下载查看。

完整带教对话录（mentor.tex 编译产物，6 步推导 + 第 1 步用户手画 4 个圆草图 + 全过程问答 + WA 诊断）

Neuvillette_Circling.cpp.txt