Codeforces Round 512--C.Vasya and Golden Ti

题目

---

---

题意：

给你一个由0-9组成的串，问能不能将串分成2份及两份以上，使每份数和相等

---

解题思路：

先特判下如果串中只有一种字符且串长度大于2则肯定可以，然后求出把0消去后串的前缀和（因为0对和没影响。再枚举i（i从1到n）位的前缀和num[i]，再看看（i-n）中有多少个前缀和num[j]能整除num[i]，如果满足的数量ans大于等于2且num[n]/ans==num[i],则一定可以分成ans份，否则输出no

---

代码：

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
char s[110];
int num[110];
int main() {
	int n;
	scanf("%d", &n);
	scanf("%s", s+1);
	int cnt = 1;
	for(int i=1;i<=n;i++){
		if (s[i] == '0')continue;
		num[cnt] = num[cnt - 1] + s[i] - '0';
		cnt++;
	}
	int flag = 1;
	for (int i = 1; i <n; i++) {
		if (s[i] != s[i + 1])flag = 0;
	}
	if (flag&&n >= 2) {
		printf("YES\n");
		return 0;
	}
	for (int i = 1; i < cnt; i++) {
		int ans = 0;
		for (int j = i; j < cnt; j++) {
			if (num[j] % num[i] == 0)ans++;
		}
		if (ans >= 2 && num[cnt - 1] % num[i] == 0 && num[cnt - 1] == num[i]*ans) {
			printf("YES\n");
			return 0;
		}
	}
	printf("NO\n");
}