题解 CF1286C1 【Madhouse (Easy version)】

Rhodoks · 2020-01-06 13:27:09 · 题解

Hard version link

题意：有一个字符串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:

#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);
}