CodeForces-1092C 题解

发表于2023-07-21更新于2023-07-21

题目传送门

一道字符串题……

我们考虑还原字符串后再一个一个的判断。很显然，这个字符串是由一个长度为 n−1n-1 的前缀和后缀组成的。因此我们可以找到这 22 个长度为 nn 的字符串，然后枚举哪个是前缀，哪个是后缀。

值得注意的是，当你判断一个字符串为前缀时，如果后面出现了同样的字符串，你只能判断它为后缀。

Code

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
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n;
bool flag;
string s1, s2, t, ans1, ans2; // t 是还原串
string s[205];
map <string, bool> mp;
bool check1(string str) { // 判断这个字符串是否是还原串的前缀
    for (int i = 0; i < str.size(); i++) {
        if (t[i] != str[i]) return 0;
    }
    return 1;
}
bool check2(string str) { // 判断这个字符串是否是还原串的后缀
    int cnt = t.size() - 1;
    for (int i = str.size() - 1; i >= 0; i--) {
        if (t[cnt--] != str[i]) return 0;
    }
    return 1;
}
signed main() {
    ios :: sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= 2 * n - 2; i++) cin >> s[i];
    for (int i = 1; i <= 2 * n - 2; i++) {
        if (s[i].size() == n - 1 and flag) s2 = s[i];
        if (s[i].size() == n - 1 and !flag) {
            s1 = s[i];
            flag = 1;
        }
    } 
    flag = 0;
    t = s1;
    t += s2[s2.size() - 1];
    // 如果 s1 是前缀
    for (int i = 1; i <= 2 * n - 2; i++) {
        if (!check1(s[i]) and !check2(s[i])) flag = 1; // 当 s1 是前缀时不合法
        else {
            if (check1(s[i]) and mp.find(s[i]) == mp.end()) {
                ans1 += 'P';
                mp[s[i]] = 1;
            }
            else ans1 += 'S';
        }
    }
    t = s2;
    t += s1[s1.size() - 1];
    // 如果 s1 是后缀
    mp.clear();
    for (int i = 1; i <= 2 * n - 2; i++) {
        if (check1(s[i]) and mp.find(s[i]) == mp.end()) {
            ans2 += 'P';
            mp[s[i]] = 1;
        }
        else ans2 += 'S';
    }
    if (!flag) cout << ans1; 
    else cout << ans2;
    return 0;
}