令 $T={\tt KUPC}$。从后往前贪心，维护当前选上的四种字符的数量。如果当前的字符是 $T_i$，当 $i=4$ 或者 $T_{i}$ 的数量小于 $T_{i+1}$ 的数量时我们就选上当前的字符。最后我们把选择的第 $i$ 个 K、U、P、C 分成一组。正确性可以用交换论证来证明。时间复杂度 $O(N)$。
QOJ.ac
QOJ
The 3rd Universal Cup Finals is coming! Join our Warm-up Game and Prediction Game and win the prizes! Learn more...
Discussion #1533 for Problem #17724. Make Many KUPC
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2026-04-15 16:05:57
Last updated: 2026-04-15 16:06:04
题解
Comments
No comments yet.