CCF 甚至特殊构造了大样例

logicneko · 2026-11-01 15:08:50 · 生活·游记

我由于大样例从 200pts+eps 挂到 100pts+eps。

便完整分析一下大样例。

crystal

crystal：大样例有一定区分能力，但完全没有检验 64 位数值处理。

评价：CCF 正常发挥

subway

subway：所有大样例都是编号有序的链，且全部样例的线路最短路都可以用同一类链上前缀和表示。

样例中的结构如下：

样例	线路数 n	站数 m	\sum k_i	询问数 q	实际换乘图及特殊性
1	2	5	6	2	只有两条线路，一条换乘边，无法检验一般图最短路。
2	3	7	10	2	唯一含环的样例，但三条边权分别为 11,3,200，其中权值 200 的边完全不会改善任何线路间最短路。删除后仍是一条链。
3	15	136	150	200	每条线路恰好经过 10 个站，换乘图严格为 1-2-\cdots-15。
4	480	481	960	90000	每条线路恰好经过 2 个站，换乘图严格为 1-2-\cdots-480；站点网络本身也退化为链。
5	480	18721	19200	2000	每条线路恰好经过 40 个站，仍是编号顺序链，且所有 t_{i,j}=1，每条换乘边权均为 2。
6	480	479521	480000	90000	每条线路恰好经过 1000 个站，仍是同一条编号顺序链，且所有 t_{i,j}=1。站点数量大幅增加，但换乘结构没有变复杂。
7	480	479521	480000	90000	每条线路恰好经过 1000 个站，仍是编号顺序链。权值增大到接近 10^9，只能够检查大距离。

这意味着：

全部 5 个外部大样例的换乘图都是链，连一个分叉都没有。
全部 7 个样例中，每个站实际最多只有两条线路经过。 没有任何一个站检验三条及以上线路的换乘。
全部 7 个样例中，任意两条线路至多共享一个站。 多个换乘站之间取最小边权的逻辑没有得到检验。
唯一的环出现在样例 2，但多出来的边权为 200，而另一条路径仅为 11+3=14。它没有改变链上的最短路度量。

因此，只保留编号相邻线路之间的边，定义：

P_1=0,\qquad P_i=\sum_{j=1}^{i-1}e_{j,j+1},

然后直接令：

D_{i,j}=\lvert P_i-P_j\rvert,

就能通过全部 7 个样例。

这不是只根据图形作出的推测。以下方案均已逐项对照全部样例答案；其中，站点端点处理保持正确，仅替换线路间距离的计算方法：

对一般数据不正确的做法	样例 1	样例 2	样例 3～7
用最小生成树上的路径长度代替最短路	全过	全过	全过
只建一棵以线路 1 为根的最短路树，再按树上路径求任意两点距离	全过	全过	全过
Floyd 使用 `i-j-k` 循环顺序	全过	全过	全过
Floyd 使用 `i-k-j` 循环顺序	全过	全过	全过
Floyd 使用 `j-i-k` 循环顺序	全过	全过	全过
Floyd 使用 `j-k-i` 循环顺序	全过	全过	全过
只保留编号相邻线路，使用前缀和	全过	全过	全过
BFS 首次访问时确定父亲，累加边权，再按所得树求距离	全过	通过 1/2 个询问	全过
Floyd 只给尚不可达的点对赋值，已有距离不再取更小值	全过	通过 1/2 个询问	全过

另外，由于没有重复的线路间换乘边，建图时直接覆盖边权、不对多个换乘站取最小值，也不会在这些样例中暴露。

这些问题用很小的数据就能检出。例如，让三条线路形成边权为 2,2,3 的三角形：

MST 会把某一对线路的距离算成 4，而正确答案是 3。
一棵单源最短路树也不能保留所有点对之间的最短距离。
对链进行适当的线路编号置换，就可以破坏部分错误 Floyd 顺序在编号有序链上的侥幸正确性。

需要承认，样例 7 的大权值有实际作用：其中 89823 个答案超过了 2^{31}-1，最大答案为 497871086697，能够检查整数溢出和过小的无穷大。

评价：请输入文本

migrate

migrate：部分大样例很特殊。

这题包含多组测试，必须区分“一个样例文件”和“文件中的一组数据”。

