F. Smaller - 题解
比赛与标签
比赛: Codeforces Round 827 (Div. 4) 标签: constructive algorithms, greedy, strings 难度: *1500
题目大意喵~？
你好呀，未来的算法大师！这道题是这样的呐：
我们有两个字符串 s 和 t，一开始它们都只有一个字符 'a'。接下来会有一系列的 q 次操作。操作有两种：
1 k x：把字符串x重复k次，然后拼接到字符串s的末尾。2 k x：把字符串x重复k次，然后拼接到字符串t的末尾。
每次操作之后，我们都要判断一下：我们能不能通过重新排列 s 和 t 各自内部的字符，使得 s 的字典序严格小于 t 呢？
注意哦，每次操作都是永久性的，会改变 s 和 t 的状态的说。
猫娘的贪心小爪子！
看到“重新排列字符”这种字眼，我们的猫猫雷达就该响起来啦！这意味着字符串里字符的顺序不重要，重要的是我们拥有哪些字符以及它们的数量，对吧？
为了让 s 尽可能地小，我们应该怎么排列它的字符呢？当然是把最小的字符放在最前面，也就是升序排列啦！比如 s 的字符是 {'c', 'a', 'b'}，那排列成的 s' 就是 "abc"，这是它能变成的最小字典序的字符串。
反过来，为了让 t 尽可能地大，我们就应该把最大的字符放在最前面，也就是降序排列！如果 t 的字符也是 {'c', 'a', 'b'}，那排列成的 t' 就是 "cba"，这是它能变成的最大字典序的字符串。
所以，问题就转化成：每次操作后，把 s 的字符升序排列得到的 s'，和把 t 的字符降序排列得到的 t'，s' 是否能严格小于 t' 呢？
让我们来分析一下 s' < t' 的条件吧，喵~
情况一：最简单的情况！
s' 的第一个字符一定是 s 中最小的那个字符。t' 的第一个字符一定是 t 中最大的那个字符。
s 和 t 一开始都是 "a"，所以 s 里面永远都至少有一个 'a' 字符。这意味着，s 中最小的字符永远都是 'a'！所以 s' 永远以 'a' 开头。
那么，如果 t 中出现了任何一个比 'a' 大的字符（比如 'b', 'c', ...），我们就可以把这个最大的字符放到 t' 的开头。s' 以 'a' 开头，t' 以一个比 'a' 大的字符开头，那 s' 肯定比 t' 小呀！
结论 1: 只要
t字符串中包含任何一个大于 'a' 的字符，答案就是 YES！
情况二：有点棘手的情况
如果 t 中只含有 'a' 这个字符呢？那么 t' 就只能是 "aaaa..." 这样一长串 'a'。
现在 s' 要和 "aaaa..." 比较，s' 还有机会更小吗？
子情况 2a: 如果
s中也出现了比 'a' 大的字符（比如 'b'），那么s'排列出来就会是 "aaaa...b..." 的形式。和t'的 "aaaa..." 相比，s'在某个位置出现了 'b'，而t'对应位置还是 'a'，所以s'反而更大了！这样就不可能让s比t小了。结论 2: 如果
t只包含 'a'，但s包含大于 'a' 的字符，答案就是 NO。子情况 2b: 这是最后的决战了！
s和t都只包含 'a' 字符。 那么s'就是len_s个 'a' 组成的字符串，t'就是len_t个 'a' 组成的字符串。根据字典序的定义，两个由相同字符组成的字符串，短的那个更小。结论 3: 如果
s和t都只包含 'a'，那么当且仅当s的长度len_s小于t的长度len_t时，答案是 YES，否则是 NO。
总结一下我们的策略喵
我们根本不需要真的去存储和操作那两个可能变得超级长的字符串！我们只需要维护几个关键信息：
s的长度len_s。t的长度len_t。s中是否包含大于 'a' 的字符（一个布尔值has_larger_s就够了）。t中是否包含大于 'a' 的字符（或者直接记录t中的最大字符max_t）。
每次操作后，我们就按下面的逻辑判断：
- 检查
t中是否有大于 'a' 的字符 (即max_t > 'a')？- 有 -> YES
- 如果没有 (即
max_t == 'a')：- 检查
s中是否有大于 'a' 的字符 (即has_larger_s为真)？- 有 -> NO
- 如果没有 (即
s也只含 'a')：- 检查
len_s < len_t？- 是 -> YES
- 否 -> NO
- 检查
- 检查
这样一来，问题是不是就变得非常清晰简单了呀？喵~
看我敲代码喵！
#include <iostream>
#include <algorithm>
#include <string> // 引入 string 头文件是个好习惯哦
using namespace std;
// 主函数，一切魔法的开始！
int main() {
// 加速输入输出，让程序跑得飞快，喵~
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
int q;
cin >> q;
// 初始化 s 和 t 的状态
long long len_s = 1, len_t = 1; // 初始长度都是 1 ("a")
// s 中最小的字符，因为初始是 "a"，所以永远是 'a'
// char min_s = 'a';
// t 中最大的字符，初始是 'a'
char max_t = 'a';
// s 中是否包含过大于 'a' 的字符？初始为 false
bool has_larger_s = false;
for (int i = 0; i < q; i++) {
int d, k;
string x;
cin >> d >> k >> x;
if (d == 1) { // 操作 s
len_s += (long long)k * x.size();
// 检查新加入的字符串 x 是否有比 'a' 大的字符
for (char c : x) {
if (c > 'a') {
has_larger_s = true;
}
}
} else if (d == 2) { // 操作 t
len_t += (long long)k * x.size();
// 检查新加入的字符串 x，并更新 t 的最大字符
for (char c : x) {
if (c > max_t) {
max_t = c;
}
}
}
// --- 开始根据我们的策略进行判断 ---
// 情况 1: t 中有比 'a' 大的字符
if (max_t > 'a') {
cout << "YES\n";
}
// 情况 2: t 中只有 'a'
else {
// 子情况 2a: s 中有比 'a' 大的字符
if (has_larger_s) {
cout << "NO\n";
}
// 子情况 2b: s 中也只有 'a'
else {
if (len_s < len_t) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
}
}
return 0;
}小声说：我稍微简化了一下AC代码里的逻辑，让它和我们的思路更贴合，但本质是一样的哦！原来的代码里min_s和has_larger_s的判断稍微有点绕，但因为s里永远有'a'，所以效果是一样的。
跑得快不快呀？
- 时间复杂度: O(Σ|x|) 的说。对于每个测试用例，我们处理
q个查询。在每个查询中，我们遍历一次输入的字符串x来更新我们的状态。所以总的时间消耗主要在于读取并处理所有x字符串，总复杂度就是所有x长度的总和。这完全可以接受！ - 空间复杂度: O(1) 的说。我们没有存储那两个可能很长的字符串
s和t，只是用了几个变量（len_s,len_t,max_t,has_larger_s）来记录状态。所以每个测试用例只需要常数级别的额外空间，非常节省内存！
这次学到了什么喵？
这道题真是太棒了，它教会了我们：
- 贪心思想: 面对一个需要构造最优解的问题，先思考如何让一方达到“最有利”状态，另一方达到“最不利”状态，然后比较这两个极端情况。这就是贪心的魅力！
- 问题简化: “重新排列”是一个强烈的信号，它告诉我们可以忽略顺序，从字符集合的角度去思考问题。成功地将复杂问题简化为几个关键状态的判断，是解题的核心技巧。
- 状态压缩: 不要被题目中可能变得巨大的数据（超长字符串）吓到！很多时候，我们并不需要存储所有数据，只需要维护一些能做出决策的关键信息（状态）即可。
希望这篇题解能帮到你，如果还有不懂的地方，随时可以再来问我哦！一起加油，变得更强吧，喵~！