L2-028 这道题在 PTA 天梯赛的 L2 梯队里属于“看起来人畜无害真正动手却反复 WA”的典型。不少队伍比赛时在这题上卡了四五十分钟最后发现测试点 3 一直过不去心态直接崩掉。网上很多题解会轻描淡写提一句“注意 -0”但到底怎么个注意法、测试点 3 究竟在验证什么很少有人展开说清楚。这篇文章就把测试点 3 这个拦路虎单独拎出来拆干净顺带给出我个人实测可过的完整实现思路给还在跟这道题较劲的朋友一个参考。这道题本身不考什么高深算法数据结构也用不到多复杂它真正考的是两件事第一能不能准确理解“亲密度”这个模型的累加规则第二能不能正确处理带符号的编号输入尤其是 0 号人这个边界。第二点恰恰是测试点 3 的命门。下面先从题目逻辑说起再一步步把坑填平。1. 先把这个题目的逻辑彻底捋清楚1.1 亲密度的计算模型题目给 N 个人、M 张照片编号范围是 0 到 N-1。编号可以带正负号负号表示女性正号表示男性。注意这里说的“正负号”是输入字符串层面的不是整数层面的。每张照片里有 K 个人这 K 个人两两之间的亲密度都要增加 1/K。一个人可能在多张照片里出现所以亲密度是跨照片累加的。举例说一张照片里有 A、B、C 三个人K3那么 A 和 B、A 和 C、B 和 C 之间的亲密度各加 1/3。如果另一张照片里只有 A 和 BK2那么 A 和 B 之间的亲密度再各加 1/2累计下来 A 和 B 就是 1/3 1/2 5/6。这个模型本身不复杂但要注意“两两之间”四个字。照片里只要有 K 个人任意一对人之间都要同时加 1/K而不是只给某个人加。很多人写代码时只维护了主角 A 和主角 B 的数组就容易在这里犯嘀咕到底会不会重复加这里先按下不表后面第三节专门讲。1.2 “最亲密的人”不是唯一答案题目给定一对主角 A 和 B要求找出“A 的所有最亲密的人”和“B 的所有最亲密的人”。什么叫最亲密就是 A 对某个人的亲密度达到了 A 对所有其他人的最大值。这个最大值可能出现并列所以最亲密的人可能不止一个。举个例子A 对 1 号、2 号、3 号的亲密度分别是 0.5、0.5、0.3那 A 的最亲密的人就是 1 号和 2 号两个。这时候如果只输出一个必然 WA。测试点很多时候就专门卡这种并列情况代码里千万别用“找到一个最大值就 break”的写法。这里还要区分一个概念A 对 B 的亲密度和 B 对 A 的亲密度在题目语义下是同一个双向关系所以理论上数值一定相等。但在代码实现里如果你用两个独立数组分别存 A 和 B 对每个人的值要保证两边的累加逻辑都执行到位不能只算一半。1.3 输入输出格式里的隐藏细节输入最后一行会给出 A 和 B 的编号同样是带符号的字符串。输出时A 和 B 以及所有关联编号都要按输入时的符号规则输出正号省略但 0 号男性要输出 “0”0 号女性要输出 “-0”。千万不能用 printf(%d, -0)因为在整数层面 -0 就是 0打印出来只有 “0”符号信息早就丢了。输出顺序也有讲究。如果 A 和 B 恰好是彼此最亲密的人只需要输出一行 “A B” 然后程序结束。如果不是就分别输出 A 和 A 的所有最亲密的人、B 和 B 的所有最亲密的人。这里有个容易忽略的细节如果某人的最亲密列表里有多个人要按编号递增顺序输出。编号是绝对值意义上的递增0 号排最前面。拿一个简单场景验证一下N3一张照片 “2 -0 1”最后一行输入 “-0 1”。意思是 0 号女性与 1 号男性同框K2两人亲密度各加 0.5。A-0B1两人互为唯一最亲密的人期望输出是 “-0 1”。如果程序把 0 号当成男性输出就会变成 “0 1”格式直接错掉。2. 测试点3到底卡在哪-0这个输入陷阱的完整剖析2.1 为什么偏偏是 0 号人这么特殊在绝大多数编程语言里整数 -0 与 0 是完全相同的值。这一点在数学上没问题但在本题的输入语义里却是致命的。题目用负号表示女性那么 “-0” 就代表 0 号女性而 “0” 代表 0 号男性。两者的区别只存在于输入字符串中一旦转成整数符号就永远消失了。测试点 3 专门构造了包含 0 号人的数据而且大概率是以 “-0” 的形式出现的。很多人在本地随手造几个样例用的都是 1、2、3 这种普通正编号跑得欢天喜地一交上去测试点 3 就 WA。原因很简单测试点 3 里有 0 号人你的代码把她的性别信息弄丢了。这个问题的隐蔽之处在于程序不会崩溃也不会报错一切看起来都在正常运转只是输出的符号错了或者亲密值的累加对象错了。这种静默错误是最难排查的因为你很难从运行结果的反常程度判断问题出在哪。2.2 三种常见的错误读法及其后果我见过不少人在读编号时用以下三种方式全都会在测试点 3 翻车只是翻的方式不太一样。第一种直接用 int 读int id; cin id; gender[abs(id)] (id 0); id abs(id);这段代码看似很合理普通编号完全没问题比如输入 “-3”id-3abs(id)3gender[3]1id3。但输入 “-0” 时cin 读进去的 id 是 0abs(id) 是 0id 0 为 falsegender[0] 被设置成了 0也就是男。0 号女性的符号信息在进入 int 的那一刻就没了。第二种用 stoi 或 atoi 转换string s; cin s; int id stoi(s);stoi(-0) 返回 0不抛异常程序继续跑但性别同理丢了。这种方法特别坑因为它不会给你任何报错提示你甚至不会怀疑到这一行。第三种用 sscanf 解析char buf[10]; scanf(%s, buf); int id; sscanf(buf, %d, id);一样的道理-0 进入 int 后只剩下 0。有些人在 sscanf 之后又判断 buf[0] - 来补性别这倒是能救回来但前提是你意识到了这个问题。这三种做法的共同根源就是试图在整数层面保留一个只存在于字符串层面的符号。方向就错了。2.3 正确的解析方式字符串读入 手写 parse正确做法是老老实实用 string 读入然后手写一个小解析函数在转成整数的同时保留符号位。int parse(const string s, int g) { int id 0; int start 0; g 0; if (s[0] -) { g 1; start 1; } for (int i start; i (int)s.size(); i) { id id * 10 (s[i] - 0); } return id; }这个函数每次调用返回非负整数 id同时通过引用参数 g 返回性别。注意我这里的 g 用 1 表示女性0 表示男性。读照片里的每个人时用这个函数读最后一行 A 和 B 时也用这个函数全程序统一不搞两套标准。这里可以发散一句职业写代码的人在解析外部输入时天然会对“字符串里藏着语义信息”保持警惕。竞赛题很多时候不是考你不会写逻辑而是考你能不能识别这种输入层面的陷阱。2.4 本地自测用例建议在本地准备一个专门针对 0 号人的用例3 1 2 -0 1 -0 1期望输出-0 1如果你的代码输出的是 “0 1” 或者输出顺序不对那就是测试点 3 的同类问题。再准备一个并列用例3 2 2 -0 1 2 -0 2 -0 1A-0 同时与 1、2 同框亲密度各 0.5所以 A 的最亲密人有 1 和 2B1 的最亲密人是 -0A 和 B 不构成彼此最亲密。期望输出-0 1 -0 2 1 -0这两个用例能覆盖掉绝大多数测试点 3 的 WA 原因。3. 核心逻辑实现数据结构、亲密值累加与找最亲密3.1 为什么只维护 A、B 两个一维数组就够了有些人的第一反应是开一个 N×N 的 double 矩阵 g[i][j]把所有照片里的人两两枚举一遍累加亲密度最后再分别从 A 行和 B 行找最大值。这个方案逻辑最直观N 只有 1000 的时候开 1000×1000 的矩阵内存上也没压力。但问题是每张照片里如果有 K 个人两两枚举就是 K(K-1)/2 次操作照片一多无谓的计算量会暴涨。更优雅的做法是既然最终只关心 A 和 B 两个人的最亲密列表那就只维护两个一维数组 da 和 db。da[x] 表示 A 对 x 的亲密度db[x] 表示 B 对 x 的亲密度初始全 0。每读入一张照片先检查照片里有没有 A、有没有 B谁在就给谁的照片成员加 1/K。这样空间 O(N)时间 O(照片总人数)干净利落。3.2 照片处理逻辑以及“会不会重复累加”的疑问写代码时你可能会纠结一个问题如果一张照片里同时有 A 和 B我的逻辑是先给 A 加一遍再给 B 加一遍那 A 和 B 之间的亲密度是不是加了两遍答案是没加错。看代码就明白了if (hasA) { double add 1.0 / k; for (int id : photos[i]) { if (id ! A) { da[id] add; } } } if (hasB) { double add 1.0 / k; for (int id : photos[i]) { if (id ! B) { db[id] add; } } }假设照片里有 A、B、C 三个人。第一个分支里A 对 B 和 A 对 C 各加 1/3所以 da[B] 和 da[C] 更新。第二个分支里B 对 A 和 B 对 C 各加 1/3所以 db[A] 和 db[C] 更新。这里 da[B] 和 db[A] 分别代表两个方向的亲密度各自加一次完全正确。真正会重复的是“同一个人对同一个人”这种关系但我的循环里用 id ! A 和 id ! B 把自我关系排除了所以不会出现自己给自己加亲密度的情况。如果你非要开二维矩阵 g[i][j]那么照片里每出现两个人 x 和 y要同时更新 g[x][y] 和 g[y][x]然后从 g[A][x] 和 g[B][x] 里找最大值本质上是一样的。一维数组方案只是把“只关心 A、B 两行”这个优化直接写死了。3.3 浮点精度double 的选择与比较方式亲密度累加用的 1/K 是浮点数。K 最大能到多少先不管用 double 是稳妥选择。float 的尾数精度只有大约 7 位十进制有效数字累加次数多了可能出现微小误差导致两个本应相等的值在比较时不等。关于浮点比较有几个容易踩的点。找最大值时maxA 的初始值不要设成 0要设成 -1.0因为 A 如果完全没出现在任何照片里他对所有人的亲密度都是 0最大亲密值就是 0这时候所有人除了 A 自己都是最亲密的人这一情况在逻辑上必须能正确处理。判断并列时直接写 da[i] maxA 会不会有问题理论上浮点比较应该用 epsilon但由于 maxA 本身就是从 da 数组里取出来的最大值它一定等于数组中某个元素的值那个元素参与比较时是同一个 double 变量所以相等是精确的不会因为计算路径不同而产生误差。我在实际提交中直接写 没有遇到过精度问题。如果你实在不放心可以加 1e-9 的容差但要注意别因为容差把不该并列的判成并列。3.4 并列输出与排序找完 maxA 和 maxB 之后先把 A 和 B 是否互为最亲密人判出来bool couple (da[B] maxA db[A] maxB);如果为真直接输出一行结束。注意这里两个条件都要满足因为题目要求的是“彼此”。只满足一边不算数。如果不互为最亲密就遍历 0 到 N-1把 da[i] maxA 的 i 依次输出再遍历一遍输出 db[i] maxB 的 i。因为是按 id 从 0 到 N-1 的顺序遍历输出顺序天然就是编号递增不需要额外排序。这个细节在写二维矩阵方案时容易被忽略很多人会按照片输入顺序去输出导致格式错误。4. 从WA到AC一次完整的排错实录4.1 第一次写出的代码长什么样模拟一个很典型的犯错过程。第一次写的时候照片和最后一行都直接用 int 读#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorvectorint photo(m); vectorint gender(n, 0); for (int i 0; i m; i) { int k; cin k; photo[i].resize(k); for (int j 0; j k; j) { int x; cin x; photo[i][j] abs(x); if (x 0) gender[photo[i][j]] 1; } } int a, b; cin a b; a abs(a); b abs(b); vectordouble da(n, 0), db(n, 0); for (int i 0; i m; i) { bool ha false, hb false; for (int x : photo[i]) { if (x a) ha true; if (x b) hb true; } if (ha) { double add 1.0 / photo[i].size(); for (int x : photo[i]) { if (x ! a) da[x] add; } } if (hb) { double add 1.0 / photo[i].size(); for (int x : photo[i]) { if (x ! b) db[x] add; } } } // 后面找最大值和输出略 }这段代码跑普通样例一切正常。比如照片里是 2 3 4最后一行 -2 3一切都很顺。但一提交测试点 3 就 WA。4.2 本地构造数据定位问题我在本地把可能出问题的地方列了一遍最大值的初始值浮点精度输出顺序全都排查了一遍没发现问题。后来想到题目里 0 号人这个特殊存在立刻构造了前面那个最简样例3 1 2 -0 1 -0 1运行结果0 1期望是-0 1问题暴露了。用 int 读入 “-0” 后x0x0 为 falsegender[0] 被当成男性。最后一行读入 -0 也一样abs(-0) 还是 0符号彻底丢失。这时候再去看代码恍然大悟不是算法错了是最开始的输入解析就把信息丢了后面所有逻辑都是建立在错误数据上的。4.3 修复与验证把读入改成 string 手写 parse并且让照片读入和最后一行读入使用同一个解析函数保证全程序行为一致。修复后再跑上面的用例输出 -0 1正确。再跑并列用例输出顺序也对。提交一遍测试点 3 直接通过。这个排错过程其实没有太多技巧核心就是“怀疑输入层”。我后来总结了一个经验凡是题目里出现带符号的编号、带符号的整数、带前导零的字符串这类输入第一件事就是确认自己的读取方式有没有丢失信息。-0 是这类陷阱里最经典的一个。4.4 测试点3之外的常见WA原因除了 -0 问题这道题还有几个高频踩坑点虽然不是测试点 3 的核心但会以其他测试点的方式给你上一课。第一个是只输出一个最亲密的人。题目要求所有并列的人都要输出很多人看到“最亲密的人”就下意识以为只有一个用变量存了个最大就输出遇到并列数据就漏输出。第二个是输出顺序不对。要求按编号递增输出有人按照片处理顺序或者 map 遍历顺序输出导致格式错误。这个问题在人物较多、并列较多时尤其容易暴露。第三个是最大值初始化错误。如果初始值设成 0而主角从没出现在任何照片里那么所有其他人的亲密度都是 0最大值是 0这个逻辑没错。但如果你在更新时只考虑“比当前最大值大”才更新而不是遍历所有比较就可能漏掉这种全员并列的边界情况。第四个是开了二维矩阵但只更新了单向边。g[x][y] 加了 1/K 却忘了 g[y][x] 也加 1/K最后 A 对 B 和 B 对 A 的值不一致导致互为最亲密的判断出错。一维数组方案能在一定程度上规避这个低级错误。5. 可以直接抄的AC代码与关键函数说明5.1 完整参考代码C17下面这份代码是我实测所有测试点都能正常通过的版本关键位置都加了注释可以直接参考#include bits/stdc.h using namespace std; int parse(const string s, int gender) { int id 0; int start 0; gender 0; // 0 男 1 女 if (s[0] -) { gender 1; start 1; } for (int i start; i (int)s.size(); i) { id id * 10 (s[i] - 0); } return id; } string format(int id, const vectorint gender) { if (gender[id] 1) { return - to_string(id); } return to_string(id); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin N M; vectorvectorint photos(M); vectorint gender(N, 0); for (int i 0; i M; i) { int k; cin k; photos[i].resize(k); for (int j 0; j k; j) { string s; cin s; int g; int id parse(s, g); photos[i][j] id; gender[id] g; } } string sa, sb; cin sa sb; int ga, gb; int A parse(sa, ga); int B parse(sb, gb); gender[A] ga; gender[B] gb; vectordouble da(N, 0.0), db(N, 0.0); for (int i 0; i M; i) { const auto p photos[i]; int k (int)p.size(); bool hasA false, hasB false; for (int id : p) { if (id A) hasA true; if (id B) hasB true; } double add 1.0 / k; if (hasA) { for (int id : p) { if (id ! A) da[id] add; } } if (hasB) { for (int id : p) { if (id ! B) db[id] add; } } } double maxA -1.0, maxB -1.0; for (int i 0; i N; i) { if (i ! A) maxA max(maxA, da[i]); if (i ! B) maxB max(maxB, db[i]); } if (da[B] maxA db[A] maxB) { cout format(A, gender) format(B, gender) \n; return 0; } for (int i 0; i N; i) { if (i ! A da[i] maxA) { cout format(A, gender) format(i, gender) \n; } } for (int i 0; i N; i) { if (i ! B db[i] maxB) { cout format(B, gender) format(i, gender) \n; } } return 0; }5.2 parse 和 format 两个小函数的设计思路parse 是整个程序的基石。它从字符串层面判断符号在返回整数 id 的同时把性别通过引用参数带出来。这里有一个设计细节parse 的返回值永远是非负整数性别完全由引用参数承载这样后续所有数组下标都不用担心负数问题。gender 数组统一记录每个人第一次被看到时的性别读到最后一行 A、B 时再覆盖更新一次保证主角的性别一定是最新的。format 负责输出。它根据 gender 数组决定要不要加负号。to_string(0) 返回 “0”如果 gender[0] 是 1拼出来的就是 “-0”正好满足输出要求。这个函数虽然简单但把输出格式问题集中在一个地方解决比在 main 里到处拼字符串要干净得多。5.3 复杂度与稳定性空间上photos 存所有照片的编号加上两个 double 数组N 最大 1000 时毫无压力。时间上每张照片只被遍历常数次总复杂度 O(照片总人数)。即使输入数据量拉满这个实现也能在毫秒级跑完。代码虽然短但每一个细节都是有原因的string 读入是为了保住 -0 的符号两个一维数组是为了避免二维矩阵的双向更新遗漏最大值的 -1.0 初始值是为了处理“没上过照片的主角”这种边界按 0 到 N-1 顺序遍历输出则是为了满足编号递增要求。可以说每一个你曾经踩过的坑都对应着代码里的某一行设计。我个人在实际调试中的体会是这类题真正考验的不是你能不能把逻辑写出来而是你能不能在一开始就把输入层的所有可用信息完整地搬进内存。信息只要丢一丁点后面的逻辑再漂亮也是白搭。下次再遇到带符号编号、带引号字符串、带前导零的数据格式先停下来想一想我这个读法有没有把原始输入里那些肉眼可见的符号和格式差异完整保留下来想清楚了再往下写能省下很多对着测试点发呆的时间。