样例	组数 t	总规模 N	最大单组 n	结构与检验能力
1	2	9	5	均为等差数列，d=2。所有双径对的最短路长度均为 2，因此只统计两步双径的错误做法能够通过。
2	2	11	6	第一组包含恰好三条最短路的岛屿对，能够检出把“恰好两条”写成“至少两条”；第二组包含不连通情形。但有效双径仍只有两步。
3	17	298	197	主数据包含最短路长度从 2 到 65 的双径对，另外加入多个局部构造、孤点、不连通和接近 \pm10^{18} 的坐标。能有效检查长距离计数逻辑，但规模只适合检查正确性。
4	12	2000000	699940	全部为等差数列，严格属于特殊性质 A。总规模达到上限，但不能检验一般坐标分布。只统计两步双径的方案能够通过整个文件。
5	14	1000000	399943	属于特殊性质 C，但包含密集点簇、大答案、不连通和不规则间距。不是简单的均匀排列，也不能全部用两步路径处理。
6	16	199999	174944	包含长链上分支传播的复杂计数；不过前 6 组较大数据中，每个点右侧最多只有 3 个直接可达点，图非常稀疏。没有覆盖接近 2\times10^6 规模的一般结构。

评价：强度尚可，但高强度数据主要集中在样例 3，后面的大范围样例很水

hub

hub：依旧缺乏强度，小样例特殊，大样例是特殊性质，假算法可以全部通过。

对任意预先指定的树的直径 P，总存在一个最优方案，使每个基地连通块都与 P 相交。

这里允许连通块向直径之外延伸，只要求它与指定直径存在公共顶点。即使如此，这个命题仍然不成立。

实测采用两次 BFS 选定直径，再强制每个基地连通块都与该直径相交，得到：

样例	数据组数	加入错误限制后得到的答案	与标准答案比较
1	2	1,2	全部一致
2	3	1,1,2	全部一致
3	5	17,9,6,6,9	全部一致
4	5	189,233,288,229,338	全部一致
5	1	12251	一致

不仅全部大样例没有检出这个错误，前两个小样例也没有检出。 上表对应固定选径方式的实际结果，不表示枚举检验过每份数据的所有直径。

这个命题只需要一棵 12 个点的树就能否定。

令 n=12,\ k=6，边集为：

E= \{(i,i+1):1\le i\le6\} \cup \{(3,8),(5,9),(4,10),(10,11),(11,12)\}.

也就是以 1,2,\ldots,7 为主链，在点 3、5 上分别挂一个叶子，再从点 4 接出长度为 3 的支链。

指定直径：

P=(1,2,3,4,5,6,7).

它的长度为 6，确实是这棵树的一条直径。

选择：

S=\{2,3,4,5,6,11\}.

其中 \{2,3,4,5,6\} 构成一个连通块，\{11\} 构成另一个连通块。所有未选顶点都与某个选中顶点相邻，因此通勤半径为 1；又因为 k<n，不可能达到半径 0，所以最优答案就是 1。

但第二个连通块 \{11\} 完全位于指定直径之外。

如果强制每个基地连通块都与 P 相交，那么任何半径为 1 的方案都必须满足：

为覆盖点 12，必须选择点 11 或 12；该连通块要接到直径上，点 11,10,4 就都必须选。
为覆盖叶子 8，必须选点 3，或者选点 8 后通过点 3 接到直径上。因此点 3 必须选。
同理，点 5 必须选。
为覆盖点 1，点 1、2 中至少选一个。
为覆盖点 7，点 6、7 中至少选一个。

因此，至少需要选择：

3+1+1+1+1=7

个点，与 k=6 矛盾。

原问题最优值为 1，加入这个错误限制后最优值变成 2。

评价：CCF 超常发挥

综述一下，在没有 selfeval 的 CSP 和 NOIp 赛场上，大样例是选手检验自己算法正确性的直接方案。提供高质量的大样例是组委会的责任，有助于比赛公平性。

然而，本场 CSP-S 的大样例相当糟糕。尤其是 subway 的全部链的，CCF 甚至特意构造了这 7 个全部是链的数据。

如此样例，令人汗颜。

额外参考

Reference1

Reference2

注：使用了 GPT-6 Astra 辅助分析了样例，润色了文笔。