洛谷P9087 「SvR-2」音符题解

题意：

我们用一个字符串代替一份乐谱，用字符代替每一个音符。

我们定义「重音」表示乐谱中出现了两个连续的相同字符，如 $\tt eeeee$ 中存在 $4$ 个「重音」。

现在 Sept 准备写一份长度为 $n$ 的乐谱给 Tpes 看，他对乐谱的评价标准如下：

乐谱中每出现一个「重音」，他的愤怒值就会增加 $a$。

乐谱中每有一段长度为 $k$ 的子串中不存在「重音」，他的愤怒值就会增加 $b$。

现在已知 $n,k,a,b$，请你帮 Sept 构造出一份乐谱，使得 Tpes 的愤怒值 $x$ 最小。

输入格式:

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行两个整数 $n,k,a,b$，意义如题目所述。

输出格式

共 $2 \cdot T$ 行，对于每组数据都输出两行：

第 1 行表示 Tpes 最小的愤怒值 $x$。

第 2 行表示你构造出的乐谱。

数据范围：

$2\le T\le 100$，$2\le n,k\le 10^5$，$1\le a,b\le 10^9$。单组数据内保证 $\sum n\le 2\times 10^5$。

输出注意事项：

输出 $x$ 和构造乐谱可以看作是两个子问题，如果你只会完成其中的一个，请在另一个子问题对应的地方用符合要求的字符或数字占位。

乐谱中你可以输出任意字符，包括数字、大小写字母等，但不能出现空格。

勉强可以算一个简单构造题吧。

考虑一个 $\mathrm{XX}$ 放到字符串中至多可以拯救多少长为 $k$ 的区间。

根据经验，我们把每个 $\mathrm{XX}$ 相距 $k-2$ 放置，则一个 $\mathrm{XX}$ 刚好可以救下 $k-1$ 个区间。

那么如果我们不放的花费就是 $k-1\times b~(\le a)$ ，否则如果大于 $a$ 一定会放一个 $\mathrm{XX}$ 。

可以发现，这里的 $k-2$ 在 $k=2$ 时会有些不同，于是我们对其特判一下即可。

时间复杂度 $\mathcal{O}(\sum n_i)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

char s[N];
char c1[5] = "1234", c2[5] = "AB";
void solve()
{
    int n, k, a, b, res = 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) ? 'C' : c1[(i - 1) & 3];
    if(k == 2) { res = (n - 1) * min(a, b); goto print; }
    if(a >= (k - 1) * b) { res = 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] = c2[(++cnt) & 1]; }
    if(a < (n - m + 1) * b) { s[m] = s[m - 1] = c2[(++cnt) & 1]; } else res = (n - m + 1) * b;
    print: cout << max(res + a * cnt, 0ll) << '\n' << (s + 1) << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}