「SvR-2」音符

题目描述

本题中「子串」指：

若字符串 $ss$ 中有一段连续的字符构成字符串 $pp$，则 $pp$ 是 $ss$ 的子串。

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

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

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

• 乐谱中每出现一个「重音」，他的愤怒值就会增加 $aa$。
• 乐谱中每有一段长度为 $kk$ 的子串中不存在「重音」，他的愤怒值就会增加 $bb$。

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

输入格式

本题有多组数据。

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

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

输出格式

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

• 第 1 行表示 Tpes 最小的愤怒值 $xx$。
• 第 2 行表示你构造出的乐谱。

样例 #1

样例输入 #1

2
4 5 2 2
8 6 3 2

样例输出 #1

0
Sept
3
2023yyds

提示

数据规模与约定

本题采用捆绑测试。

对于 $100\mathrm{\%}100\backslash \%$ 的数据，有 $2\le T\le 1002\backslash le\; T\backslash le\; 100$，$2\le n,k\le 10^{5}2\backslash le\; n,k\backslash le\; 10^5$，$1\le a,b\le 10^{9}1\backslash le\; a,b\backslash le\; 10^9$。单组数据内保证 $\sum n\le 2\times 10^5\backslash sum\; n\backslash le\; 2\backslash times\; 10^5$。

输出注意事项

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

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

Special Judge 返回信息说明

本题采用 Special Judge 判断你的答案是否正确。

checker.cpp 将会以 $\mathtt{\text{Score=A, Type=B}}\backslash verb!Score=A,\; Type=B!$ 的方式返回信息。

$\mathtt{S}\mathtt{c}\mathtt{o}\mathtt{r}\mathtt{e}\backslash tt\; Score$ 类表示你的得分情况，$\text{A}\backslash text\; A$ 有以下取值：

• $\text{A}=1\backslash text\; A=1$，表示含义如下：
  $\underset{‾}{\text{Accepted.}}\mathtt{\text{ Your Ans and SM are both proper.}}\backslash underline\backslash text\{Accepted.\}\; \backslash verb!\; Your\; Ans\; and\; SM\; are\; both\; proper.!$
  代表 $TT$ 组答案全部符合要求。
• $\text{A}=2\backslash text\; A=2$，表示含义如下：
  $\underset{‾}{\text{Partially Correct.}}\mathtt{\text{ All Ans are right.}}\backslash underline\backslash text\{Partially\; Correct.\}\backslash verb!\; All\; Ans\; are\; right.!$
  表示该测试点中你的回答中 $xx$ 全部正确，你能得到该测试点 $20\mathrm{\%}20\backslash \%$ 的分数。
• $\text{A}=3\backslash text\; A=3$，表示含义如下：
  $\underset{‾}{\text{Partially Correct.}}\mathtt{\text{ You pass 70\% tests}}!\backslash underline\backslash text\{Partially\; Correct.\}\backslash verb!\; You\; pass\; 70\%\; tests!!$
  表示该测试点中你的回答正确的组数不少于$\lfloor 0.7\times T\rfloor \backslash lfloor0.7\backslash times\; T\backslash rfloor$（$xx$ 与乐谱均符合要求），你能得到该测试点 $10\mathrm{\%}10\backslash \%$ 的分数。
• $\text{A}=4\backslash text\; A=4$，表示该测试点你只能拿到 $00$ 分。

$\mathtt{T}\mathtt{y}\mathtt{p}\mathtt{e}\backslash tt\; Type$ 类表示你的得分情况，$\text{B}\backslash text\; B$ 有以下取值：

• $\text{B}=0\backslash text\; B=0$，表示你的答案全部正确，与 $\text{A}=1\backslash text\; A=1$ 配对。
• $\text{B}=1\backslash text\; B=1$，表示含义如下：
  $\underset{‾}{\text{Wrong Answer.}}\mathtt{\text{ The length of your SM is not right}}!\backslash underline\backslash text\{Wrong\; Answer.\}\backslash verb!\; The\; length\; of\; your\; SM\; is\; not\; right!!$
  代表你在一组数据中构造的乐谱的长度不为 $nn$。
• $\text{B}=2\backslash text\; B=2$，表示含义如下：
  $\underset{‾}{\text{Wrong Answer.}}\mathtt{\text{ Your Ans is not right}}!\backslash underline\backslash text\{Wrong\; Answer.\}\backslash verb!\; Your\; Ans\; is\; not\; right!!$
  代表你在一组数据中 $xx$ 的值错误。
