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 查询当前字符。
确实说的比较抽象，中间跳跃步骤有点多。许多我自己做的时候的弯路没写进去，所以可能需要自己尝试解决题目才能理解。
#include <bits/stdc++.h>
using namespace std;
char ask1(int i) {
cout << "? 1 " << i << endl;
char c;
cin >> c;
return c;
}
int ask2(int l, int r) {
if (l > r) return 0;
cout << "? 2 " << l << " " << r << endl;
int res;
cin >> res;
return res;
}
int n;
array<int, 26> last;
string ans;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
auto tmp = last;
ranges::sort(tmp);
int l = 0, r = 25;
while (l < 26 && tmp[l] == 0) {
l++;
}
while (l <= r) {
int mid = (l + r + 1) >> 1;
// clog << mid << "\n";
int res = ask2(tmp[mid], i), cnt = 26 - mid;
if (res == cnt) {
if (l == r) {
break;
}
l = mid;
} else {
r = mid - 1;
}
}
if (r < l) {
char ch = ask1(i);
ans.push_back(ch);
last[ch - 'a'] = i;
} else {
char ch = ans[tmp[l] - 1];
ans.push_back(ch);
last[ch - 'a'] = i;
}
}
cout << "! " << ans << endl;
return 0;
}
网友解答：
--【壹】--：
佬可以看看灵茶和羊蹄
--【贰】--：
好像目前 L 站没有 #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 查询当前字符。
确实说的比较抽象，中间跳跃步骤有点多。许多我自己做的时候的弯路没写进去，所以可能需要自己尝试解决题目才能理解。
#include <bits/stdc++.h>
using namespace std;
char ask1(int i) {
cout << "? 1 " << i << endl;
char c;
cin >> c;
return c;
}
int ask2(int l, int r) {
if (l > r) return 0;
cout << "? 2 " << l << " " << r << endl;
int res;
cin >> res;
return res;
}
int n;
array<int, 26> last;
string ans;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
auto tmp = last;
ranges::sort(tmp);
int l = 0, r = 25;
while (l < 26 && tmp[l] == 0) {
l++;
}
while (l <= r) {
int mid = (l + r + 1) >> 1;
// clog << mid << "\n";
int res = ask2(tmp[mid], i), cnt = 26 - mid;
if (res == cnt) {
if (l == r) {
break;
}
l = mid;
} else {
r = mid - 1;
}
}
if (r < l) {
char ch = ask1(i);
ans.push_back(ch);
last[ch - 'a'] = i;
} else {
char ch = ans[tmp[l] - 1];
ans.push_back(ch);
last[ch - 'a'] = i;
}
}
cout << "! " << ans << endl;
return 0;
}
网友解答：
--【壹】--：
佬可以看看灵茶和羊蹄
--【贰】--：
好像目前 L 站没有 #codeforces 标签？