灯下随笔(五)——一个历史悠久的错误解法给我们的启示

我思考了很久,试图寻找一本通在 牛的旅行 这道题目上给出错解的原因。这个寻找的过程也给了我一些启发,在此与各位分享。

如果在直径的构成上只考虑 我的题解 中的情况 3,会在第 7 个点上挂掉。

然后作者就在这个做法上打了个补丁:连边后新牧场的直径可能还没有原来两个牧场的直径大(这个理由是我看一些人写的题解里说明的,原文倒是没提及这样做法的意义),所以还要取原来牧场直径的最大值,在二者中取较大者作为答案。

现在留给各位一些时间认真思考,想想上面的思考过程究竟有什么漏洞。思考得差不多后,再看看分割线下面的部分。


这里是我归纳出的漏洞:

  1. 如果 3 情况求出的“直径”还没原来连通块的直径大的话,那这条路径还满足直径的定义吗?前面对新连通块直径的定义,是否存在一些问题?
  2. 有不少同学提到了“直径可能会变短”。问题是如果仅仅是在一个连通块里加非负边,显然直径是不存在变短的可能的。这样的解释应该很快就能想到其不合理之处。
  3. 打的补丁本身:直接在原来牧场直径的最大值与新牧场可能直径的最小值这二者中取较大值,漏洞也很明显。这两者看上去并不具有可比性,因为原来直径最大值的牧场,并不一定会是新牧场的组成部分。而题目要求的是:所有合法连接方案中,新牧场 直径的最小值。

在有这么多漏洞的情况下,如果做这道题的同学能够多一些独立,深入的思考,应该会很快发现书中给出的这种解法的漏洞所在。但很不幸,这样的同学并不多。原来的 25 篇题解中,仅有四篇题解给出了严谨的正确做法。我又试着翻了提交记录,发现 AC 的提交里,鲜少有真正正确的代码。

(注:@Imakf 的题解思路虽然对了,但是还是出现了 新的大牧场的直径不一定比原来的两个牧场大 这样稍加思考就会发现不对劲的话)

原来的题目翻译确实存在一些表述不清晰之处,这可能是引发了一些人疑惑,让他们犯错的一个原因。一本通的编者,或许也是在看了不完美的翻译版题目后,在思考过程中出现了一些偏差。而我在重新翻阅那些被 hack 的题解时,发现很多题解只是机械性地搬运一本通的做法,没有任何自己思考的成分,于是他们沿着同样的路,踏入了同样的坑中,又将同样错误的观念传给了更多的人。

有些题解在尝试思考,他们似乎摸到了一些真相,但他们的思考还不够深入,还不足以跳出前人栽进去的坑。有些同学想到了 新的大牧场的直径不一定比原来的两个牧场大,于是打补丁的方法被他们接受。到此为止,他们没有再更进一步。

人并非完美的动物,犯错是经常的事情。但是一个最初偶然产生的错误,在测试数据未能发现其漏洞的情况下,却能让非常多的人重蹈覆辙,就不太对劲了。

洛谷的题解区有一行大字,写着“以下题解仅供学习参考使用”。这里的学习与参考,只是止步于被动地接受题解的思路,然后沿着题解铺下的路再走一遍吗?包括我在内的很多同学,在完成这道题目时,思路上都受到了错误题解的影响,写的代码并不能通过新加的 hack 数据。这样的学习,只是不断地重复着错误罢了,真正的知识,却并没有获得多少。

如果我们在做题时,写题解时,多一分独立思考,少一分人云亦云,这样的错误,大概率就可以避免。而在深入的批判性思考中,我们也能及时发现并纠正前人犯下的错误,并在思考中获得新的知识,推动着学术圈不断完成自我更新。这样的学术生态,对圈内的每一个人,以及整个学术圈的健康发展,都是十分有利的。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据