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\)的前面一部分：
注意到最坏情况依然是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;
}