CF1705F Mark and the Online Exam 题解

Phartial · 2024-02-24 13:02:38 · 题解

首先这个东西可以转化成每次询问子集和：在开始询问一次全 \texttt{F} 可以得到 \sum_{i}[s_i=\texttt{F}]，询问一个集合 S 可以得到 \sum_{i\in S}[s_i=\texttt{T}]+\sum_{i\notin S}[s_i=\texttt{F}]，有：

解方程就可以得到 \sum_{i\in S}[s_i=\texttt{T}] 了。以下的询问均指询问子集和。

设 f_n 为 2^n 次询问能够确定的最长序列长度，显然有 f_0=1。

令 q_n 为具体的询问方案，为方便，不妨令最后一次询问总是询问整个序列中 1 的个数，即 q_{n,2^n}=\{i\mid 1\le i\le f_n\}（下标从 1 开始）。

可以使用以下构造方式得到 f_{n+1}=2f_n+2^n-1 的结果（设 \operatorname{query}(S) 为询问 S 得到的结果）：

1. 将长度为 2f_n+2^n-1 的序列分成长度为 f_n,f_n,2^n-1 的三块；
2. 询问第二块中 1 的个数，记作 c=\operatorname{query}(\{k\mid f_n+1\le k\le 2f_n\})；
3. 对所有 1\le i<2^n，询问 q_{n,i}\cup\{f_n+k\mid k\in q_{n,i}\}\cup\{2f_n+i\} 与 q_{n,i}\cup\{f_n+k\mid k\notin q_{n,i}\}，不妨设两次询问的结果分别为 a=\operatorname{query}(q_{n,i})+\operatorname{query}(\{f_n+k\mid k\in q_{n,i}\})+\operatorname{query}(\{2f_n+i\}) 和 b=\operatorname{query}(q_{n,i})+(c-\operatorname{query}(\{f_n+k\mid k\in q_{n,i}\}))，则有：
4. 询问整个序列中 1 的个数。

于是我们就在 2^{n+1} 次询问中得到了还原第一、二块需要的每个询问的答案，并额外知道了 2^n-1 位的值。

使用归纳法不难证明 f_n=n2^{n-1}+1。于是我们就可以在 \mathcal{O}(\frac{n}{\log n}) 次询问内还原出长度为 n 的序列。

本题中 n\le 1000，可以在 257 次操作内还原出整个序列。遥遥领先。

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int kN = 1001;

int n, c0;

int Q(string s) {
  s = s.substr(0, n);
  int l = count(s.begin(), s.end(), 'T'), v;
  cout << s << endl;
  cin >> v;
  return (l - (c0 - v)) / 2;
}
vector<string> G(int k) {
  if (k == 0) {
    return {"T"};
  }
  vector<string> l = G(k - 1);
  int n = l[0].size();
  vector<string> p;
  string _ = string(l.size() - 1, 'F');
  for (int i = 0; i < l.size() - 1; ++i) {
    _[i] = 'T';
    p.push_back(l[i] + l[i] + _);
    _[i] = 'F';
    string _l;
    for (char &ch : l[i]) {
      _l += 'T' + 'F' - ch;
    }
    p.push_back(l[i] + _l + _);
  }
  p.push_back(string(n, 'F') + string(n, 'T') + _);
  p.push_back(string(n * 2 + l.size() - 1, 'T'));
  return p;
}
string C(int k, vector<int> &q) {
  if (k == 0) {
    return q[0] ? "T" : "F";
  }
  vector<int> lq, rq;
  int c = q[q.size() - 2];
  string ans, t;
  for (int i = 0; i + 2 < q.size(); i += 2) {
    int a = q[i], b = q[i + 1];
    lq.push_back((a + b - c) / 2);
    rq.push_back((a - b + c) / 2);
    t += "FT"[(a + b - c) & 1];
  }
  rq.push_back(c);
  lq.push_back(q.back() - c - count(t.begin(), t.end(), 'T'));
  return C(k - 1, lq) + C(k - 1, rq) + t;
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  cout << string(n, 'F') << endl;
  cin >> c0;
  vector<string> ql = G(8);
  vector<int> sl;
  for (string i : ql) {
    sl.push_back(Q(i));
  }
  Q(C(8, sl));
  return 0;
}