Codeforces K. Similarity (Hard Version)题解

题目简述

给定 (n,m,k)，构造 (n) 个长度为 (k) 的互异小写字符串，使得所有对的最长公共子串长度的最大值 恰好等于 (m)。输出 Yes 并给出字符串，若无解输出 No。

解题关键

• 若 (m\ge k)，必有相同串 → 无解。
• 若 (m=0)，需所有字符互异 → 需要 (n\le 26)。
• 若 (0<m<k)，可用如下构造：

构造方法

1. 每个串前 (m-1) 位固定为 'z'。
2. 剩余 (k-m+1) 位用交替字母 c1 c2 c1 c2 ... 填充。
3. 初始 c1='a', c2='a'。每生成一个串后，若 c2<'z' 则 c2++，否则 c1++, c2=c1。

这样任意两串公共子串长度 ≤ (m)，且存在长度为 (m) 的对（相邻串可能在第 (m) 位相同）。

代码

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int N = 2e5 + 10, mod = 998244353, inf = LLONG_MAX;
ll n, m, x, k, c, d, tmp;
void solve() {cin >> n >> m >> k;if (m >= k || (m == 0 && n > 26)) {//先判断无解cout << "No" << '\n';return;}cout << "Yes" << '\n';if (m == 0) {//m==0 我们只需要像这样输出aaaa bbbbfor (int i = 0; i < n; i++) {cout << string(k, 'a' + i) << '\n';}return;}char c1 = 'a', c2 = 'a';for (int i = 1; i <= n; i++) {for (int j = 0; j < m - 1; j++)//先输出m-1个zcout << 'z';for (int j = 1; j <= k - m + 1; j++) {//剩下像这样输出aaa aba aca.....bbb bcb 即交叉输出if (j % 2) {cout << c1;} else {cout << c2;}}if (c2 == 'z') {c1++;c2 = c1;} elsec2++;cout << '\n';}
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _ = 1;// cin >> _;while (_--) {solve();}return 0;
}