← 返回题目列表

Codeforces · 1748/C

C. 零和前缀

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

数组 $$$v_1,v_2,\ldots,v_n$$$ 的分数定义为索引 $$$i$$$ ($$$1 \le i \le n$$$) 的数量,使得 $$$v_1+v_2+\ldots+v_i = 0$$$。

给定一个数组 $$$a_1,a_2,\ldots,a_n$$$,长度为 $$$n$$$。您可以多次执行以下操作:

- 选择索引 $$$i$$$ ($$$1 \le i \le n$$$) 使得 $$$a_i=0$$$;
- 然后将 $$$a_i$$$ 替换为任意整数。

通过执行一系列此类操作可以获得 $$$a$$$ 的最大可能分数是多少?

输入

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — array $$$a$$$.

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

输出

对于每个测试用例,在执行一系列操作后打印数组 $$$a$$$ 的最大可能分数。

示例

输入 #1

5
5
2 0 1 -1 0
3
1000000000 1000000000 0
4
0 0 0 0
8
3 0 2 -10 10 -30 30 0
9
1 0 0 1 -1 0 1 0 -1

输出 #1

3
1
4
4
5

注意

在第一个测试用例中,最好在一次操作中将 $$$a_2$$$ 的值更改为 $$$-2$$$。

生成的数组 $$$a$$$ 将为 $$$[2,-2,1,-1,0]$$$,得分为 $$$3$$$:

- $$$a_1+a_2=2-2=0$$$;
- $$$a_1+a_2+a_3+a_4=2-2+1-1=0$$$;
- $$$a_1+a_2+a_3+a_4+a_5=2-2+1-1+0=0$$$。

在第二个测试用例中,最好将 $$$a_3$$$ 的值更改为 $$$-2\,000\,000\,000$$$,从而为我们提供一个分数为 $$$1$$$ 的数组。

在第三个测试用例中,不需要执行任何操作。