洛谷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;
}