题解 CF1286C1 【Madhouse (Easy version)】
Rhodoks
2020-01-06 13:27:09
[Hard version link](https://www.luogu.com.cn/blog/Rhodoks/solution-cf1286c2)
题意：有一个字符串$s$，可以询问3次它的子串$s[l..r]$，返回这一子串的所有子串，并且子串间的顺序与子串内部字符的顺序全部打乱。至多询问三次，并且返回的字符串数不能超过$(n+1)^2$个。输出$s$。
考虑询问$s[1..n]$和$s[2..n]$，共计返回字符串数为$\frac{n*(n+1)}{2}+\frac{n*(n-1)}{2}=n^2$，询问次数为2，满足要求。
相对于$s[2..n]$，询问$s[1..n]$得到的子串额外增加了$s[1..i](1 \leq i \leq n)$,如果我们能够得到这$n$个字符串，那么可以通过长度区分出他们。$s[1..i]$比$s[1..i-1]$多出来的那一个字符，便是字符串第$i$位上的字符。
使用$\text{sort}$和$\text{multiset}$实现去重，首先将读入的每个字符串都进行一遍排序，这样两个由同样字符组成（顺序可以不同）的字符串会得到同一个结果。本题中因为子串被打乱，顺序并不重要。
将$s[1..n]$询问的结果插入$\text{multiset}$，再把$s[2..n]$询问的结果从$\text{multiset}$中删掉，那么最后剩下来的$n$个字符串就是我们需要的结果。依此可以复原出原串。
code:
```cpp
#include <bits/stdc++.h>
#define _ 0
using namespace std;
string s;
multiset<string> st;
string ss[110];
char ans[1000];
bool cmp(string s1,string s2)
{
return s1.size()<s2.size();
}
int buc[1100];
int main()
{
int n;
cin>>n;
if (n==1)
{
cout<<"? "<<1<<' '<<1<<'\n';
fflush(stdout);
char c;
cin>>c;
cout<<"! "<<c;
fflush(stdout);
return 0;
}
cout<<"? "<<1<<' '<<n<<'\n';
fflush(stdout);
for (int i=0;i<n*(n+1)/2;i++)
{
cin>>s;
sort(s.begin(),s.end());
st.insert(s);
}
cout<<"? "<<2<<' '<<n<<'\n';
fflush(stdout);
for (int i=0;i<n*(n-1)/2;i++)
{
cin>>s;
sort(s.begin(),s.end());
st.erase(st.find(s));
}
int cnt=0;
for (auto p:st)
{
ss[cnt++]=p;
}
sort(ss,ss+cnt,cmp);
ans[0]=ss[0][0];
for (int i=1;i<cnt;i++)
{
for (auto p:ss[i-1])
buc[p]--;
for (auto p:ss[i])
buc[p]++;
for (int j=0;j<255;j++)
if (buc[j]>0)
{
buc[j]=0;
ans[i]=j;
}
}
cout<<"! "<<ans;
fflush(stdout);
return ~~(0^_^0);
}
```