前言
还是一道模拟题，说实话思路出的挺快的，但处理方式想了很久（最后参考了luogu题解）
https://codeforces.com/problemset/problem/2092/D
题意
给定的字符串s只包含L,I,T三种字母，进行一种操作：
- 找到
i满足s[i] != s[i - 1], 在s[i]之前插入另一个字母
判断能否进行若干次给定的操作将s转化为L,I,T数量相同的字符串。
思路
手搓几组样例可以发现只要有一处i使得s[i] != s[i - 1]，这个字符串就可以转化为符合题目要求的字符串，否则输出-1即可。
假设找到了这样的一个i，那么通过在i前插入'L' + 'T' + 'I' - s[i] - s[i - 1]，就可以得到一个字母互不相同的长度为3的字符串。
令a = s[i - 1], b = 'L' + 'T' + 'I' - s[i] - s[i - 1], c = s[i],通过题中给定的操作，我们可以得到：
- acb -> 对位置i进行操作；
- bac -> 对位置i+1操作。注意此时得到的字符串实际为abac，而我们只需要对bac进行操作，所以将i自增1；
我们可以判断a、b、c的数量后更新a、b、c的值，可以用map或简单的int数组存数量，用swap模拟插入操作，并在更新之后重复上一步的操作，直到cnt[a] == cnt[b] and cnt[a] == cnt[c]
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
| #include <bits/stdc++.h>
using namespace std;
int n;
string s;
int cnt[500 + 'A'];
int total = 'L' + 'T' + 'I';
void solve() {
cin >> n >> s;
bool nice = false;
cnt['I'] = cnt['L'] = cnt['T'] = 0;
for(int i = 0; i < n; ++i) {
cnt[s[i]]++;
if(i != n - 1 && s[i] != s[i + 1]) nice = true;
}
if(!nice) {
cout << -1 << endl;
return;
}
vector<int> ans;
for(int i = 1; i < n; ++i) {
if(s[i] == s[i - 1]) continue;
int a = s[i - 1], b = total - s[i - 1] - s[i], c = s[i];
cnt[b]++;
ans.push_back(i);
while(cnt[a] != cnt[b] || cnt[a] != cnt[c]) {
if(cnt[c] <= cnt[a]) {
ans.push_back(i);
cnt[c]++;
swap(b, c);
} else {
ans.push_back(i + 1);
i++;
cnt[a]++;
swap(a, b);
}
}
break;
}
cout << ans.size() << endl;
for(int i = 0; i < ans.size(); ++i) cout << ans[i] << " \n"[i == ans.size() - 1];
}
int main() {
int t; cin >> t;
while(t--) {
solve();
}
return 0;
}
|
后记
说实话在AC掉之后讲述做法其实挺简单的，但自己在做题时碰壁挺多的。主要是维护更新后的字符串，我之前想要用insert修改字符串，每次遍历整个字符串，但是写起来代码太丑。
在换了写法之后，也有一些细节，比如i加1减1，或者是操作之间的一些顺序，又或者是cnt数组的清零。
感觉我还是需要继续练习模拟的（好痛苦，我并不想这么做q_q）
