题解 | #切圈圈#

题意：对于一个保证 ${\sum }_{i=1}^n{a}_i=0\backslash sum\backslash limits\_\{i=1\}^\{n\}\; a\_i=0$ 的序列 $\{a_n\}\backslash \{a\_n\backslash \}$，求划分出的最大段数使得每一段区间和均为 $00$。

考虑前缀和，对于一个区间 $[l,r][l,r]$，如果 $s_{l-1}=s_{r}s\_\{l-1\}=s\_r$ 代表区间和为 $00$：

$s_{l-1}=a_1+a_2+\cdots +a_{l-1}s\_\{l-1\}=a\_1+a\_2+\backslash cdots+a\_\{l-1\}$

$s_r=a_1+a_2+\cdots +a_{r}s\_\{r\}=a\_1+a\_2+\backslash cdots+a\_\{r\}$

$\therefore s_r-s_{l-1}=a_l+\cdots +a_r\backslash therefore\; s\_\{r\}-s\_\{l-1\}=a\_l+\backslash cdots+a\_r$

又 $\because s_{l-1}=s_r\backslash because\; s\_\{l-1\}=s\_r$

$\therefore a_l+\cdots +a_r=0\backslash therefore\; a\_l+\backslash cdots+a\_r=0$，得证。

有了这个结论，我们只需要数出前缀和数组中的众数即可，等于是把每一段都划分成这个众数既为 $s_{l-1}s\_\{l-1\}$ 又为 $s_{r}s\_r$。

环形和整个序列和为零的性质保证了这样做的正确性。

#include<map>
#include<cstdio>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
int mx(int x, int y){
	return x > y ? x : y;
}
std::map<int, int>map;
int main(){
	int T = init();
	while (T--) {
        map.clear();
		int n = init(), ans = 0, max = 0;
		while (n--) {
			ans += init();
			max = mx(max, ++map[ans]);
		}
		print(max), putchar('\n');
	}
}