CF1292E
题意：有一个包含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;
}