题解：P12466 『FCRT / 1 - 3』Wordle

· · 题解

我们不妨将 52 个字母重新标号成 0, 1, \ldots, 51 这 52 个数字。

设答案序列为 S，输入给出的序列为 T，且 S_i = (T_i + k) \bmod 52。假设我们在位置 i 猜 (T_i + k_0) \bmod 52，回答的数就会加上 [k = k_0]。

所以询问的本质就是给一个序列 x_1, x_2, \ldots, x_n，返回 \sum\limits_{i = 1}^{n} [k = x_i]。要在 f(n) 次询问内猜一个 [0, 52) 间的整数 k。

假设现在 k 目前还有 m 种可能的取值，初始时 m = 52。我们找一个最小的整数 m'，试图令 m \gets m'，然后不断迭代直至 m = 1。

什么样的 m' 会合法？假设第 i 种可能取值被问了 c_i 次，那么要求 c_i 的众数出现次数 \le m'，\sum c_i = n。

于是这容易贪心解决，首先尽量让 c_i = 0，满了 m' 个就让 c_i = 1，依次类推。构造出来可能 \sum c_i = n，此时让 c_m 加上 d = n - \sum c_i 即可解决。

容易发现 m' 一定是一段后缀合法，于是可以二分找 m'。

这样每一次猜测都是最优的，正确性容易证明。

#include <iostream>
#include <vector>
#include <functional>
#include <numeric>

using namespace std;

int n;
string s;

char Right_shift (char c, int x) {
  if (x >= 26) c = (c >= 'a' && c <= 'z' ? c - 'a' + 'A' : c - 'A' + 'a'), x -= 26;
  char goal = (c >= 'a' && c <= 'z' ? 'z' : 'Z');
  int walk = min(x, goal - c);
  c += walk, x -= walk;
  if (c == goal && x) {
    if (c == 'z') c = 'A' + x - 1;
    else c = 'a' + x - 1;
  }
  return c; 
}

int Ask (vector<int> a) {
  auto it = s.begin();
  for (int i = 0; i < 52; ++i) {
    while (a[i]--) cout << Right_shift(*it, i), ++it;
  } 
  cout << endl;
  int ret;
  cin >> ret;
  return ret;
}

void Answer (int k) {
  for (auto c : s) cout << Right_shift(c, k);
  cout << endl;
  int ret;
  cin >> ret;
  if (ret != n) {
    cout << "Error ! " << endl;
    exit(1);
  }
}

void Solve () {
  cin >> s, n = s.size();
  vector<int> st(52);
  iota(st.begin(), st.end(), 0);
  while (true) {
    // cout << "! " << st.size() << '\n';
    int cnt = st.size(), L = 1, R = cnt;
    vector<int> way; 
    while (L <= R) {
      int mid = (L + R) >> 1;
      vector<int> lis;
      for (int v = 0; ; ++v) {
        int ned = min(cnt - int(lis.size()), mid);
        for (int i = 0; i < ned; ++i) lis.push_back(v);
        if (lis.size() == cnt) break; 
      }
      int sum = 0; 
      for (auto i : lis) sum += i; 
      if (sum <= n) {
        lis.back() += n - sum;
        way = lis;
        R = mid - 1; 
      }
      else {
        L = mid + 1; 
      }
    }
    vector<int> mp(52);
    for (int i = 0; i < cnt; ++i) mp[st[i]] = way[i];
    int ret = Ask(mp);
    if (ret == n) return; 
    vector<int> candi;
    for (int i = 0; i < cnt; ++i) {
      if (way[i] == ret) candi.push_back(st[i]);
    }
    if (candi.size() == 1) {
      Answer(candi[0]);
      return;
    }
    st = candi;
  }
}

int main () {
  int T;
  cin >> T;
  while (T--) Solve();
  return 0; 
}