我昨天正在解决一个Codeforces问题。问题的URL是这个
我将在下面简短地解释这个问题。
给定一个二进制字符串，将其划分为最小数量的子序列以使字符串中的每个字符恰好属于一个子序列，并且每个子序列看起来像"；010101"或"；101010…"；(即子序列不应包含两个相邻的零或一个(。
现在，对于这个问题，我昨天在比赛中提交了一个解决方案。这就是解决方案。它被临时接受，并且在最终测试用例中获得了"超过时间限制"的状态。
因此，今天，我再次提交了另一个解决方案，并通过了所有案例。
在第一个解决方案中，我使用了HashSet，在第二个解决方案中将使用LinkedHashSet。我想知道，为什么HashSet没有清除所有的病例？这是否意味着每当我需要Set实现时，我都应该使用LinkedHashSet？我看了这篇文章，发现HashSet的性能比LinkedHashSet好。但为什么我的代码在这里不起作用？
这个问题可能会在Codeforces上得到更多的回复，但我无论如何都会在这里回答。
比赛结束后，Codeforces允许其他用户"；破解"；通过编写自定义输入以在其他用户的程序上运行的解决方案。如果辩护用户的程序在自定义输入上运行缓慢，则他们提交代码的状态将从"0"变为"0"；接受"；至"；超过时间限制"；。
具体地说，您的代码从"；接受"；至"；超过时间限制"；是有人创造了一个"；反散列测试"；(哈希函数会导致许多冲突的测试(程序运行速度比平时慢。如果你对如何生成这样的测试感兴趣，你可以在Codeforces上找到几篇文章，比如下面这篇：https://codeforces.com/blog/entry/60442.
正如@Photon所链接的，Codeforces上有一篇文章解释了为什么你应该避免使用Java.HashSet和Java.HashMap：https://codeforces.com/blog/entry/4876，这主要是由于反哈希测试。在某些情况下，从平衡BST添加额外的log(n)因子可能不会那么糟糕(通过使用TreeSet或TreeMap(。在许多情况下，额外的log(n)因子不会使代码超时，而且它可以保护您免受反哈希测试的影响。
如何确定您的算法是否足够快以添加log(n)因子？我想这需要一些经验，但大多数人建议进行某种计算。大多数在线判断(包括Codeforces(显示程序在特定问题上运行的时间(通常在1到4秒之间(，在执行计算时，您可以使用每秒10^9恒定时间运算作为经验法则。