1335b.md

题目地址(B. Construct the String)

https://codeforces.com/problemset/problem/1335/B

题目描述

You are given three positive integers 𝑛, 𝑎 and 𝑏. You have to construct a string 𝑠 of length 𝑛 consisting of lowercase Latin letters such that each substring of length 𝑎 has exactly 𝑏 distinct letters. It is guaranteed that the answer exists.

You have to answer 𝑡 independent test cases.

Recall that the substring 𝑠[𝑙…𝑟] is the string 𝑠𝑙,𝑠𝑙+1,…,𝑠𝑟 and its length is 𝑟−𝑙+1. In this problem you are only interested in substrings of length 𝑎.

Input
The first line of the input contains one integer 𝑡 (1≤𝑡≤2000) — the number of test cases. Then 𝑡 test cases follow.

The only line of a test case contains three space-separated integers 𝑛, 𝑎 and 𝑏 (1≤𝑎≤𝑛≤2000,1≤𝑏≤min(26,𝑎)), where 𝑛 is the length of the required string, 𝑎 is the length of a substring and 𝑏 is the required number of distinct letters in each substring of length 𝑎.

It is guaranteed that the sum of 𝑛 over all test cases does not exceed 2000 (∑𝑛≤2000).

Output
For each test case, print the answer — such a string 𝑠 of length 𝑛 consisting of lowercase Latin letters that each substring of length 𝑎 has exactly 𝑏 distinct letters. If there are multiple valid answers, print any of them. It is guaranteed that the answer exists.

Example
inputCopy
4
7 5 3
6 1 1
6 6 1
5 2 2
outputCopy
tleelte
qwerty
vvvvvv
abcde
Note
In the first test case of the example, consider all the substrings of length 5:

"tleel": it contains 3 distinct (unique) letters,
"leelt": it contains 3 distinct (unique) letters,
"eelte": it contains 3 distinct (unique) letters.

前置知识

• 构造

公司

• 暂无

思路

这是一道构造题，需要我们构建出满足条件的字符串。

由于题目确保有解。因此我们可以考虑先构建一个长度为 a 的全部相同的字符串。接下来，我们需要将其中 b - 1 个字符串变成其他互不相同的字符（也不能和原有字符相同），这样我们就构造出了第一个长度为 a 且有 b 个互不相同的字符。

然后利用类似滑动窗口的技巧，保持窗口大小为 a 不变。每次右侧窗口扩展一个字符，左侧窗口收缩一个字符。那么最简单的思路就是保证左侧收缩窗口的字符和右侧扩展窗口的字符串相同即可。不断重复直到构造完长度为 n 的字符串。

关键点

代码

• 语言支持：Python3

Python3 Code:

t = int(input())

for _ in range(t):
    n, a, b = map(int, input().split(" "))
    A = ["a"] * n
    for i in range(1, b):
        A[i] = chr(ord(A[i - 1]) + 1)
    for i in range(a, n):
        A[i] = A[i - a]
    print("".join(A))

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$