Northeast North America 2019 C Cutting the Necklace

题意：

给出一个长度为n的环，环上每个单位都有一个价值。要求使得将其分成恰好k段，每段的价值和相等。是否存在这种切法。

思路：

设和为sum，如果存在解，那么一定会是这样的

显然在12段之间的分界点上其sum[1] % avg 与 23段、34段、41段的和% avg相等，所以只需要判断是否有k个这样的分界点即可。前缀和预处理和暴力枚举都是 \(O(n)\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, k;
ll sum[10000005], w;
map<ll, ll> cnt;

int main() {
	scanf("%d%d", &k, &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &w);
		sum[i] = sum[i - 1] + w;
	}
	if (n >= k) {
		if (sum[n] % k == 0) {
			bool flag = false;
			ll avg = sum[n] / k;
			for (int i = 1; i <= n; i++) {
				cnt[sum[i] % avg]++;
				if (cnt[sum[i] % avg] >= k) {
					flag = true;
					break;
				}
			}
			if (flag) puts("YES");
			else puts("NO");
		} else puts("NO");
	} else puts("NO");
}

Northeast North America 2019 C Cutting the Necklace

原文：https://www.cnblogs.com/LYFer233/p/14749244.html