Guess The String

Created by LXC on Tue Apr 23 19:28:22 2024

https://codeforces.com/problemset/problem/1697/D

ranting: 1900

tag: binary search, constructive algorithms, interactive

problem

本题为交互题，使用 IO 交互。

在你输出一行后，请清空缓冲区：

• 在 C++ 中，使用 fflush(stdout) 或 cout.flush()。

• 在 Pascal 中，使用 flush(output)。

• 在 Python 中，使用 stdout.flush()。

• 其他语言请自行查阅文档。

请遵循题目完成交互，发出不合法询问可能会出现 TLE，WA 等问题。

---

给定一个长度为 $n$ 且只包含小写字母的字符串 $S$，你需要猜出它。

一共有 $4$ 种交互方式：

格式	允许调用次数	限制	返回值	说明
无	$1$	无	一个整数，$n$ 的值。	在最开始调用。
? 1 i	$26$	$i$ 为 $[1,n]$ 范围内的整数。	一个字符，$S_i$（$S$ 的第 $i$ 个字符）。	无
? 2 l r	$6 \times 10^3$	$1 \le l \le r \le n$，且 $l,r$ 为整数。	一个整数，$S_{l \ldots r}$（$S$ 的第 $l$ 至 $r$ 个字符）中不同字符的种数。	无
! s	$1$	$s$ 是一个字符串，代表你所认为的 $S$。	（评测结果——AC 或 WA。）	最后调用，然后停止交互。

---

对于 $100%$ 的数据，$1 \le n \le 10^3$。

solution

在猜第i个字符前，假设前面的字符都猜出了。

那么前面最多就26个不同的字符，我们维护每种最后一次出现的位置。

通过第二种查询，查询区间包含了当前i位置的字符，这是未知的。如果查询已知有k种不同的字符，查询得到的结果是k+1说明当前i位置的字符是与这k个字符不同的，而一但查询区间向左扩展再加入一种新字符，查到的结果仍然是k+1，那么说明当前字符就是新加入的字符。

这个具有二段性，可以二分查找，不超过5次可以得到，所以最多只需要5000次第二种查询。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

string s = "abcdsasfasfdxwsfdsafdsaafdxdfsawzefafdsadfsa";

char ask1(int x) {
    cout << "? 1 " << x << endl;
    // return s[x-1];
    string t;
    cin >> t;
    return t[0];
}

int ask2(int l, int r) {
    cout << "? 2 " << l << " " << r << endl;
    // vector<int> c(26);
    // for (int i=l-1; i<r; i++) {
    //     c[s[i]-'a'] = 1;
    // }
    // return accumulate(c.begin(), c.end(), 0);
    int x;
    cin >> x;
    return x;
}

void sol() {
    int n;
    cin >> n;
    // n = s.size();
    string t(1+n, '0');
    vector<int> c(26, 0);
    for (int i=1; i<=n; i++) {
        vector<int> idx(26);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int x, int y) {
            return c[x] > c[y];
        });
        // cout << c << "\n";
        // cout << idx << endl;
        // int p = 1;
        // for (int j:idx) {
        //     if (c[j] == 0) break;
        //     int r = ask2(c[j], i);
        //     if (p == r) {
        //         t[i] = char(j+'a');
        //         break;
        //     } else {
        //         p = r;
        //     }
        // }
        int l = 0, r = 26;
        while (r>0 && c[idx[r-1]] == 0) r--;
        int e = r;
        while (l<r) {
            int m = l+r>>1;
            if (m+2 == ask2(c[idx[m]], i)) {
                l = m+1;
            } else {
                r = m;
            }
        }
        if (e == r) {
            t[i] = ask1(i);
        } else {
            t[i] = char(idx[r]+'a');
        }
        c[t[i]-'a'] = i;
        // cout << i << ": " << t[i] << endl;
    }
    cout << "! " << t.substr(1) << endl;
    // assert(t.substr(1) == s);
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}