CF1560E Polycarp and String Transformation

发表于 分类于

思路

根据题意，操作序列的长度应该等于字符串$t$中不同字符的种数。

结合题目中每次删去$s$中所有的指定字符$c$的操作，不难发现如果正常操作，$s$在最后一次删除操作前只包含最后一次删除的字符，在倒数第二次删除操作前只包含删除序列中最后两种字符，以此类推……

由上述推断可知，操作序列的逆序列可以通过每次取最后一个字符并将该字符全部删去得出。在此记操作序列为$ans_1,ans_2,\dots,ans_n$，原序列$s$中字符$c$出现的次数为$cnt_c$。

根据操作的性质可知，对于字符$ans_i$，$t$中出现$ans_i$的次数应为$i\times cnt_{ans_i}$。由此可以反推出$cnt_i$，且可以通过累加得到$len(s)$。至此，取$t$的前$len(s)$个字符为$s$模拟操作过程检验即可。

《关于我在用Python写题之前按C的常数算复杂度觉得能过这件事》

TLE

代码

重写的C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
#define debug printf("%d %s\n",__LINE__,__FUNCTION__);fflush(stdout)
using ll=long long;using i64=long long;using db=double;
using u32=unsigned int;using u64=unsigned long long;using db=double;
using pii=pair<int,int>;using vi=vector<int>;
using qi=queue<int>;using pqi=priority_queue<int>;using si=set<int>;
#define pb push_back
#define mk make_pair
#define ins insert
#define era erase
#define fi first
#define se second
#define lowbit(x) x&-x
#define ALL(a) a.begin(),a.end()
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
template<class T>inline bool chkmin(T&a,T b){return b<a?a=b,true:false;}
template<class T>inline bool chkmax(T&a,T b){return a<b?a=b,true:false;}
int _w,_t;FILE* _f;
#define MULTI_CASES

const int N=5e5+5;
char s[N],t[N],ans[30],tmp[N];
bool vis[26];
int cnt[26],ls,lt,la,ltmp;

bool check(){
    ltmp=0;
    memset(vis,0,sizeof vis);
    for(int i=1;i<=la;i++){
        for(int j=1;j<=ls;j++){
            if(!vis[s[j]-'a']){
                tmp[++ltmp]=s[j];
            }
        }
        vis[ans[i]-'a']=1;
    }
    tmp[ltmp+1]=0;
    // printf("%s %s\n",t+1,tmp+1);
    return strcmp(t+1,tmp+1)==0;
}

void solve(){
    scanf("%s",t+1);
    ls=0;la=0;
    lt=(int)strlen(t+1);
    memset(vis,0,sizeof vis);
    memset(cnt,0,sizeof cnt);
    for(int i=lt;i>0;i--){
        if(!vis[t[i]-'a']){
            ans[++la]=t[i];
            vis[t[i]-'a']=1;
        }
        ++cnt[t[i]-'a'];
    }
    ans[la+1]=0;
    for(int i=1,j=la;i<j;i++,j--){
        swap(ans[i],ans[j]);
    }
    for(int i=1;i<=la;i++){
        if(cnt[ans[i]-'a']%i){
            printf("-1\n");return;
        }
        cnt[ans[i]-'a']/=i;
        ls+=cnt[ans[i]-'a'];
    }
    for(int i=1;i<=ls;i++){
        s[i]=t[i];
    }
    s[ls+1]=0;
    if(check()){
        printf("%s %s\n",s+1,ans+1);
    }
    else{
        printf("-1\n");
    }
}

int main(){
    #ifdef MULTI_CASES
    _w=scanf("%d",&_t);while(_t--)
    #endif
    solve();
    return 0;
}

比赛中T飞的Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def check(t,s,ans):
    tmp=''
    vis=dict()
    for c in ans:
        vis.setdefault(c,0)
    for c in ans:
        for cc in s:
            if vis[cc]==1:
                continue
            tmp+=cc
        vis[c]=1
    return tmp==t

_t=int(input())
for _c in range(_t):
    s=input()
    flag=1
    t,ans="",""
    dic=dict()
    for c in s:
        dic.setdefault(c,0)
        dic[c]+=1
    cntk=len(dic.keys())
    for c in s[::-1]:
        if ans.find(c)==-1:
            ans=ans+c
    ans=ans[::-1]
    nlen=0
    for i in range(len(ans)):
        c=ans[i]
        if dic[c]%(i+1)!=0:
            flag=0
            break
        nlen+=dic[c]//(i+1)
    if flag==0:
        print(-1)
        continue
    t=s[:nlen]
    if flag and check(s,t,ans):
        print(t,ans)
    else:
        print(-1)