P9087 「SvR-2」音符
MarchKid_Joe
·
·
题解
P9087 「SvR-2」音符
题意
构造题目。定义 \text{XX} 为两个连续的相同字符。
有两种代价：
- 每个 \text{XX} 产生 a 的代价。
- 长度为 k 的子串没有出现 \text{XX} 产生 b 的代价。
构造一个字符串使得总代价最小。
Solution
考虑 \text{XX} 的影响：造成 a 的代价；在不越界的情况下可以被 k-1 个子串所包含，消除 (k-1)\times{b} 的代价。
特判 k=2 的情况，此时发现字符串只有可能为全是相同字符的字符串或不存在 \text{XX} 的字符串。因为如果是两个混合的话，贡献为 c_1\times{a}+c_2\times{b},[c_1+c_2=n-1]，显然不如 (n-1)\times\min(a,b) 更优。
根据上面的分析：可以不使用 \text{XX} 的判断依据是：
{a}\geqslant{b}\times(k-1)
此时直接随意输出一个不存在 \text{XX} 的字符串即可，贡献为 b\times(n-k+1)。
否则构造含有 \text{XX} 的字符串：
当 $l,r\in[1,n]$ 时，在 $m,m-1$ 的位置放置 $\text{XX}$，即 ${a}\times{cnt}$。
当 ${r}\gt{n}$ 时，继续在 $m,m-1$ 的位置放置 $\text{XX}$ 或者计算 $n-m+1$ 个剩余字串的代价，即 $\min\{a,b\times(n-m+1)\}$。
## Example
如果不能理解的话，举个例子。假设 $n=15,k=5$。
观察一个 $\text{XX}$ （红色部分 $[4,5]$）在**不越界**时可以影响的 $k-1$ 个子串（蓝色部分 $[1,8]$）：
发现 $[5,9]$ 这个子串的 $b$ 的代价无法被 $[4,5]$ 消除。若要继续消除 $b$ ，需要每隔 $k-1$ 个位置再放置一个 $\text{XX}$。
按照上面的构造方案，若在 $[12,13]$ 放一个 $\text{XX}$ 会溢出 $[16,16]$，这样可能会浪费。此时便有两种选择：继续花费 $a$ 的代价放置 $\text{XX}$ 或者直接计算剩余子串 $b$ 的代价。
此时剩余无法覆盖的子串（图中黄线）的数量为 $n-m+1$ 个，花费 $a$ 的代价放置 $\text{XX}$ （图中红虚线）或者花费 $b\times(n-m+1)$ 的代价，两者取代价最小的。
## Code
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
char s[N];
char name[10] = "Nahida"; /*随机定义一个不含有 XX 的字符串即可*/
char same[10] = "AC"; /*选择两个字符是因为 k=3 时这种构造方案会出现 XXXX 的情况，改为 XXYY 即可*/
int T, n, k, a, b;
signed main()
{
cin >> T;
while (T --> 0)
{
int ans = 0, cnt = 0, m = 0;
cin >> n >> k >> a >> b; s[n + 1] = '\0';
for (int i = 1; i <= n; i++) s[i] = (k == 2 && a < b) ? 'Q' : name[(i - 1) % 6];
if (k == 2) {ans = (n - 1) * min(a, b);goto print;}
if (a >= (k - 1) * b) {ans = b * (n - k + 1);goto print;}
for (int l = 1, r; m = l + k - 1, (r = m + k - 2) <= n; l = m)
s[m] = s[m - 1] = same[(++cnt) & 1];
if (a < (n - m + 1) * b)
s[m] = s[m - 1] = same[(++cnt) & 1];
else
ans = (n - m + 1) * b;
print: cout << max(ans + a * cnt, 0ll) << '\n' << (s + 1) << '\n';
}
return 0;
}
```