CF1560E 题解

きりと · 2021-08-20 15:01:19 · 题解

My Blog

题目大意

起初有一个小写字符串 s 和一个空串 t，现对 s 进行一些操作，每次操作会选择一个字母，并删除 s 中所有此字母，然后将 s' 加入 t 的末尾，直到 s 为空。

已知 t ，求原串 s 以及字母删除顺序，若无解输出 -1。

解题思路

先考虑怎么求删除顺序，首先可以确定的是，t 末尾最后一个字母一定是最后被删的，然后在此之上，发现从后往前，越早出现的字母一定越晚被删，直接拿个 map 啥的求一下删除顺序。

在知道删除顺序以后，可以发现，每一个在第 i 次操作被删掉的字母一定会被复读 i-1 次，也就是在 t 中出现 i 次，那我们直接预处理出每个字母在 t 中出现的次数 v[i]，然后按删除顺序遍历一遍字母，每个字母会在 s 中出现 \frac{v[i]}{i} 次，如果除不通那就无解，最后累加一下各个字母出现次数，记为 l，t 的前 l 个字符就可能是原串 s。

然后发现样例最后一个有问题，如果一些无解情况，换了顺序不换字母数量就会被搞，所以最后要再按题意模拟一遍看看和 t 是不是一样的。

赛时由于前一天熬夜打派，困得头昏脑涨，没想到 t 中前 l 个就是可能答案，在写 KMP，然后就因为调了太久，导致比赛结束约 30s 以后才写出来。

Code

#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define int long long
#define forr(i,l,r) for(register int i=l;i<=r;i++)
#define ffor(i,r,l) for(register int i=r;i>=l;i--)
using namespace std;
const int N=5e5+10;
int v[27];
int cc;
char ans[27];
int f[N];
string n;
signed main()
{
    int t;
    cin>>t;
    flag:while(t--)
    {
        memset(v,0,sizeof(v));
        forr(i,1,26)
        {
            ans[i]=' ';
        }
        cc=0;
        cin>>n;
        int l=n.size();
        if(l==1)
        {
            cout<<n<<" "<<n<<endl;
            continue;
        }
        n=' '+n;
        ffor(i,l,1)
        {
            if(!v[n[i]-'a'])
            {
                ans[++cc]=n[i];
            }
            v[n[i]-'a']++;
        }
        int ll=0,e,o;
        ffor(i,cc,1)
        {
            e=cc-i+1;
            o=v[ans[i]-'a'];
            if(o%e!=0)
            {
                puts("-1");
                goto flag;
            }
            ll+=o/e;
        }
        memset(v,0,sizeof(v));
        string q=" ",qq=" ";
        forr(i,1,ll)
        {
            q+=n[i];
            qq+=n[i];
        }
        ffor(i,cc,1)
        {
            v[ans[i]-'a']=1;
            forr(j,1,qq.size()-1)
            {
                if(!v[qq[j]-'a'])
                {
                    q+=qq[j];
                }
            }
        }
        if(q!=n)
        {
            puts("-1");
            continue;
        }
        forr(i,1,qq.size()-1)
        {
            cout<<qq[i];
        }
        cout<<" ";
        ffor(i,cc,1)
        {
            cout<<ans[i];
        }
        puts("");
    }
}