CF1028G Guess the number [DP][交互]

CF1028G Guess the number

神仙交互题...

我们考虑如果已经可以确定答案\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;
}