自动搬运

查看原文

来自洛谷，原作者为

	Sliarae Re:start

搬运于2025-08-24 23:15:46，当前版本为作者最后更新于2025-05-10 16:24:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们不妨将 $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; 
}