← 返回题目列表

Codeforces · 2107/C

C. 最大子数组和

中文机器翻译题面 查看原题

给定一个数组 $$$a_1,a_2,\ldots,a_n$$$,长度为 $$$n$$$ 和一个正整数 $$$k$$$,但数组 $$$a$$$ 的某些部分丢失。你的任务是填补缺失的部分,以便 最大子数组和$$$a$$$ 的 $$$^{\text{∗}}$$$ 恰好是 $$$k$$$,或者报告不存在解。

正式地,您将获得一个二进制字符串 $$$s$$$ 和一个部分填充的数组 $$$a$$$,其中:

  • 如果您还记得 $$$a_i$$$ 的值,则 $$$s_i = 1$$$ 可以表明这一点,并且您将获得 $$$a_i$$$ 的实际值。
  • 如果您不记得 $$$a_i$$$ 的值,则 $$$s_i = 0$$$ 来表示,并且您将得到 $$$a_i = 0$$$。

您记住的所有值都满足 $$$|a_i| \le 10^6$$$。但是,您可以使用最大 $$$10^{18}$$$ 的值来填写您不记得的值。可以证明,如果存在解,则也存在满足$$$|a_i|的解。 \le 10^{18}$$$。

$$$^{\text{*}}$$$The 长度为 $$$n$$$ 的数组 $$$a$$$ 的 最大子数组和 ,即 $$$a_1, a_2, \ldots a_n$$$ 定义为 $$$\max_{1 \le i \le j \le n} S(i, j)$$$ 其中 $$$S(i, j) = a_i + a_{i + 1} + \ldots + a_j$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个数字 $$$n,k$$$ ($$$1 \le n \le 2 \cdot 10^5,1 \le k \le 10^{12}$$$)。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制 ($$$\texttt{01}$$$) 字符串 $$$s$$$。

每个测试用例的第三行包含 $$$n$$$ 数字 $$$a_1,a_2,\ldots,a_n$$$ ($$$|a_i| \le 10^6$$$)。如果$$$s_i = \texttt{0}$$$,则保证$$$a_i = 0$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果存在解决方案,则首先输出 $$$\texttt{Yes}$$$;如果不存在解决方案,则首先输出 $$$\texttt{No}$$$。您可以在任一情况下打印每个字符,例如 $$$\texttt{YES}$$$ 和 $$$\texttt{yEs}$$$ 也将被接受。

如果至少有一个解决方案,请在第二行打印 $$$n$$$ 数字 $$$a_1,a_2,\ldots,a_n$$$。 $$$|a_i| \le 10^{18}$$$ 必须成立。

示例

输入
复制

10
3 5
011
0 0 1
5 6
11011
4 -3 0 -2 1
4 4
0011
0 0 -4 -5
6 12
110111
1 2 0 5 -1 9
5 19
00000
0 0 0 0 0
5 19
11001
-8 6 0 0 -5
5 10
10101
10 0 10 0 10
1 1
1
0
3 5
111
3 -1 3
4 5
1011
-2 0 1 -5

输出
复制

Yes
4 0 1
Yes
4 -3 5 -2 1
Yes
2 2 -4 -5
No
Yes
5 1 9 2 2
Yes
-8 6 6 7 -5
Yes
10 -20 10 -20 10
No
Yes
3 -1 3
Yes
-2 4 1 -5

注意

在测试用例 $$$1$$$ 中,只有第一个位置未填充。我们可以用 $$$4$$$ 填充它,得到数组 $$$[4, 0, 1]$$$,它的最大子数组和为 $$$5$$$。

在测试用例$$$2$$$中,只有第三个位置没有被填充。我们可以用$$$5$$$填充它来得到数组$$$[4, -3, 5, -2, 1]$$$。这里最大子数组和来自子数组$$$[4, -3, 5]$$$,根据要求它是$$$6$$$。

在测试用例 $$$3$$$ 中,第一个和第二个位置未填充。我们可以用 $$$2$$$ 填充两者,得到数组 $$$[2, 2, -4, -5]$$$,它的最大子数组和为 $$$4$$$。请注意,其他输出也是可能的,例如 $$$[0, 4, -4, -5]$$$。

在测试用例 $$$4$$$ 中,不可能获得有效的数组。例如,如果我们用 $$$0$$$ 填充第三个位置,我们会得到 $$$[1, 2, 0, 5, -1, 9]$$$,但是它的最大子数组总和为 $$$16$$$,而不是要求的 $$$12$$$。