litjohn 在 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) 中出现。
通过一些神秘联想(主要是单调性相关),大概能想到是二分。但是不同的选项依然...