Codeforces

Luogu

分析

首先查一下 CCCHCOHOOO。这样子我们就能确定 $[2,n-1]$ 中所有字符(没有确定的位置一定是 H)。此时如果 $1$ 没有确定,则它不可能是 C;如果 $n$ 没有确定,则它不可能是 O。这样子只有 $4$ 种情况,做 $3$ 次长度为 $n$ 的查询即可。

这样子总花费是 $1.25+\frac{3}{n^2}$ 的,当 $n\geq 5$ 时可以过。

所以我们特判 $n=4$ 的情况。先询问 CCCHCOHO。如果 $2,3$ 已经确定,而 $1,4$ 未被确定,则 $1$ 不可能是 C,所以只有 $6$ 种情况,做 $5$ 次查询即可,花费为 $1.3125$;否则我们再查询 OO,即可确定 $2,3$:如果 $2,3$ 是 HH 则再询问 HHH 即可得到 $1,4$,花费约为 $1.36$,否则 $1$ 和 $4$ 一定确定了一个,做 $2$ 次查询即可,花费为 $1.375$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50+10;

char ans[N];

char a[N]; int l;
int ask() {
    a[l+1]='\0',printf("? %s\n",a+1); fflush(stdout);
    int t=read(); if (t<0) exit(0);
    for (int i=1;i<=t;++i) {
        int p=read();
        for (int j=1;j<=l;++j) ans[p+j-1]=a[j];
    }
    return t;
}

int main() {
    int T=read();
    while (T--) {
        int n=read();
        for (int i=1;i<=n;++i) ans[i]='\0';
        if (n==4) {
            a[1]='C',a[2]='C',l=2,ask();
            a[1]='C',a[2]='H',l=2,ask();
            a[1]='C',a[2]='O',l=2,ask();
            a[1]='H',a[2]='O',l=2,ask();
            if (!ans[1]&&ans[2]&&ans[3]&&!ans[4]) {
                a[1]=ans[1]?ans[1]:'H',a[2]=ans[2],a[3]=ans[3],a[4]=ans[4]?ans[4]:'C',l=4,ask();
                a[1]=ans[1]?ans[1]:'H',a[2]=ans[2],a[3]=ans[3],a[4]=ans[4]?ans[4]:'H',l=4,ask();
                a[1]=ans[1]?ans[1]:'H',a[2]=ans[2],a[3]=ans[3],a[4]=ans[4]?ans[4]:'O',l=4,ask();
                a[1]=ans[1]?ans[1]:'O',a[2]=ans[2],a[3]=ans[3],a[4]=ans[4]?ans[4]:'C',l=4,ask();
                a[1]=ans[1]?ans[1]:'O',a[2]=ans[2],a[3]=ans[3],a[4]=ans[4]?ans[4]:'H',l=4,ask();
                if (!ans[1]) ans[1]='O';
                if (!ans[4]) ans[4]='O';
            } else {
                a[1]='O',a[2]='O',l=2,ask();
                if (!ans[2]) ans[2]='H';
                if (!ans[3]) ans[3]='H';
                if (ans[2]=='H'&&ans[3]=='H') {
                    a[1]='H',a[2]='H',a[3]='H',l=3,ask();
                    if (!ans[1]) ans[1]='O';
                    if (!ans[4]) ans[4]='C';
                } else {
                    if (!ans[1]) {
                        a[1]='H',a[2]=ans[2],a[3]=ans[3],a[4]=ans[4],l=4,ask();
                        a[1]='O',a[2]=ans[2],a[3]=ans[3],a[4]=ans[4],l=4,ask();
                    } else {
                        a[1]=ans[1],a[2]=ans[2],a[3]=ans[3],a[4]='C',l=4,ask();
                        a[1]=ans[1],a[2]=ans[2],a[3]=ans[3],a[4]='H',l=4,ask();
                    }
                }
            }
        } else {
            a[1]='C',a[2]='C',l=2,ask();
            a[1]='C',a[2]='H',l=2,ask();
            a[1]='C',a[2]='O',l=2,ask();
            a[1]='H',a[2]='O',l=2,ask();
            a[1]='O',a[2]='O',l=2,ask();
            for (int i=2;i<n;++i) if (!ans[i]) ans[i]='H';
            for (int i=2;i<n;++i) a[i]=ans[i];
            a[1]=ans[1]?ans[1]:'O',a[n]=ans[n]?ans[n]:'C',l=n,ask();
            for (int i=2;i<n;++i) a[i]=ans[i];
            a[1]=ans[1]?ans[1]:'O',a[n]=ans[n]?ans[n]:'H',l=n,ask();
            for (int i=2;i<n;++i) a[i]=ans[i];
            a[1]=ans[1]?ans[1]:'H',a[n]=ans[n]?ans[n]:'C',l=n,ask();
            if (!ans[1]) ans[1]='H';
            if (!ans[n]) ans[n]='H';
        }
        ans[n+1]='\0',printf("! %s\n",ans+1),fflush(stdout);
        if (!read()) exit(0);
    }
    return 0;
}
最后修改:2020 年 06 月 07 日 02 : 23 PM