博主链接

题目


题意:

给你一个由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");
}