[CF1292E]Rin and The Unknown Flower

本文主要是介绍[CF1292E]Rin and The Unknown Flower，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Rin and The Unknown Flower

题解

~~再次吐槽一下CF的spj，WA了不手动退出竟然会返回T~~

我们很容易发现本题记录询问次数的方法有些奇怪，很容易发现，询问长度越长，代价就会越低。
但很明显，询问长度变成只会使得我们的收获减小。所以我们尽量还是先减短我们询问的长度，得出结果。

我们发现，如果我们先询问"CH",“CC”,“CO”,“HO”,“OO"的话，就可以知道除了第n位以外哪些位为"C”,除了第1位以外哪些位为"O"。于是， $(1, n)$ 中剩下的没填的就只能为"H"。
现在第1位如果没有的话只剩下"H","O"两种选择，询问其中一个就可以知道其值。第n位同理。
这样做的代价为 $\frac{5}{4}+\frac{1}{(n-1)^2}+\frac{1}{n^2}$ 。对于 $n > 4$ 的情况都可以过，但 $n = 4$ 时代价 $>\frac{7}{5}$ ，需要单独处理。

当 $n = 4$ 时，我们先询问"CH",“CC”,“CO”,“HO"四种情况。
我们发现，此时，如果第 $2$ 位为"O"的话，前三位只有"OOO"与"OOH"两种情况。
如果询问"OOO"与"OOH"时有解，我们只需再枚举第四位即可。此时的代价为 $\frac{11}{9}+\frac{1}{8}<\frac{7}{5}$ 。
如果都不对的话，第二位与第三位都只能为"H”。此时第一位只能为"H"或"O"，第n位只能为"C"或"H"。各自询问一次就能有解。代价为 $\frac{4}{3}+\frac{1}{16}<\frac{7}{5}$ 。

这样，就可以将这道题解决了。

源码

~~贞德难调~~

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long LL;
const int INF=0x7f7f7f7f;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while('0'>s||'9'<s){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
} 
int t,n,len;
char str[55],qstr[55];
void ask(){//for(int i=1;i<=len;i++)if(!qstr[i])qstr[i]='H';printf("? %s\n",qstr+1);fflush(stdout);int k;read(k);for(int i=1;i<=k;i++){int id;read(id);for(int j=0;j<len;j++)str[j+id]=qstr[j+1];}
}
void print(){//for(int i=1;i<=n;i++)if(!str[i])str[i]='H';printf("! %s\n",str+1);fflush(stdout);int k;read(k);if(!k&&str[1]=='H'&&str[2]=='O')exit(0);
}
signed main(){read(t);int tt=0;while(t--){memset(str,0,sizeof(str));memset(qstr,0,sizeof(qstr));read(n);if(n>4){len=2;qstr[1]='C';qstr[2]='H';ask();qstr[1]='C';qstr[2]='O';ask();qstr[1]='C';qstr[2]='C';ask();qstr[1]='H';qstr[2]='O';ask();qstr[1]='O';qstr[2]='O';ask();for(int i=2;i<n;i++)if(!str[i])str[i]='H';if(!str[1]){len=n-1;for(int i=2;i<=len;i++)qstr[i]=str[i];qstr[1]='O';ask();if(!str[1])str[1]='H';}if(!str[n]){len=n;for(int i=1;i<len;i++)qstr[i]=str[i];qstr[n]='C';ask();if(!str[n])str[n]='H';//printf("strn%c\n",str[n]);}print();continue;}else{len=2;qstr[1]='C';qstr[2]='H';ask();qstr[1]='C';qstr[2]='O';ask();qstr[1]='C';qstr[2]='C';ask();qstr[1]='H';qstr[2]='O';ask();int sum=0;for(int i=1;i<=4;i++)if(!str[i])sum++;if(!sum){print();continue;}if(sum==1){int id;for(int i=1;i<=4;i++)if(!str[i])id=i;len=4;for(int i=1;i<=4;i++)qstr[i]=str[i];qstr[id]='O';ask();if(str[id]){print();continue;}qstr[id]='H';ask();if(!str[id])str[id]='C';print();continue;}if(sum==2){if(!str[2]){len=3;qstr[1]='O';qstr[2]=str[3];qstr[3]=str[4];ask();if(!str[2])str[2]='H';len=4;for(int i=2;i<=4;i++)qstr[i]=str[i];qstr[1]='O';ask();if(!str[1])str[1]='H';}else if(!str[3]){len=3;qstr[1]=str[1];qstr[2]=str[2];qstr[3]='O';ask();if(!str[3])str[3]='H';len=4;for(int i=1;i<=3;i++)qstr[i]=str[i];qstr[4]='O';ask();if(str[4]){print();continue;}qstr[4]='H';ask();if(!str[4])str[4]='C';}else if(!str[4]){len=3;qstr[3]=str[3];qstr[2]=str[2];qstr[1]='O';ask();if(!str[1])str[1]='H';len=4;for(int i=1;i<=3;i++)qstr[i]=str[i];qstr[4]='O';ask();if(str[4]){print();continue;}qstr[4]='H';ask();if(!str[4])str[4]='C';}print();continue;}len=3;qstr[1]=qstr[2]=qstr[3]='O';ask();qstr[3]='H';ask();if(str[3]){if(str[1]&&str[4])tt=1;else if(!str[1]){len=4;for(int i=2;i<5;i++)qstr[i]=str[i];qstr[1]='O';ask();if(!str[1])str[1]='H';}else if(!str[4]){len=4;for(int i=1;i<4;i++)qstr[i]=str[i];qstr[4]='O';ask();if(str[4]){print();continue;}qstr[4]='H';ask();if(!str[4])str[4]='C';}print();continue;}if(!str[2])str[2]=str[3]='H';len=3;qstr[1]=qstr[2]=qstr[3]='H';ask();if(!str[1])str[1]='O';len=4;for(int i=1;i<4;i++)qstr[i]=str[i];qstr[4]='H';ask();if(!str[4])str[4]='C';print();continue;}}return 0;
}