题目翻译

定义字符串的费用是 $(i,j)$ 的个数满足 $1\leq i\lt j\leq n,s_i=s_j,s_{i+1}=s_{j+1}$。

给定 $n\leq 2\times 10^5$ 和字符集大小 $k(k\leq 26)$，用字母表前 $k$ 个小写字母组成的长度为 $n$ 的字符串中，找任意一种费用最小的字符串。

题目思路

字符集大小为 $k$ 的长度为 $2$ 的本质不同的字符串有 $k^2$ 个。对于 $n\leq k^2+1$，我们都可以构造费用为 $0$ 的解。

我们对于 $n\leq k^2+1$ 的，构造一组找一下规律：$\tt{[a,ab,ac,ad][b,bc,bd][c,cd]a}$。

我们不是所有 $k^2$ 个字符串都能放进去，因为可能会导致两个小字符串首尾相接出现重复。

这个例子启发我们，每一组都形如上面，先放自己，然后依次遍历字符集填充，可以构造费用为 $0$ 的解。感性理解一下，我们这里例子保证了单个 $k^2+1$ 长度的费用为 $0$，我们重复几次就很平均，所以看上去是对的。

严格证明一下，设这 $k^2$ 个字符串的出现次数分别为 $a_1,a_2,\cdots a_{k^2}$，那么我们的费用是 $\sum\limits_{i=1}^{k^2} \binom{a_i}{2}=\sum\frac{a_i(a_i-1)}{2}=\sum\frac{a_i^2-a_i}{2}=\frac{\sum a_i^2-a_i}{2}=\frac{\sum a_i^2}{2}-\frac{\sum a_i}{2}=\frac{\sum a_i^2}{2}-\frac{n-1}{2}$。

要是的上面这个式子最小，即最小化 $\sum a_i^2$。你贪心考虑，这个式子最小就是 $a_i$ 全部均摊的情况。那么我们上面给的这个费用为 $0$ 的构造就很平均。所以重复若干次即可。

完整代码

#include <bits/stdc++.h>
using namespace std;
int n, k;
string s;
int main()
{
    cin >> n >> k;
    for (int i = 0; i < k; i++)
    {
        s += char(i + 'a');
        for (int j = i + 1; j < k; j++)
            s += char(i + 'a'), s += char(j + 'a');
    }
    for (int i = 0; i < n; i++)
        cout << s[i % s.size()];
    cout << endl;
    return 0;
}