「ZROI」01

题目大意：给出一个长度为 $n$ 的 $01$ 串 $s$ 和整数 $k$，求一个 $s$ 中最长的子串 $t$ 使得 $t$ 中 $0$ 的个数是 $1$ 的个数的 $k$ 倍，输出最长的 $t$ 的长度。$n \leq 10^6$

每遇到一个 $0$ 就 $sum+1$，遇到 $1$ 就 $sum-k$，那么只有 $sum$ 为 $0$ 的区间才是合法的，因此可以一遍前缀和，如果两个位置的前缀和相等，那么它们中间这段区间就是合法的，而由于求的是最长的区间，因此对于每个值，保存第一次出现的位置即可。注意 $0$ 值第一次出现的位置是 $-1$。

#include <cstdio>
#include <map>

char s[1000005];
int n, k, ans;
long long sum;
std::map<long long,int> a;

int max(int x, int y) {
	return x > y ? x : y;
}

int main() {
	scanf("%d%d%s", &n, &k, s);
	a[0] = -1;
	for (int i = 0; i < n; ++i) {
		sum += s[i] == '0' ? 1 : -k;
		if (a.count(sum) == 0) a[sum] = i;
		else ans = max(ans, i - a[sum]);
	}
	printf("%d\n", ans);
	return 0;
}

时间复杂度 $O(n)$