https://codeforces.com/contest/1511/problem/D
题目大意
用少于 $k \ (1 \le k \le 26)$ 的字符集，构造一个 $n \ (\le 2 \times 10^5)$ 长的串。使得
$$ \sum_i \sum_{j = i + 1}^{n - 1} [s[i, i + 1] = s[j, j + 1]] $$尽量小。
简要题解
假设原串中每种 $2$ 长字符串 $ab$ 出现频率为 $c_{ab}$ 则题目实际上就是要求
$$ \sum c_{ab} * (c_{ab} - 1) / 2 = \sum c_{ab}^2 / 2 - \sum c_{ab} / 2 $$第二部分是个定值 $n - 1$，因此我们只需要最小化第一部分。根据均值不等式，显然我们希望每种串数量尽可能一致。于是想到，如果我们找到某个串可以恰好不重不漏的遍历每一种二元组，那么只要重复这个串就是最好结果（首尾连接的一组应该也要考虑进来）。
我们发现去掉重复的 aa，bb 这样的串后，原问题相当于找到一张 $k$ 个点的有向完全图上的欧拉回路。因为每个点的入度等于出度，且全图联通，这样欧拉回路是一定存在的。注意，因为最后一定会连回起点，但实际上我们想要连回起点是某一组的末尾和下一组的开始，因此需要把最后一个输出的点删掉。
那么怎么处理 aa，这样的串呢？因为生成的序列相邻的两项一定是不同的，我们只需在最终的结果中每次某个字符第一次出现和最后一次出现时把它重复即可。
复杂度
$T$：$O(n + k ^ 2)$
$S$：$O(n + k ^ 2)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
template<typename Func> struct YCombinatorResult {
Func func;
template<typename T>
explicit YCombinatorResult(T &&func) : func(std::forward<T>(func)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) {
return func(std::ref(*this), std::forward<Args>(args)...);
}
};
template<typename Func> decltype(auto) y_comb(Func &&fun) {
return YCombinatorResult<std::decay_t<Func>>(std::forward<Func>(fun));
}
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n, k; cin >> n >> k;
vector<vector<int>> g(k);
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
if (i == j) continue;
g[i].push_back(j);
}
}
vector<int> vis(k);
string ans;
y_comb([&](auto dfs, int u) -> void {
while (!g[u].empty()) {
int v = g[u].back(); g[u].pop_back();
dfs(v);
}
ans += ((char)(u + 'a'));
if (!vis[u]) {
vis[u] = 1;
ans += ((char)(u + 'a'));
}
})(0);
// cerr << ans << endl;
int m = ans.size() - 1;
for (int i = 0; i < n; i++) {
cout << ans[i % m];
}
cout << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] C. Yet Another Card Deck - Educational Codeforces Round 107 (Rated for Div. 2)