P3958 [NOIP 2017 提高组] 奶酪 · 习题解析

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P3958，日期见页头。两边不一致时信原站。 ⚠ 样例解释那张剖面图也存了一份（public/sol/p3958-sample.png）。

题目描述

现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。在坐标系中，奶酪的下表面为 z = 0，上表面为 z = h。

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞；特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑到奶酪的上表面去？

空间内两点 P₁(x₁,y₁,z₁)、P₂(x₂,y₂,z₂) 的距离公式为 dist = √((x₁−x₂)² + (y₁−y₂)² + (z₁−z₂)²)。

输入格式

每个输入文件包含多组数据。第一行一个正整数 T，代表该输入文件中所含的数据组数。

接下来是 T 组数据，每组第一行包含三个正整数 n, h, r，分别代表奶酪中空洞的数量、奶酪的高度和空洞的半径。接下来 n 行，每行三个整数 x, y, z，表示空洞球心坐标为 (x, y, z)。

输出格式

T 行，如果在第 i 组数据中 Jerry 能从下表面跑到上表面，则输出 Yes，否则输出 No。

说明/提示

样例 1 的三组剖面图

对于 20% 的数据，n = 1；对于 40% 的数据，1 ≤ n ≤ 8；对于 80% 的数据，1 ≤ n ≤ 10³， 1 ≤ h, r ≤ 10⁴，坐标的绝对值不超过 10⁴。

对于 100% 的数据，1 ≤ n ≤ 1 × 10³，1 ≤ h, r ≤ 10⁹，1 ≤ T ≤ 20， 坐标的绝对值不超过 10⁹。

时限 1 秒，内存 250 MB。

输入输出样例

输入

输出

Yes
No
Yes

第一组：(0,0,1) 和下表面相切、(0,0,3) 和上表面相切、两洞在 (0,0,2) 相切 ⇒ Yes。第二组：两洞既不相交也不相切 ⇒ No。第三组：两洞相交且都挨着表面 ⇒ Yes。 ⚠ 第一组三处全是「相切」 —— 记住这句话，第 ④ 步要用它。

1把「两球相交」当成一条边，这就是一道连通性题

p3958.cpp★ 这一版就能 AC（顶格 T = 20 / 每组 n = 1000，本机 80 毫秒）

// P3958 [NOIP2017 提高组] 奶酪 —— ★ 这一版就能 AC
//
// 把「两个空洞相交或相切」当成一条边，就是一道连通性题：
//   下表面当成 0 号虚点（z ≤ r 的洞和它连），上表面当成 n+1 号虚点（z ≥ h − r 的洞和它连），
//   最后问 0 和 n+1 在不在同一块。
//
// ⚠⚠ 这道题最狠的一句在数据范围里：**坐标的绝对值不超过 10⁹** ——
//   于是 dx 可以到 2×10⁹，`dx² + dy² + dz²` 最大 **1.2 × 10¹⁹**，
//   而 `long long` 的上限只有 **9.22 × 10¹⁸** ⇒ ★★★ **连 long long 都不够**（本页第 ③ 步）。
//   ⇒ 这一版的办法是**边加边判**：每加一项就和 `(2r)²` 比一次，超了就直接否。
//     这样累加值永远不超过 `(2r)² + (2r)² = 8 × 10¹⁸ < 9.22 × 10¹⁸`，**一次都不会溢出**。
//     ⚠ 只判「每个分量 ≤ 2r」是**不够**的（那时三项和仍可到 1.2 × 10¹⁹）——
//     本页作者第一版就是那么写的。
#include <bits/stdc++.h>
using namespace std;

static const int N = 1005;
static int fa[N + 2];

