+1学姐在线嘤嘤嘤
Description
众所周知，+1学姐人美心好又聪明，但就是没有男朋友，你说气不气。这也正常，成为她的男朋友必须要答对她的问题才行，你想接受挑战吗？今天，+1学姐给出的问题是：有一个长度为n的字符串，告诉你该字符串的n-1个前缀子字符串，和n-1个后缀子字符串，为了增加难度，+1学姐给出的顺序是乱的，她要让你回答这2*n-2 个字符串是前缀的还是后缀的，若该字符串为前缀的，回答‘P’，若为后缀的，回答‘S’。你想成为+1学姐的男朋友吗？那就A了这道题吧。例如：字符串abcd，前缀子字符串为:a, ab, abc 后缀子字符串为:d, cd, bcd.
Input
输入的第一行包含一个整数n（2<=n<=100）,原始字符串的长度。
接下来的2n-2行，每行有一个字符串，是原始字符串的前缀或后缀。
给出的每一个字符串的的长度都为1到n-1，保证每个长度的字符串有两个，且由小写字母组成，给出的顺序是任意的。
Output
输出一个长度为2n-2，且仅由字符‘P’和‘S’组成的字符串。按顺序输出，若给出的第k个字符串为前缀的，那么输出的字符串第k个应为'P'.答案保证唯一。
Sample Input 1
4cdabcabcddab
Sample Output 1
SPPSSP
Hint
样例中原始字符串为:abcd.前缀的：a, ab, abc后缀的：d, cd, bcd所以输出：SPPSSP
思路：先把首尾两个字母找出来，如何还原串，在find子串
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<algorithm> using namespace std;string s[205];int P[40],S[40],l[205];queue<char> q1,q2;bool vis[30];int main() {int n;scanf("%d",&n);for(int i=1; i<=2*n-2; i++) {cin>>s[i];l[i]=s[i].size();P[s[i][0]-'a']++;S[s[i][l[i]-1]-'a']++;}for(int i=0; i<26; i++) {if(P[i]>=n-1) q1.push('a'+i);if(S[i]>=n-1) q2.push('a'+i);}char a,b;if(q1.size()==1&&q2.size()>1) {a=q1.front();vis[a-'a']=true;while(!q2.empty()){char t=q2.front();q2.pop();if(!vis[t-'a']){b=t;break;}}}else if(q2.size()==1&&q1.size()>1) {b=q2.front();vis[b-'a']=true;while(!q1.empty()){char t=q1.front();q1.pop();if(!vis[t-'a']){a=t;break;}}}else{a=q1.front();b=q2.front();}string sss;for(int i=1;i<=2*n-2;i++){if(l[i]==n-1&&s[i][0]==a){sss=s[i]+b;break;}}for(int i=1;i<=2*n-2;i++){if(sss.find(s[i])==0)printf("P");elseprintf("S");}return 0;}
如果觉得《+1学姐嘤嘤嘤》对你有帮助，请点赞、收藏，并留下你的观点哦！
