本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-16 06:03:35

显然的，遇到一个 $0$ 就一定要从当前开始翻转，若不够无法翻转，那么无解。

然后对于翻转，实际上就是将区间 $+1$ 并 $\bmod 2$，那么 $+1$ 直接差分，然后边做边记录前缀和即可，然后用到当前值时再 $\bmod 2$。

然后枚举 $k$ 按照刚才的思路翻转即可。

#include <bits\/stdc++.h>

using namespace std;

typedef long long ll;

int T;
int n;
char s[5010];
int sum[5010];

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		scanf("%s", s + 1);

		for (int k = n; k >= 1; --k) {
			for (int i = 0; i <= n; ++i) sum[i] = 0;
			for (int i = 1; i <= n - k + 1; ++i) {
				int t = s[i] - '0';
				sum[i] += sum[i - 1];
				if (!((t + sum[i]) & 1)) {
					++sum[i];
					--sum[i + k];
				}
			}

			for (int i = n - k + 2; i <= n; ++i) sum[i] += sum[i - 1];

			bool ok = true;

			for (int i = 1; i <= n; ++i) {
				int t = s[i] - '0';

				if (!((t + sum[i]) & 1)) {
					ok = false;
					break;
				}
			}

			if (ok) {
				printf("%d\n", k);
				break;
			}
		}
	}

	return 0;
}