题目链接:http://codeforces.com/contest/1092/problem/C
题意是有一个长度为n的字符串(并没有给出),然后给出了2*n-2个这个字符串的前缀和后缀子串,也就是长度为1的有两个,分别是字符串的前缀和后缀,长度为2的也有两个,也是一个为前缀一个为后缀,直到n-1的长度的前后缀子串,然后让判断当前子串是前缀还是后缀,要注意的是abc的长度为2的后缀是bc不是cb。
思维就是暴力去模拟,我先对这些子串进行了从大到小排序,然后假设了一种情况,让两个长度为n-1的子串一个是前缀一个是后缀,然后对其他字符串进行判断(此时会有四种情况),如果在判断的情况中出现了冲突,那就表明最开始的假设的情况是错的,然后我们调整假设的情况再继续判断就好了。我这种做法应该很麻烦,也有人用dfs去写的,不知道怎么实现的...
AC代码:
#include <bits/stdc++.h>
using namespace std;
int n;
struct Node{
string str;
int len, id;
string str1;
}Edge[2005];
bool cmp(Node a,Node b){
return a.len > b.len;
}
bool cmp1(Node a,Node b){
return a.id < b.id;
}
int main()
{
scanf("%d",&n);
n = 2 * n - 2;
for(int i=0;i<n;i++){
cin>>Edge[i].str;
Edge[i].id = i;
Edge[i].len = Edge[i].str.length();
}
sort(Edge, Edge + n, cmp);
Edge[0].str1 = "S";
Edge[1].str1 = "P";
bool flag = true;
for(int i=2;i<n;i+=2){
bool flag1 = true, flag2 = true, flag3 = true, flag4 = true;
for(int j=0;j<Edge[i].len;j++){
if(Edge[1].str[j] != Edge[i].str[j]){
flag1 = false;
break;
}
}
for(int j=Edge[i].len-1,k=Edge[0].len-1;j>=0;j--,k--){
if(Edge[0].str[k] != Edge[i].str[j]){
flag2 = false;
break;
}
}
for(int j=0;j<Edge[i+1].len;j++){
if(Edge[1].str[j] != Edge[i+1].str[j]){
flag3 = false;
break;
}
}
for(int j=Edge[i+1].len-1,k=Edge[0].len-1;j>=0;j--,k--){
if(Edge[0].str[k] != Edge[i+1].str[j]){
flag4 = false;
break;
}
}
if(flag1 && flag2 && flag3 && flag4){
Edge[i].str1 = "S";
Edge[i+1].str1 = "P";
}
else if(flag1 && !flag2 && !flag3 && flag4){
Edge[i].str1 = "P";
Edge[i+1].str1 = "S";
}
else if(!flag1 && flag2 && flag3 && !flag4){
Edge[i].str1 = "S";
Edge[i+1].str1 = "P";
}
else{
flag = false;
break;
}
}
if(flag == false){
Edge[0].str1 = "P";
Edge[1].str1 = "S";
for(int i=2;i<n;i+=2){
bool flag1 = true, flag2 = true, flag3 = true, flag4 = true;
for(int j=0;j<Edge[i].len;j++){
if(Edge[0].str[j] != Edge[i].str[j]){
flag1 = false;
break;
}
}
for(int j=Edge[i].len-1,k=Edge[1].len-1;j>=0;j--,k--){
if(Edge[1].str[k] != Edge[i].str[j]){
flag2 = false;
break;
}
}
for(int j=0;j<Edge[i+1].len;j++){
if(Edge[0].str[j] != Edge[i+1].str[j]){
flag3 = false;
break;
}
}
for(int j=Edge[i+1].len-1,k=Edge[1].len-1;j>=0;j--,k--){
if(Edge[1].str[k] != Edge[i+1].str[j]){
flag4 = false;
break;
}
}
if(flag1 && flag2 && flag3 && flag4){
Edge[i].str1 = "S";
Edge[i+1].str1 = "P";
}
else if(flag1 && !flag2 && !flag3 && flag4){
Edge[i].str1 = "P";
Edge[i+1].str1 = "S";
}
else if(!flag1 && flag2 && flag3 && !flag4){
Edge[i].str1 = "S";
Edge[i+1].str1 = "P";
}
else{
flag = false;
break;
}
}
}
// for(int i=0;i<n;i++){
// cout<<Edge[i].str1;
// }
sort(Edge, Edge + n, cmp1);
for(int i=0;i<n;i++){
cout<<Edge[i].str1;
}
return 0;
}