- dxd 的博客
某些有问题的题的说明
- 2024-1-13 21:05:05 @
这道题目有什么问题?
- 简而言之,从今天的视角来看,本题是一定程度上的“错题”。
- 因为目前并没有一个做法,对于满足本题数据范围的任意数据,都能够既保证在本题的时限下求出答案,又保证求出的答案是正确的(或者对于本身含有随机性的做法,只有极小概率无法求出答案)。
为什么会有“错题”?
一般有以下两种情况。
- 这道题是搜索题。题目的标准解法就是搜索+剪枝、启发式搜索等做法,但是这类解法往往拥有指数级的时间复杂度,或者不一定能正确地求出答案。在题目的数据范围下不能保证一定能求出正确答案。年代较久远的题目中较为常见。不过这一类题目仍可以用作搜索练习题。
- 这道题确实是错题。由于出题人的一些失误,出题人为本题提供的做法是错的,本题的数据可能也是错误的,但是由于历史原因,这道题目被保留了。
为什么我/其他人还能 AC 这道题?
- 如果你的程序能够 AC 该题目,这是因为本题的测试数据强度较弱,使得你的程序能够通过它们。
- 我们鼓励自行尝试构造一些较强的数据,或者阅读本题的讨论区寻找一些其他用户提供的 hack 数据,使得你的程序在这些数据下输出错误的答案或运行时间超限。
- 请注意 AC 的评测结果不能保证你的程序/算法是完全正确的。这一点也适用于其他正确的题目,所有题目都可能有测试数据强度偏弱的问题。如果认为某篇题解有问题或者某道题目本身有问题,我们鼓励用户自行思考,找出问题,并在讨论区反馈。