一篇普通的题解

· · 题解

题面翻译

你有两个字符串 s 和 t，它们初始都为 a，你会对字符串进行 q 次操作两种类型的操作：
操作一：在 s 末尾添加字符串 k 恰好 x 次
操作二：在 t 末尾添加字符串 k 恰好 x 次
求每次操作之后，是否可以重新排列 s 和 t 的字符，使 s 字典序比 t 小，如果可以，则 cout<<"YES"; ，否则 cout<<"NO";。

知识点

字符串的字典序比较与正常的数字不同，它比较的主要是每一个字符的大小，只有当两个字符串较短部分完全相等时才会比较长度，而比较符号只会判断字符的大小，并不会比较长度所以长度需要单独判断。

题目做法

首先我们知道 a 是小写字母中最小的字符，所以我们可以发现，只要去维护 s 的开头为 a 就是最有机会成立的，同时我们也要维护 t 的开头不为 a 就可以使 s 的字典序比 t 小。当两者不能通过开头比较时，在比较全文或长度。

之后你提交代码就会发现超时了，那就再考虑剪枝，我们可以发现其实只要 t 的开头不是 a 并且比 s 小时那么之后一定是成立的。