贪心+构造，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()