link

题意:有一个包含O,H,C的串,你现在只知道长度,每次可以询问一个串t在这个串里的所有出现位置,代价是$\frac{1}{|t|^2}$,你需要用不超过1.4的代价询问出这个串。


这个做法目前是$1.333333$的。

下面用1来代替C,2来代替H,3来代替O。

考虑可以先询问长度为2的串,可以得到每个字符前后可以接哪些字符。

假设我们已经有确定的位置了,可以进行如下操作来找到原串:

对于每个极长(已经确定位置的)串,如果前一个/后一个可以确定,就加上这个字符

如果没有字符能被这样加上,就找到最长的子串,在前面和后面中选出可能情况较少的一边,遍历每个取值,询问直到加上这个取值出现在原串里(最后一个取值不用询问)

那么现在考虑询问长度为2的串来找到确定的位置

考虑询问完一个串之后,除了出现位置其它位置都不是这个子串。

那么考虑先按照11,12,13的顺序询问,如果找到了11或12子串,可以直接暴力搞出原串。否则询问完13之后就没有1开头的串了,也就是除了最后一个位置,其它没确定的位置一定不是1,如果找到了13可以暴力判,次数<= $0.75+\sum_{i=3}^n\frac{1}{i^2}$ 其中某一个串找到了位置,则可以直接暴力判。

如果都没找到可以考虑询问23和32,如果找到了至少一个,那么剩下除了最后一个位置都已经确定了,只用询问一次长度为n

如果全部没找到则串只有可能是22221 33331 22222 33333这四种情况,可以判一次2222再判一次33333解决,代价是$1.25+\frac{1}{(n-1)^2}+\frac{1}{n^2}$,$n=4$时为$1.423611$,$n=5$时为$1.3525$。

考虑优化$n=4$的情况。

考虑询问23之后的局面

如果发现了23可以询问32再判一次是1.3125的

如果没发现则只能333...222..1这种串了

情况大概有这些:

3331
3321
3221
2221
3333
3332
3322
3222
2222

考虑按照长度为3的子串分组:

3331 (333)
3333
3332

 2221 (222)
3222
2222

3322
 3221 (322)

3321 (3321)

直接按顺序询问不够优秀,因为最后一组个数太多,可以和第二组交换

所以流程就变成了:

询问 333 如果存在就判断3331/3332 (1次3 2次4) 否则
询问 322 如果存在就得到答案 否则
询问 222 如果存在就得到答案 否则答案是3321

于是$n=4$最坏情况变成了1.333,已经足以通过了

考虑优化$n>4$的前面一部分:

注意到最坏情况依然是23和32都没找到的情况,考虑套用类似优化:

考虑询问23之后的局面

如果发现了23可以询问32再判一次

如果没发现则只能333...222..1这种串了

不过n增加之后不好找规律了,考虑通用操作

(下文无特殊情况均为len=n-1)

先判333...
然后333...2
然后333...22
然后类似的直到发现子串或者322...也没找到
如果发现子串那么一定最多只有最后一个字符不知道,可以是1/2,暴力询问
如果没发现那么222..一定是一个子串,判222..1或222..2。

这一部分最坏变成了1.29

然后我不会优化n=4了

贴个代码

int n;
int nx[4][4];
int w[55];
int od[4],id[4];
char s[]={" CHO"};
bool ask(const vector<int>&vt){
    cout<<"? ";
    for(auto i:vt)cout<<s[i];
    cout<<endl;
    int k;
    cin>>k;
    if(!~k)exit(0);
    if(!k)return 0;
    int m=vt.size();
    for(;k;--k){
        int x;
        cin>>x;
        for(int i=0;i<m;++i)w[i+x]=vt[i];
    }
    return 1;
} 
bool find(){
    int s=-1,at=0;
    for(int i=1;i<=n;++i)if(w[i]){
        if(i>1&&id[w[i]]==1){
            for(int j=1;j<=3;++j)if(nx[j][w[i]]){w[i-1]=j;return 1;}
        }
        int j=i;
        while(w[j+1])++j;
        if(j<n&&od[w[j]]==1){
            for(int k=1;k<=3;++k)if(nx[w[j]][k]){w[j+1]=k;return 1;}
        }
        if(chkmax(s,j-i))at=i;
        i=j;
    }
    if(s==n-1)return 0;
    int wi=at==1?inf:id[w[at]],wo=at+s==n?inf:od[w[at+s]]-(at+s==n-1||od[1]?0:1);
    if(wi<=wo){
        vector<int> q(s+2);
        for(int i=0;i<=s;++i)q[i+1]=w[i+at];
        int c=id[w[at]];
        for(int i=1;i<=3;++i)if(nx[i][w[at]]){
            if(c>1){
                q[0]=i;
                if(ask(q))return 1;
                --c;
            }
            else {w[at-1]=i;return 1;}
        }
    }
    else{
        vector<int> q(s+2);
        for(int i=0;i<=s;++i)q[i]=w[i+at];
        int c=wo;
        for(int i=1;i<=3;++i)if(nx[w[at+s]][i]&&(i!=1||at+s==n-1||od[1])){
            if(c>1){
                q[s+1]=i;
                if(ask(q))return 1;
                --c;
            }
            else {w[at+s+1]=i;return 1;}
        }
    }
    return 0;
}
bool try2(int x,int y){
    if(ask({x,y})){nx[x][y]=0;--od[x];--id[y];return 1;}
    else {nx[x][y]=0;--od[x];--id[y];return 0;}
}
void answer(){
    cout<<"! ";
    for(int i=1;i<=n;++i)cout<<s[w[i]];
    cout<<endl;
    int k;
    cin>>k;
    if(!~k)exit(0);
    for(int i=1;i<=n;++i)w[i]=0;
}
bool gg(){
    if(n==4){
        if(ask({3,3,3})){
            nx[3][3]=0;
            if(!w[4])return ((ask({3,3,3,1}))||(w[4]=2)),0;
            return 0;
        }
        else if(ask({2,2,2})){
            nx[2][2]=0;
            if(!w[4])w[4]=1;
            if(!w[1])w[1]=3;
            return 0;
        }
        else if(ask({3,2,2})){
            if(w[1])w[4]=1;
            else w[1]=3;
            return 0;
        }
        else return (w[1]=3,w[2]=3,w[3]=2,w[4]=1),0;
    }
    else{
        vector<int> v(n-1,3);
        int m=n-1;
        while(m&&!ask(v)){v[m-1]=2;--m;}
        for(int i=0;i<n-1;++i)w[i+1]=v[i];
        while(find());
        return 0;
    }
}
bool fnd(){
    while(find());
    return 1;
}
void query(){
    for(int i=1;i<=3;++i)for(int j=1;j<=3;++j)nx[i][j]=1;
    for(int i=1;i<=3;++i)od[i]=id[i]=3;
    (try2(1,1)||try2(1,2)||try2(1,3)||(try2(3,2)&&(try2(2,3)||1))||gg())&&fnd();
    answer();
}
signed main(){
    int t;
    cin>>t;
    for(;t;--t){
        cin>>n;
        query();
    }
    return 0;
}

标签: 交互题

添加新评论