Codeforces 杂题集（其三）

 

记录一些没有写在其他随笔中的 Codeforces 杂题, 以 Problemset 题号排序

 

1092C - Prefixes and Suffixes(1700, strings)
给定一个未知字符串被打乱顺序的所有真前缀和真后缀（长度从 \(1\) 到 \(n-1\)），要求将每个输入的子串正确分类为前缀（'P'）或后缀（'S'）。

题解

关键是判断长度是 \(n-1\) 的两个真前缀或真后缀到底谁是真前缀/真后缀，这样就知道整个串的内容了

view code

#include <bits/stdc++.h>
using namespace std;using ll = long long;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<string> v(2 * n - 2);string s1, s2;for (int i = 0; i < 2 * n - 2; i++) {cin >> v[i];if (v[i].size() == n - 1) {if (s1.empty()) {s1 = s2 = v[i];} else {s1 += v[i].back();s2 = v[i][0] + s2;}}}auto solve = [&](string s) {string ans;vector<int> vis(n);for (auto a : v) {int len = a.size();if (!vis[len] && s.substr(0, len) == a) {ans += 'P';vis[len] = 1;} else if (s.substr(n - len, len) == a) {ans += 'S';} else {return ""s;}}return ans;};string ans1 = solve(s1);if (ans1.size()) {cout << ans1 << '\n';} else {cout << solve(s2) << '\n';}
}