• $\text{B}=3\backslash text\; B=3$，表示含义如下：
  $\underset{‾}{\text{Wrong Answer.}}\mathtt{\text{ Your Ans and SM are not matched}}!\backslash underline\backslash text\{Wrong\; Answer.\}\backslash verb!\; Your\; Ans\; and\; SM\; are\; not\; matched!!$
  代表你在一组数据中构造的乐谱使 Tpes 产生的愤怒值不为 $xx$。

注意到 $\text{Ans, SM}\backslash text\{Ans,\; SM\}$ 分别表示 Answer（$xx$ 的值）和 Sheet Music（乐谱）。

注意到 $\mathtt{T}\mathtt{y}\mathtt{p}\mathtt{e}\backslash tt\; Type$ 只会反映你在该测试点中第一次错误的类型。

题解：

复杂度分析：o（n）

定义dp[i][0/1]为考虑到第i个位置，该位置与上一个位置一样/不一样的最小愤怒值

显然dp[i][0]=min(dp[i-1][0],dp[i-1][1])+a;

对于dp[i][1]，考虑两种情况:

一：当i-k+2<=j<=i-1时,dp[i][1]=min（dp[j][0]）

且对于dp的任意一个维度，dp的值是严格非减的，因为加上任何字符都不会让愤怒值减小

所以仅考虑j=i-k+2的情况就可

二:当j<i-k+2时,dp[i][1]=min（dp[j][0]+b*(i-j-k+2)）=min(dp[j][0]+b*j)-(i-k+2)*b;

所以可以维护一个minn为当j<i-k+2时dp[j][0]+b*j的前缀最小值

dp[i][1]=minn-(i-k+2)*b;

#include<stdio.h>
#include<stdlib.h>
#include<algorithm> 
#include<string.h>
#include<iostream>
#include<queue>
#include<math.h>
#include<string>
#include<map>
#include<functional>

#define inf 0x3f3f3f3f3f3f3f3f

using namespace std;
#define int long long
int T, n, k, a, b;

#define N 100005

//0代表和上一位一样，1代表和上一位不一样
int dp[N][2];//表示考虑到第i个位置，是否从这个位置出现一个重音的最小愤怒值



//path[i][j][0/1]记录dp[i][j]是由dp[path[i][j][0]][path[i][j][1]]转移而来的
int path[N][2][2];

int ans[N];


signed main(void)
{
	cin >> T;

	while (T--)
	{
		cin >> n >> k >> a >> b;

		memset(dp, 0x3f, sizeof(dp));
		memset(path, 0, sizeof(path));
		memset(ans, 0, sizeof(ans));

		dp[1][0] = dp[1][1] = 0;
		int minn = 0x3f3f3f3f3f3f3f3f, p = -1;

		for (int i = 2; i <= n; i++)
		{
			dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + a;
			path[i][0][0] = i - 1;
			if (dp[i - 1][0] > dp[i - 1][1])
			{
				path[i][0][1] = 1;
			}
			else
			{
				path[i][0][1] = 0;
			}

			int pp = max(1ll, i + 2 - k);//在不用出b的时候转移

			if (i + 2 - k > 1)
			{
				if (dp[i - k + 2-1][0] - b*(i - k + 2-1) < minn)
				{
					minn = dp[i - k + 2-1][0] - b*(i - k + 2-1);

					p = i - k + 2-1;
				}
			}
			path[i][1][1] = 0;
			path[i][1][0] = pp;
			
			dp[i][1] = dp[pp][0];

			if (pp != -1 && minn + (i - k + 2)*b < dp[i][1])
			{
				dp[i][1] = minn + (i - k + 2)*b;
				path[i][1][0] = p;//在出b的时候转移
			}
				
			

		}

		printf("%lld\n", min(dp[n][0], dp[n][1]));

		int flag;

		if (dp[n][0] > dp[n][1])
		{
			flag = 1;
		}
		else
		{
			flag = 0;
		}

		
		int pos = n;

		while (pos != 1)
		{
			int r = pos;
			int l = path[pos][flag][0]-1;

			if (flag == 0)
			{
				for (int i = l; i < r; i++)
				{
					ans[i] = ans[r];
				}
			}
			else
			{
				for (int i = r - 1; i >= l; i--)
				{
					ans[i] = ans[i + 1] ^ 1;
				}

			}
			int x = pos;
			int y = flag;
			
			pos = path[x][y][0];
			flag = path[x][y][1];

			
		}


		for (int i = 1; i <= n; i++)
		{
			printf("%lld", ans[i]);
		}
		putchar('\n');

	}


	system("pause");
	return 0;
}