CodeForces 问题中的歧义 - HashSet 与 LinkedHashSet 的用法
Ambiguity in a CodeForces Problem - usage of HashSet Vs LinkedHashSet
我昨天在解决一个 Codeforces 问题。问题的URL是this
我将在下面简单地解释一下这个问题。
Given a binary string, divide it into a minimum number of subsequences
in such a way that each character of the string belongs to exactly one
subsequence and each subsequence looks like "010101 ..." or "101010
..." (i.e. the subsequence should not contain two adjacent zeros or
ones).
现在，对于这个问题，我在昨天的比赛中提交了一个解决方案。这就是solution。它暂时被接受，并在最终测试用例中获得 超出时间限制 状态。
所以今天我又提交了一个solution，这样就全部通过了
在第一个解决方案中，我使用了 HashSet，在第二个解决方案中，我使用了 LinkedHashSet。我想知道，为什么HashSet没有清除所有案件？这是否意味着只要我需要 Set 实现，我就应该使用 LinkedHashSet？我看了 this 篇文章，发现 HashSet 比 LinkedHashSet 表现更好。但为什么我的代码在这里不起作用？
这个问题可能会在 Codeforces 上得到更多回复，但我还是会在这里回答。
比赛结束后，Codeforces 允许其他用户通过将自定义输入写入其他用户程序的 运行 来“破解”解决方案。如果防御用户的程序 运行 在自定义输入上运行缓慢，他们的代码提交状态将从“已接受”更改为“超过时间限制”。
具体来说，您的代码从“已接受”更改为“超出时间限制”的原因是有人创建了“anti-hash 测试”（您的哈希函数在该测试上会导致许多冲突）你的程序 运行 比平时慢。如果您对如何生成此类测试感兴趣，可以在 Codeforces 上找到几个 post，例如：https://codeforces.com/blog/entry/60442.
正如@Photon 所链接的那样，Codeforces 上有一个 post 解释了为什么您应该避免使用 Java.HashSet 和 Java.HashMap：https://codeforces.com/blog/entry/4876，这主要是由于 anti-hash 测试。在某些情况下，从平衡的 BST 添加额外的 log(n) 因子可能不会那么糟糕（通过使用 TreeSet 或 TreeMap）。在许多情况下，额外的 log(n) 因素不会使您的代码超时，并且它可以保护您免受 anti-hash 测试。
您如何确定您的算法是否足够快以添加 log(n) 因子？我想这需要一些经验，但大多数人建议执行某种计算。大多数在线评委（包括 Codeforces）都会显示您的程序在特定问题上允许 运行 的时间（通常在一到四秒之间），您可以使用 10^9 constant-time 操作每秒作为执行计算时的经验法则。
我昨天在解决一个 Codeforces 问题。问题的URL是this
我将在下面简单地解释一下这个问题。
Given a binary string, divide it into a minimum number of subsequences in such a way that each character of the string belongs to exactly one subsequence and each subsequence looks like "010101 ..." or "101010 ..." (i.e. the subsequence should not contain two adjacent zeros or ones).
现在，对于这个问题，我在昨天的比赛中提交了一个解决方案。这就是solution。它暂时被接受，并在最终测试用例中获得 超出时间限制 状态。
所以今天我又提交了一个solution，这样就全部通过了
在第一个解决方案中，我使用了 HashSet，在第二个解决方案中，我使用了 LinkedHashSet。我想知道，为什么HashSet没有清除所有案件？这是否意味着只要我需要 Set 实现，我就应该使用 LinkedHashSet？我看了 this 篇文章，发现 HashSet 比 LinkedHashSet 表现更好。但为什么我的代码在这里不起作用？
这个问题可能会在 Codeforces 上得到更多回复，但我还是会在这里回答。
比赛结束后，Codeforces 允许其他用户通过将自定义输入写入其他用户程序的 运行 来“破解”解决方案。如果防御用户的程序 运行 在自定义输入上运行缓慢，他们的代码提交状态将从“已接受”更改为“超过时间限制”。
具体来说，您的代码从“已接受”更改为“超出时间限制”的原因是有人创建了“anti-hash 测试”（您的哈希函数在该测试上会导致许多冲突）你的程序 运行 比平时慢。如果您对如何生成此类测试感兴趣，可以在 Codeforces 上找到几个 post，例如：https://codeforces.com/blog/entry/60442.
正如@Photon 所链接的那样，Codeforces 上有一个 post 解释了为什么您应该避免使用 Java.HashSet 和 Java.HashMap：https://codeforces.com/blog/entry/4876，这主要是由于 anti-hash 测试。在某些情况下，从平衡的 BST 添加额外的 log(n) 因子可能不会那么糟糕（通过使用 TreeSet 或 TreeMap）。在许多情况下，额外的 log(n) 因素不会使您的代码超时，并且它可以保护您免受 anti-hash 测试。
您如何确定您的算法是否足够快以添加 log(n) 因子？我想这需要一些经验，但大多数人建议执行某种计算。大多数在线评委（包括 Codeforces）都会显示您的程序在特定问题上允许 运行 的时间（通常在一到四秒之间），您可以使用 10^9 constant-time 操作每秒作为执行计算时的经验法则。