← 返回题目列表

Codeforces · 2231/D

D. 最大前缀和

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

521 与“我爱你”的中文发音相同。在这个特殊的日子里,小S想给小A一些精心准备的片段,以回忆他们多年的友谊。

小S准备了一个数组$$$a_1,a_2,\ldots,a_n$$$。让我们定义它的前缀和数组 $$$b_1, b_2, \ldots, b_n$$$,其中 $$$b_i = a_1 + a_2 + \ldots + a_i$$$。还定义 $$$b$$$ 的前缀最大数组:$$$c_1, c_2, \ldots, c_n$$$,其中 $$$c_i = \max(b_1, b_2, \ldots, b_i)$$$。

现在数组$$$a$$$已经部分丢失,幸好小S还保留着数组$$$c$$$。你的任务是恢复数组$$$a$$$并发送给小A,或者报告不存在这样的数组——这样的话,善良可爱的小A也不会生气。

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

  • 如果您记住 $$$a_i$$$ 的值,则 $$$s_i = 1$$$,并且您将获得 $$$a_i$$$ 的真实值。
  • 如果您不记得 $$$a_i$$$ 的值,则 $$$s_i = 0$$$,并且您将得到 $$$a_i = 0$$$。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

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

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

每个测试用例的第四行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$|c_i| \le 2 \cdot 10^{11}$$$)。

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

输出

对于每个测试用例,打印“是" 如果数组 $$$a$$$ 存在则在第一行,否则打印 "No“。您可以在任何情况下打印答案。例如,”是的", "是", "NO", "nO”也将被接受。

如果至少有一个解,则在第二行打印 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$|a_i| \leq 10^{18}$$$)。如果有多个合适的数组,您可以打印其中任何一个。

示例

输入
复制

10
4
1110
1 2 -1 0
1 3 3 3
5
00001
0 0 0 0 5
-4 -4 -1 -1 -1
1
1
0
1
6
001111
0 0 2 -3 3 -6
-5 -2 0 0 0 0
5
11110
1 2 0 5 0
1 2 2 7 6
2
01
0 1
-1 -1
6
001010
0 0 5 0 3 0
3 3 4 9 13 16
6
000100
0 0 0 4 0 0
2 6 6 7 7 7
2
00
0 0
4 -1
8
11111111
6 1 1 2 0 5 1 9
6 7 8 10 10 15 16 25

输出
复制

Yes
1 2 -1 0
Yes
-4 0 3 -6 5
No
Yes
-5 3 2 -3 3 -6
No
No
No
Yes
2 4 -3 4 -100 0
No
Yes
6 1 1 2 0 5 1 9

注意

在第一个测试用例中,我们有:

  • $$$a = [1, 2, -1, 0]$$$。
  • $$$b = [1, 3, 2, 2]$$$。
  • $$$c = [1, 3, 3, 3]$$$。

在第三个测试用例中,正确的数组 $$$a$$$ 应等于 $$$[1]$$$,因此不存在解决方案。