static int find(int x) {
    int r = x;
    while (fa[r] != r) r = fa[r];
    while (fa[x] != r) { int nx = fa[x]; fa[x] = r; x = nx; }
    return r;
}
static void unite(int a, int b) { fa[find(a)] = find(b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    string out;
    while (T--) {
        long long n, h, r;
        cin >> n >> h >> r;
        vector<array<long long, 3>> p(n + 1);
        for (long long i = 1; i <= n; i++) cin >> p[i][0] >> p[i][1] >> p[i][2];
        for (long long i = 0; i <= n + 1; i++) fa[i] = (int)i;       // ★ 每组都要清
        long long d2 = 2 * r;
        for (long long i = 1; i <= n; i++) {
            if (p[i][2] <= r) unite(0, (int)i);                      // 和下表面相交 / 相切
            if (p[i][2] + r >= h) unite((int)(n + 1), (int)i);       // 和上表面
            for (long long j = i + 1; j <= n; j++) {
                long long dx = p[i][0] - p[j][0], dy = p[i][1] - p[j][1], dz = p[i][2] - p[j][2];
                /* ★ 边加边判：累加值永远 ≤ 2 × (2r)² = 8 × 10¹⁸，装得进 long long */
                long long lim = d2 * d2, s = dx * dx;
                if (s > lim) continue;
                s += dy * dy;
                if (s > lim) continue;
                s += dz * dz;
                if (s <= lim) unite((int)i, (int)j);
            }
        }
        out += (find(0) == find((int)(n + 1))) ? "Yes\n" : "No\n";
    }
    cout << out;
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★ 两个虚点：下表面 0 号、上表面 n+1 号

洞 i 和洞 j 相交/相切  ⇔  dist² ≤ (2r)²        ⇒ union(i, j)
洞 i 挨着下表面        ⇔  z ≤ r                ⇒ union(0, i)
洞 i 挨着上表面        ⇔  z + r ≥ h            ⇒ union(n+1, i)

最后问 find(0) == find(n+1)。 ★ 这道题练的正是题单说的那一步：看出「这是并查集」—— 它一个「合并 / 查询」的字眼都没有，是你自己把「能跑过去」翻译成了「同一个连通块」。 ★ 复杂度 O(T n²) = 2 × 10⁷ 对，本机 80 毫秒。

2★ 先把「不要开根号」这件事说完

比较 dist ≤ 2r 时不要真的开根号 —— 两边平方，比 dist² ≤ (2r)² 就行： sqrt 既慢又要操心浮点误差，而这里全是整数。 ★ 这是「能用整数就别碰浮点」在这道题上的直接应用。

3★★★ 而这道题真正的坑是：连 long long 都不够

p3958LL.cpp✗ 直接 dx*dx + dy*dy + dz*dz（官方样例照过）

// P3958 · 错法 ①：直接 `dx*dx + dy*dy + dz*dz`，用 long long
//
// ⚠⚠ 「开了 long long 就没事」是这道题上最贵的一个错觉：
//   坐标绝对值到 10⁹ ⇒ 每个分量差到 2×10⁹ ⇒ 每项 4×10¹⁸，
//   **三项加起来 1.2 × 10¹⁹ > 9.22 × 10¹⁸**（long long 的上限）。
//   绕回去之后变成负数 ⇒ `<= (2r)²` 成立 ⇒ **把两个隔得极远的空洞判成相交**。
// ★ 而顺手写的生成器坐标只有几十 ⇒ 这一档是**结构性的精确 0**（本页第 ③ 步）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 1005;
static int fa[N + 2];

static int find(int x) {
    int r = x;
    while (fa[r] != r) r = fa[r];
    while (fa[x] != r) { int nx = fa[x]; fa[x] = r; x = nx; }
    return r;
}
static void unite(int a, int b) { fa[find(a)] = find(b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    string out;
    while (T--) {
        long long n, h, r;
        cin >> n >> h >> r;
        vector<array<long long, 3>> p(n + 1);
        for (long long i = 1; i <= n; i++) cin >> p[i][0] >> p[i][1] >> p[i][2];
        for (long long i = 0; i <= n + 1; i++) fa[i] = (int)i;       // ★ 每组都要清
        long long d2 = 2 * r;
        for (long long i = 1; i <= n; i++) {
            if (p[i][2] <= r) unite(0, (int)i);                      // 和下表面相交 / 相切
            if (p[i][2] + r >= h) unite((int)(n + 1), (int)i);       // 和上表面
            for (long long j = i + 1; j <= n; j++) {
                long long dx = p[i][0] - p[j][0], dy = p[i][1] - p[j][1], dz = p[i][2] - p[j][2];
                if (dx * dx + dy * dy + dz * dz <= d2 * d2) unite((int)i, (int)j);   // ✗ 会溢出
            }
        }
        out += (find(0) == find((int)(n + 1))) ? "Yes\n" : "No\n";
    }
    cout << out;
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 「开了 long long 就没事」是这道题上最贵的一个错觉

把题面那两行乘一遍：


坐标绝对值	≤ 10⁹ ⇒ 每个分量差最大 2 × 10⁹
每一项 `dx²`	≤ 4 × 10¹⁸
三项加起来	★ 1.2 × 10¹⁹
`long long` 上限	9.22 × 10¹⁸
⇒ 前者是后者的	★★★ 130%

绕回去之后变成负数 ⇒ <= (2r)² 成立 ⇒ 把两个隔得极远的空洞判成相交。

300 轮	档 0	档 1 只有一组	档 2 大量相切	★★★ 档 3 坐标铺到 ±10⁹
真的有一对 `dx²+dy²+dz² ≥ 2⁶³`	★ 0	★ 0	★ 0	261
⇒ 「直接用 long long」被抓	★ 0	★ 0	★ 0	★ 261

★★ 触发条件 ≡ 抓获数，一个不差。 ⚠ 而前三档全是结构性的 0 —— 顺手写的生成器坐标只取 0~20， dx² 撑死几百，结构上够不着 2⁶³。 ⇒ 又一次「溢出的触发条件是一条数值线，生成器够不够是算术题」。

⚠⚠ 而本页作者第一版的「修法」也不够 —— 那也是量出来才知道的

第一版写的守卫是「先判每个分量：|dx| > 2r 就直接否」。看着挺稳 —— 可只要三个分量都恰好等于 2r = 2 × 10⁹，平方和仍然是 1.2 × 10¹⁹，照样溢出。

★ 真正够用的写法是边加边判：

long long lim = d2 * d2, s = dx * dx;
if (s > lim) continue;          // 此刻 s ≤ 4 × 10¹⁸
s += dy * dy;                   // ⇒ 累加值 ≤ 8 × 10¹⁸ < 9.22 × 10¹⁸ ✓
if (s > lim) continue;          // 此刻 s 又回到 ≤ 4 × 10¹⁸
s += dz * dz;                   // ⇒ 仍然 ≤ 8 × 10¹⁸ ✓
if (s <= lim) unite(i, j);

★★ 每加一项就和 (2r)² 比一次，累加值永远不超过 2 × (2r)² = 8 × 10¹⁸ —— 一次都不会溢出，而且不用 __int128。 ⇒ ★★ 这一条值得单独记：「加个守卫」和「守卫够不够」是两件事，后者要把最坏情况乘一遍才知道。

4⚠ 相切算不算：题面写了三遍「相切或是相交」

p3958Strict.cpp✗ 把相切排除在外（官方样例打出 No No No）

// P3958 · 错法 ②：把「相切」排除在外
//
// ⚠ 题面写得很明白：「如果两个空洞**相切或是相交**」都能过去；
//   和上下表面也是「相切或是相交」。⇒ 三处比较全是 `≤`、`>=`，不是严格不等号。
// ★ 官方样例第一组就是**三处相切**（(0,0,0) 切下表面、(0,0,4) 切上表面、两洞在 (0,0,2) 相切）
//   ⇒ 它一测就死。
#include <bits/stdc++.h>
using namespace std;

static const int N = 1005;
static int fa[N + 2];

static int find(int x) {
    int r = x;
    while (fa[r] != r) r = fa[r];
    while (fa[x] != r) { int nx = fa[x]; fa[x] = r; x = nx; }
    return r;
}
static void unite(int a, int b) { fa[find(a)] = find(b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    string out;
    while (T--) {
        long long n, h, r;
        cin >> n >> h >> r;
        vector<array<long long, 3>> p(n + 1);
        for (long long i = 1; i <= n; i++) cin >> p[i][0] >> p[i][1] >> p[i][2];
        for (long long i = 0; i <= n + 1; i++) fa[i] = (int)i;       // ★ 每组都要清
        long long d2 = 2 * r;
        for (long long i = 1; i <= n; i++) {
            if (p[i][2] < r) unite(0, (int)i);                       // ✗ 相切不算
            if (p[i][2] + r > h) unite((int)(n + 1), (int)i);        // ✗ 相切不算
            for (long long j = i + 1; j <= n; j++) {
                long long dx = p[i][0] - p[j][0], dy = p[i][1] - p[j][1], dz = p[i][2] - p[j][2];
                /* ★ 边加边判：累加值永远 ≤ 2 × (2r)² = 8 × 10¹⁸，装得进 long long */
                long long lim = d2 * d2, s = dx * dx;
                if (s > lim) continue;
                s += dy * dy;
                if (s > lim) continue;
                s += dz * dz;
                if (s < lim) unite((int)i, (int)j);                  // ✗ 相切不算
            }
        }
        out += (find(0) == find((int)(n + 1))) ? "Yes\n" : "No\n";
    }
    cout << out;
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

三处比较全是 ≤ / ≥，不是严格不等号。 ★ 官方样例第一组三处全是相切（洞切下表面、洞切上表面、两洞相切）⇒ 它一测就死。

300 轮	档 0	档 1	★★ 档 2 大量相切	档 3
输入里真的出现过相切	182	135	296	★ 0
⇒ 被抓	35	18	53	★ 0

⚠ 两层差 5 倍上下 —— 「出现过相切」还不够，那处相切还得真的影响连通性。 ★ 而档 3（坐标只取 ±10⁹、r = 1）里一次相切都没有 ⇒ 能证的 0。

5⚠ 多组数据没清空 —— 而它恒把 No 判成 Yes

p3958Clear.cpp✗ fa[] 只在开头初始化一次（官方样例打出 Yes Yes Yes）

// P3958 · 错法 ③：多组数据之间没有把并查集清干净
//
// ⚠ 题面第一行就是「每个输入文件包含**多组数据**」。
//   上一组的合并留在 fa[] 里，下一组照用同样的下标 0..n+1 ⇒ 直接污染。
// ★ 它**恒把 No 判成 Yes**（多出来的合并只会让 0 和 n+1 更容易连上）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 1005;
static int fa[N + 2];

static int find(int x) {
    int r = x;
    while (fa[r] != r) r = fa[r];
    while (fa[x] != r) { int nx = fa[x]; fa[x] = r; x = nx; }
    return r;
}
static void unite(int a, int b) { fa[find(a)] = find(b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    for (int i = 0; i <= N + 1; i++) fa[i] = i;                      // 只在开头初始化一次
    string out;
    while (T--) {
        long long n, h, r;
        cin >> n >> h >> r;
        vector<array<long long, 3>> p(n + 1);
        for (long long i = 1; i <= n; i++) cin >> p[i][0] >> p[i][1] >> p[i][2];
        // ✗ 忘了清空 —— 上一组的合并留在这儿了
        long long d2 = 2 * r;
        for (long long i = 1; i <= n; i++) {
            if (p[i][2] <= r) unite(0, (int)i);                      // 和下表面相交 / 相切
            if (p[i][2] + r >= h) unite((int)(n + 1), (int)i);       // 和上表面
            for (long long j = i + 1; j <= n; j++) {
                long long dx = p[i][0] - p[j][0], dy = p[i][1] - p[j][1], dz = p[i][2] - p[j][2];
                /* ★ 边加边判：累加值永远 ≤ 2 × (2r)² = 8 × 10¹⁸，装得进 long long */
                long long lim = d2 * d2, s = dx * dx;
                if (s > lim) continue;
                s += dy * dy;
                if (s > lim) continue;
                s += dz * dz;
                if (s <= lim) unite((int)i, (int)j);
            }
        }
        out += (find(0) == find((int)(n + 1))) ? "Yes\n" : "No\n";
    }
    cout << out;
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

300 轮	档 0	★ 档 1 只有一组	档 2	档 3
`T == 1` 的轮数	96	300	96	96
⇒ 「没清空」漏掉的轮数	⚠ 147	★ 300	178	102

★ 档 1 那一列 300 ≡ 300 是能证的（只有一组，没有上一组可以污染）； ⚠ 而别的档差得多 —— 上一组的合并不一定改变这一组的答案。 ★ 它恒把 No 判成 Yes（多出来的合并只会让 0 和 n+1 更容易连上） ⇒ 又一次「答案偏大还是偏小，不用跑就能判」。

6★ 对拍这一页

300 轮（`n` 随机 3~8）	档 0 顺手	★ 档 1 只有一组	★★ 档 2 大量相切	★★★ 档 3 坐标 ±10⁹
直接用 long long 相加	★ 0	★ 0	★ 0	261
相切不算	35	18	53	★ 0
多组没清空	153	★ 0	122	198

★ 官方样例挡住两个、放过一个 —— 而放过的那个只能靠算

错法	官方样例挡住了吗	为什么
相切不算	★ 挡住（打出 `No No No`）	第一组三处全是相切
多组没清空	★ 挡住（打出 `Yes Yes Yes`）	样例本身就有三组
⚠ 直接用 long long	⚠ 放过	样例坐标最大才 4，`dx²` 撑死十几

⇒ 前两个是结构问题，样例的结构恰好问得出来；最后一个是一条数值线（9.22 × 10¹⁸），样例和顺手写的生成器都够不着 —— 只能把题面那两行乘一遍。

7度量程序和生成器

p3958Count.cpp度量程序（本页所有数字都出自它）

p3958Gen.cpp（五个档位）数据生成器

8一页纸


★ 关键的一步	把「能跑过去」翻译成「同一个连通块」；上下表面各用一个虚点
★ 不要开根号	两边平方比 `dist² ≤ (2r)²`，全程整数
★★★ 连 long long 都不够	顶格平方和 1.2 × 10¹⁹，是 `long long` 上限的 130%（触发 ≡ 抓获，261 ≡ 261）
⚠⚠ 而第一版的守卫也不够	「每个分量 ≤ 2r」时三项和仍可到 1.2 × 10¹⁹ ⇒ 要边加边判（累加值 ≤ 8 × 10¹⁸）
⇒ 一条能带走的	「加个守卫」和「守卫够不够」是两件事 —— 后者要把最坏情况乘一遍
⚠ 相切	题面写了三遍「相切或是相交」⇒ 三处比较全是 `≤`；官方样例第一组三处全是相切
⚠ 多组	没清空恒把 No 判成 Yes；`T == 1` 那一档 300 ≡ 300 是能证的 0

洛谷 P3958 [NOIP 2017 提高组] 奶酪

0题目原文（本地存了一份）

输入

输出

1把「两球相交」当成一条边，这就是一道连通性题

2★ 先把「不要开根号」这件事说完

3★★★ 而这道题真正的坑是：连 long long 都不够

4⚠ 相切算不算：题面写了三遍「相切或是相交」

5⚠ 多组数据没清空 —— 而它恒把 No 判成 Yes

6★ 对拍这一页

7度量程序和生成器

8一页纸