Problem - D - Codeforces

不錯的字符串構造體，記錄一下

首先注意到k≤20這一條件。對于一個長度為n的字符串，最多有n個不同的回文子串，這種情況出現在所有字符都相同時。因此，限制條件中的xi必須滿足xi≤ci，且相鄰兩個限制條件的ci差值不能超過它們之間的長度（即xi差值）。

注意到k≤20的限制，最簡便的構造方法是：為每個限制條件構造一段連續相同的字符來滿足要求。可以保證字母使用數量不超過26個，多余的部分則可以用一段連續字符來填充。

假設僅有一個限制條件，例如要求構造長度為n且包含c種不同回文子串的字符串，可以采用n-2個'a'加上"xya"循環的方式滿足需求。

當后續增加更多限制條件時，若需新增ci種不同回文子串，只需在字符串中插入ci個字符'a'+i，最后接上"xya"循環節即可。

關鍵在于循環節的銜接策略。將"axy"視為一個環形結構，包含xya、yax、axy三種循環形式。記錄前一個循環節的末尾字符為las：當las為'a'時追加"xya"循環節；當las為'x'或'y'時做相應處理。這種構造方法能有效避免產生多余回文子串。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
#define pii pair<int, int>
#define lowbit(x) (x & (-x))void solve()
{int n, k;cin >> n >> k;vector<int> a(k + 1), b(k + 1);for (int i = 1; i <= k; i++)cin >> a[i];for (int i = 1; i <= k; i++)cin >> b[i];// 必須滿足 b[i] ≤ a[i]，增量不超長度差for (int i = 1; i <= k; i++){if (b[i] > a[i] || b[i] - b[i - 1] > a[i] - a[i - 1]){cout << "NO" << endl;return;}}// 構造第一個前綴：先填充 (b[1]-2) 個 'a'，新增 b[1] 個回文string res = string(b[1] - 2, 'a');// 用循環節 “xya” 填充到恰好長度 a[1]while (res.size() < a[1])res += "xya";while (res.size() > a[1])res.pop_back();// 記錄末尾字符，用于后續選擇合適的循環節char las = res.back();for (int i = 2; i <= k; i++){string t;// 根據上次末尾 las，選擇首尾都不和 las 沖突的循環節if (las == 'a')t = "xya";else if (las == 'x')t = "yax";else if (las == 'y')t = "axy";// 新增回文：插入 (b[i] - b[i-1]) 個新字符 c = 'a'+(i-1)char c = 'a' + (i - 1);res += string(b[i] - b[i - 1], c);// 循環節填充至長度 a[i]while (res.size() < a[i])res += t;while (res.size() > a[i])res.pop_back();// 僅當末尾是循環節字符時，才更新 lasif (res.back() == 'a' || res.back() == 'x' || res.back() == 'y')las = res.back();}// 輸出結果cout << "YES" << endl;cout << res << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--)solve();
}