CodeForces-946C 题解

发表于2023-03-27更新于2023-04-03

题目传送门

看到各位大佬都在发题解，我也来水一篇。

关于这道题，我们首先要理解一下题目……

该子序列可以通过删除掉变换后的 ss 中的某些字母得到。

从这句话中可以知道，变换后的字符串 ss 只需要包含 a∼za\thicksim z 即可，并不需要为连续子序列。

我们可以定义一个字符变量，初始值为 aa，代表进度（下一个满足要求的 sis_i 会变换成进度）。然后遍历一遍字符串 ss，如果 sis_i 小于进度，说明满足要求，可以转变，记得进度也要增加，其他的则不能。而如果当前进度已经大于 zz，说明字符串 ss 已经包含 a∼za\thicksim z，那么此时可以直接跳出循环。

最后我们判断一下，如果进度小于等于 zz，证明并没有跳出循环，字符串 ss 不满足要求，输出 -1。否则，代表字符串 ss 满足要求，直接输出 ss 即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define int long long
using namespace std;
string s;
char c = 'a';
signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (c > 'z') break;
        if (s[i] <= c) {
            s[i] = c;
            c++;
        }
    }
    if (c <= 'z') cout << -1;
    else cout << s;
    return 0;
}