题解：CF1292E Rin and The Unknown Flower

· · 题解

Rin and The Unknown Flower

挺有意思的一道构造题。

首先 n 比较大时，则 \frac{1}{n^2} 就很小，这个性质可以允许我们在确定了大部分位置后穷举问出少量未确定的位置。为了确定大部分的位置，则需要把每个字母出现的大部分位置都确定下来。先考虑 \texttt{C}，如果问一次 \texttt{C} 就可以知道所有 \texttt{C} 的位置，花费为 1。但如果问了 \texttt{CC}, \texttt{CH}, \texttt{CO}，就可以知道除了最后一个位置外的位置是否为 \texttt{C}。按照同样的 3 次操作，可以问出另一字母的位置。不过 6 次长度为 2 的询问未免多了些，则可以让其中一个操作有一箭双雕的作用。如问了上文的 3 个操作后，再问 \texttt{HO}, \texttt{OO}，就可以知道出了第一个位置外的位置是否为 \texttt{O}。则第 2 至 n-1 个位置中不为 \texttt{C} 或 \texttt{O} 的位置都为 \texttt{H}，第一个位置若没问出则为 \texttt{H} 或 \texttt{O}，最后一个位置若没问出则为 \texttt{H} 或 \texttt{C}。共 4 种情况，询问前 3 种，若都不是则为第 4 种。这样的花费为 \frac{5}{4}+\frac{3}{n^2}，可以通过 n \geq 5 的测试点。

当 n=4 时，由于 n 比较小，则情况总数少，每一步询问后就会有更多的性质。按照前面的方法先问前 4 问，若问出来任意一组，则知道至少两个位置，仍未知的位置若是在前 3 个位置中就不可能是 \texttt{C}，这样最多只有 6 种情况，问 5 次即可。花费 1+\frac{5}{16}。

若没问出，再问 \texttt{OO}。如果 \texttt{OO} 出现，则会有 \texttt{OOOO}, \texttt{OOO?}, \texttt{OO??} 三种情况。其中第三种情况的第三位必然为 \texttt{H}。若最后一位未知，则只可能是 \texttt{C} 或 \texttt{H}。问一次即可。花费 \frac{5}{4}+\frac{1}{16}。

若问完 \texttt{OO} 后还没问出任意一组，则中间必然是 \texttt{HH}。再问一次 \texttt{HHH}，若第一个位置未知，则必为 \texttt{O}；若最后一个位置未知，则必为 \texttt{C}。花费 \frac{5}{4}+\frac{1}{9}。

最后实现时可以将一些类似的操作合并，枚举的时候即使是重复的也不用管，因为不会超过最坏情况。然后询问，回答，以及枚举情况的部分写成函数。这样代码就会简单很多。对于有的题解里说代码超过 500 行……不好评价。我的代码只有短短 60 行，2k 都不到。

Code

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(x) ((int)x.size())
#define vi vector <int>
#define L(i, j, k) for (int i=(j); i<=(k); ++i)
using namespace std;
string c; int n; vector <string> tmp;
vi ask(string s) {
    cout<<"? "<<s<<endl; int cnt; cin>>cnt; vi tmp;
    while (cnt--) { int x; cin>>x; tmp.eb(x-1); L(i, 0, sz(s)-1) c[x-1+i]=s[i]; }
    return tmp;
}
void submit(string s) { cout<<"! "<<s<<endl; }
void ttry() {
    L(i, 0, sz(tmp)-2) if (!ask(tmp[i]).empty()) return submit(tmp[i]);
    submit(tmp[sz(tmp)-1]);
}
void sub1() {
    ask("CC"); ask("CH"); ask("CO"); ask("HO"); ask("OO");
    L(i, 1, n-2) if (!c[i]) c[i]='H';
    bool f1=!c[0], f2=!c[n-1];
    if (f1) c[0]='O'; if (f2) c[n-1]='C'; tmp.eb(c);
    if (f1) c[0]='O'; if (f2) c[n-1]='H'; tmp.eb(c);
    if (f1) c[0]='H'; if (f2) c[n-1]='C'; tmp.eb(c);
    if (f1) c[0]='H'; if (f2) c[n-1]='H'; tmp.eb(c);
    ttry();
}
void sub2() {
    ask("CC"); ask("CH"); ask("CO"); ask("HO");
    if (c[0]||c[1]||c[2]||c[3]) {
        int p1=0, p2=0; while (c[p1]&&p1<3) ++p1;
        p2=p1+1; while (c[p2]&&p2<3) ++p2; if (p2==4) p2=3;
        c[p1]='O', c[p2]='C'; tmp.eb(c);
        c[p1]='O', c[p2]='H'; tmp.eb(c);
        c[p1]='O', c[p2]='O'; tmp.eb(c);
        c[p1]='H', c[p2]='C'; tmp.eb(c);
        c[p1]='H', c[p2]='H'; tmp.eb(c);
        c[p1]='H', c[p2]='O'; tmp.eb(c);
        return ttry();
    }
    vi rec=ask("OO");
    if (!rec.empty()) {
        if (!c[2]) c[2]='H';
        if (c[3]) return submit(c);
        c[3]='C'; tmp.eb(c);
        c[3]='H'; tmp.eb(c);
        return ttry();
    }
    c[1]=c[2]='H', c[0]='O', c[3]='C';
    ask("HHH"); submit(c);
}
signed main() {
    int T; cin>>T;
    while (T--) {
        cin>>n; string().swap(c); vector <string> ().swap(tmp); L(i, 1, n) c.pb(0);
        if (n>4) sub1(); else sub2();
        int res; cin>>res; if (res) cout<<endl; else return 0;
    }
}