普及23题解
A
读入的时候遍历检查一遍，看有多少个字符 .
B
暴力模拟即可。即 从第
项到第
项，每次
。就可求出
。复杂度
。
C
考虑倒推。如果当前最后一步向右走那么就相当于把这个字符插入到最前面，如果是向左走就相当于插入到最后面。直接用一个 维护一下即可。
D
考虑按照 从小往大排序，考虑
表示前
个数，第
个数必须选最多能选多少个。转移为：
考虑如何优化转移，我们维护表示：
那么，
考虑 和
都可以在
的时间内求得。
考虑 。
所以时间复杂度是 的。
