紊莫
2023-01-05 14:40:34
鉴于最近洛谷的公开赛出现的重题引起的纠纷，我打算整理一下此类问题的危害和做法。
也许有时候无意的重题不会被处罚，但我想也应该尽量避免来换取选手的更好体验。
原题大致可分为完全一致、几乎一致和做法一致三种。
- 完全一致：使用一题的 AC 代码可以 AC 另一题。
- 几乎一致：由一题的 AC 代码改动至另一题的 AC 代码可以由一个不会该题的人完成。
- 做法一致：核心思路、做法一致，但代码实现上、不那么关键的细节上有差异。
（from OIwiki）
重了广为人知的题的后果：
xuanxuan001的练习赛Round1
所以本文主要说一些不常见的题如何高效查重。
说实话，很难通过复制粘贴题面来得到结果，尤其是全文比对。
因为没有搬题人傻到会复制原题。
【例题 1】
通过这次可以知道复制题面的下场。
常见做法是人工提取简化题意或者简化思路后进行搜索。
更常见的做法是提炼出本题的关键算法。
【例题 2】
在情况说明中 @FGgirl 提到：
线段树 拓扑排序 就这七个字，不要多。
据此在 bing（国际版） 和 google 上均可找到原题，而且页码非常前面。
对于出题人的题解，可以截取关键字进行搜索，因为一道题的题面不可能相同，算法又太宽泛，但常见解法往往不会很多。
当然，此做法的前提是原题传播较广泛且有较多人写题解。
经过我简单的统计，发现历次洛谷比赛的重题往往来自各大国外题库（Codeforces，Atcoder，······）
原因可能在于，这两个网站都是英文题面（或其他语种），经过出题人翻译后，很难通过中文查询。
对此，你可以尝试对上述方法中的关键字改为英文进行尝试。
你也可以大概估算题目的难度，到各大题库，确定筛选范围和算法，一般会有 200 题左右，一一验证基本不会再有重题。
做到这步绝大多数重题已经被查出了。
需要高水平选手。
一来可以帮助出题，二来高水平选手往往阅历更广，容易分辨一道题目是不是套路，看过的题更多，可以很大程度避免恶意搬题。
近期已经查收到多起出题组团队被篡改信息甚至大批盗题的信息。在这里提醒各个出题组不仅应当考察加团用户的题目质量或水平，也当对其心理年龄或者账号安全性等进行考察，以避免此类事件的发生。此外也不建议用户进入一些来路不明的团队，避免自己精心筹备的试题被盗用。
（from chen_zhe 的讨论贴）
这种盗用的题往往也很难被查出来。
【例题 3】
像这种一些活动中的题目或者某地市级的比赛，往往很少有题库收录，也几乎没有题解。这时如果团队中人来自五湖四海，这种问题就极难以被提前发现。
例如校内 OJ 题，如果团队中大多数互相熟悉，就不会出现 JEOI R1 T3 的事件。
总之，对于传播不广的题目，查重便造成了很大难度，此时应该借助人力，尽可能地减少重题。
关于查重这个问题，
作者只是一时间心血来潮，若有补充和勘误，请告诉我。
致谢：所有人！特别是提到的。