codeforces 每日一题

问题描述：

如题。既然 leetcode 有每日一题，CF 应该也可以？

https://codeforces.com/problemset/problem/1697/D

这个题目是神秘交互。首先考虑一种套路，即逐个字符确定。

我一开始走了一些弯路。这里直接讲到正解。假设已经知道了 [1, i)，如何确定第 i 个字符？

注意到操作 1 的次数很少且只有 26 次，非常合理怀疑每种字母使用一次操作 1.

重点在操作 2. 它有什么用？

注意到，选定一个区间左端点 l，然后对区间 [l, i] 使用第二类查询，如果得到的回答 res 比 [l, i) 区间中的不同字符种类数更多，说明 i 在 [l, i) 中根本没有出现。否则说明出现了。

随着 [l, i] 不断向左扩充，i 更加有可能在 [l, i) 中出现。

通过一些神秘联想（主要是单调性相关），大概能想到是二分。但是不同的选项依然太多了。

注意到，我们得到的信息是关于 i 和 [l, i) 中字符构成的集合的。那么，显然如果两个不同的 l 的选择使得 [l, i) 中字符构成的集合是相同的，这两个 l 就是等价的。

考虑所有本质不同的等价类，并在每类中选出一个 l 作为代表。不难发现，每种字符最后一次出现的位置恰好代表了一个等价类。

这样，我们对这些代表点进行二分，就能得到当前字符与哪个之前的字符是相等的。如果找不到相等的字符，动用操作 1 查询当前字符。

确实说的比较抽象，中间跳跃步骤有点多。许多我自己做的时候的弯路没写进去，所以可能需要自己尝试解决题目才能理解。