Codeforces Round #527 (Div. 3) C. Prefixes and Suffixes

时间:2021-12-10 04:09:46

题目链接

题意:给你一个长度n,还有2*n-2个字符串,长度相同的字符串一个数前缀一个是后缀,让你把每个串标一下是前缀还是后缀,输出任意解即可。

思路;因为不知道前缀还是后缀所以只能搜,但可以肯定的是长度为n-1的字符串一个是前缀一个是后缀,那么只要搜两次就完事了,一个当前缀不行就换另一个当前缀,然后中间判断一下即可。

ps:这也是给远古题,没补,因为最不喜欢 字符串的题,,,qwq。

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back using namespace std; LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
int n;
struct uzi
{
int i;
string a;
bool operator <(const uzi &t)const{
return a.size()>t.a.size();
}
}p[555];
char ans[555];
int dfs1(){
for(int i=3;i<=2*n-2;i+=2){
int bj=0;
if(p[1].a.find(p[i].a)==0){
string A=p[2].a,B=p[i+1].a;
reverse(A.begin(),A.end());
reverse(B.begin(),B.end());
if(A.find(B)==0){
ans[p[i].i]='P';
ans[p[i+1].i]='S';bj=1;}
}
if(p[1].a.find(p[i+1].a)==0){
string A=p[2].a,B=p[i].a;
reverse(A.begin(),A.end());
reverse(B.begin(),B.end());
if(A.find(B)==0){
ans[p[i].i]='S';
ans[p[i+1].i]='P';bj=1;}
}
if(!bj)return 0;
}
return 1;
}
int dfs2(){
for(int i=3;i<=2*n-2;i+=2){
int bj=0;
if(p[2].a.find(p[i].a)==0){
string A=p[1].a,B=p[i+1].a;
reverse(A.begin(),A.end());
reverse(B.begin(),B.end());
if(A.find(B)==0){
ans[p[i].i]='P';
ans[p[i+1].i]='S';bj=1;}
}
if(p[2].a.find(p[i+1].a)==0){
string A=p[1].a,B=p[i].a;
reverse(A.begin(),A.end());
reverse(B.begin(),B.end());
if(A.find(B)==0){
ans[p[i].i]='S';
ans[p[i+1].i]='P';bj=1;}
}
if(!bj)return 0;
}
return 1;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=2*n-2;i++){
cin>>p[i].a;
p[i].i=i;
}
sort(p+1,p+1+2*n-2);
if(dfs1()){
ans[p[1].i]='P';
ans[p[2].i]='S';
for(int i=1;i<=2*n-2;i++)cout<<ans[i];
return 0;
}
dfs2();
ans[p[2].i]='P';
ans[p[1].i]='S';
for(int i=1;i<=2*n-2;i++)cout<<ans[i];
return 0;
}