贪心+构造，1924A - Did We Get Everything Covered?
目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
| 1924A - Did We Get Everything Covered? |
二、解题报告
1、思路分析
我们从头遍历s，用集合st代表出现的前k个小写字母的字符集
如果 st 在某个位置变成全集，说明长度为1的序列是ok的
我们将st清空，接着遍历
st 又在某个位置变成全集，说明长度为2的序列是ok的
……
那么如何输出非法方案？
我们依次将每个全集时刻加入st的字符保存，然后再加上一个非法时不在st中的任意字符即可
2、复杂度
时间复杂度： O(N)空间复杂度：O(N)
3、代码详解
import sys
import math
import heapq
from collections import defaultdict, Counter
from string import ascii_lowercaseinput = lambda: sys.stdin.readline().strip()
output = lambda x: sys.stdout.write(str(x) + '\n')
MII = lambda: map(int, input().split())
LMI = lambda: list(map(int, input().split()))
LI = lambda: list(input())
II = lambda: int(input())
I = lambda: input()
fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y# sys.stdin = open('in.txt', 'r')def solve():n, k, m = LMI()s = I()st = 0full = (1 << k) - 1ans = ''for x in s:if ord(x) - ord('a') < k:st |= 1 << (ord(x) - ord('a'))if st == full:st = 0ans += xif len(ans) < n:print('NO')for i in range(k):if ((st >> i) & 1) == 0:ans += str(chr(ord('a') + i)) * (n - len(ans))breakprint(ans)else:print('YES') passif __name__ == "__main__":T = 1T = II()for _ in range(T):solve()