11/8
15:55
神仙交互题…
我们考虑如果已经可以确定答案\geq l,可以问q次,那么可以确定的r最大是什么.
令f_{l,q}表示这个值.实际上询问一些位置就是在把序列分段,我们考虑一段一段处理.令r_i表示第i个数可以确定的r
r_0 = l, r_i = r_{i-1}+f_{r_{i-1},q-1} + 1
f_{l,q}=r_{l+1}-l-1
(边界区间开闭什么的感性理解一下…)
用r表示当前可以确定的右端点,用f构造询问,交互即可
#include <bits/stdc++.h>
const int K = 10000;
long long f[K + 10][6];
std::vector<long long> query;
long long dfs(long long l, int q) {
if (q == 0)
return 0;
l = std::min(l, (long long)K);
if (f[l][q])
return f[l][q];
long long r = l;
for (int i = 1; i <= l + 1; ++i)
r += dfs(r, q - 1) + 1;
f[l][q] = r - l - 1;
return f[l][q];
}
int main() {
dfs(1, 5);
long long r = 1;
for (int i = 1; i <= 5; ++i) {
query.clear();
query.push_back(r - 1);
int lim = std::min(r, (long long)K);
for (int j = 1; j <= lim; ++j) {
int _lim = std::min(r, (long long)K);
r += f[_lim][5 - i];
query.push_back(r++);
}
std::cout << query.size() - 1 << ' ';
for (unsigned j = 1; j < query.size(); ++j)
std::cout << query[j] << ' ';
std::cout << std::endl;
int c; std::cin >> c;
if (c == -1)
break;
r = query[c] + 1;
}
return 0;
}