【Codeforces 1292E】Rin and The Unknown Flower | Mrsrz's blog

构造，分类讨论。

题目大意：

交互题。

给定一个只由 C、H、O 组成的字符串 $s$，你可以进行询问，每次给定一个字符串 $t$，会返回 $t$ 在 $s$ 中作为子串出现的所有位置（开头位置），并花费 $\frac 1{|t|^2}$ 的代价。

你需要花费不超过 $\frac 7 5$ 的代价求出 $s$。

保证 $4\leq |s|\leq 50$。

题解：

我们发现，询问 AA，AB，AC 就可以知道位置 $1\sim n-1$ 中的所有 A。

相应的，询问 AB，BB，CB 就可以知道位置 $2\sim n$ 中的所有 B。

共用一次询问 AB，这里只需要花费 $\frac 5 4$ 的代价。

此时 $2\sim n-1$ 位置的 A 和 B 确定，剩下的就是 C 了。

还有位置 $1$ 和 $n$。

如果位置 $1$ 没有确定，则不可能是 A。同理位置 $n$ 没有确定，则不可能是 B。

那么我们用一次 $n-1$ 的询问和一次 $n$ 的询问即可确定 $1$ 和 $n$ 位置的字符。

总花费 $\frac 5 4+\frac 1{(n-1)^2}+\frac 1 {n^2}$。

当 $n\geq 5$ 时是不会超过的，但是在 $n=4$ 时会超过。

我们可以特判 $n=4$ 的情况，具体实现是一个大分类讨论，可以参考代码。

Code：

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int T,n;
char ans[55];
bool ask(string s){
    cout<<"? "<<s<<endl;
    int k,x;bool ok;
    for(cin>>k,ok=k;k--;){
        cin>>x;
        for(int i=0;i<s.length();++i)ans[x+i-1]=s[i];
    }
    return ok;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        memset(ans,0,sizeof ans),ask("CC"),ask("CH"),ask("CO");
        if(n==4){
            if(ans[3]){
                if(!ans[1]){
                    ask("HC");
                    if(!ans[1])ans[1]='O';
                }
                if(!ans[0]){
                    ask((string)"H"+ans[1]);
                    if(!ans[0])ans[0]='O';
                }
            }else if(!ans[0]&&!ans[1]&&!ans[2]){
                if(ask("HO")){
                    if(ans[2]=='H'&&ans[3]=='O'){
                        if(!ans[0]||!ans[1]){
                            ask("HHHO"),ask("OOHO");
                            if(!ans[0]&&!ans[1])ans[0]='O',ans[1]='H';
                        }
                    }else if(ans[1]=='H'&&ans[2]=='O'){
                        ask("HHOH"),ask("HHOO"),ask("HHOC"),
                        ask("OHOH"),ask("OHOO");if(!ans[3])ans[0]='O',ans[3]='C';
                    }else{
                        ask("HOHC"),ask("HOOC"),ask("HOOH"),ask("HOHH");
                        if(!ans[3])ans[2]=ans[3]='O';
                    }
                }else if(ask("OO")){
                    if(!ans[2])ans[2]='H';
                    if(!ans[3])ans[3]=ask((string)"OO"+ans[2]+"H")?'H':'C';
                }else{
                    ask("HHH"),ans[1]=ans[2]='H';
                    if(!*ans)*ans='O';if(!ans[3])ans[3]='C';
                }
            }else{
                if(!ans[0]){
                    ask("HC");if(!ans[0])ans[0]='O';
                }else if(!ans[2]){
                    ask(ans[1]+(string)"H");if(!ans[2])ans[2]='O';
                }
                if(!ans[3]){
                    string s;s=s+ans[0]+ans[1]+ans[2];
                    ask(s+(string)"C");
                    ask(s+(string)"H");
                    if(!ans[3])ans[3]='O';
                }
            }
        }else{
            ask("HH"),ask("OH");
            for(int i=1;i<n-1;++i)if(!ans[i])ans[i]='O';
            if(!ans[n-1]){
                string s;
                for(int i=1;i<n-1;++i)s+=ans[i];
                s+='C';
                ask(s);
                if(!ans[n-1])ans[n-1]='O';
            }
            if(!ans[0]){
                string s;
                for(int i=1;i<n;++i)s+=ans[i];
                s='H'+s;
                ask(s);
                if(!ans[0])ans[0]='O';
            }
        }
        cout<<"! "<<ans<<endl;
        cin>>n;
        if(!n)break;
    }
    return 0;
}