(论我卡在第一题导致没去想第三题，结束前用5分钟想完思路。。。） 首先每组数据给出了n，k，还有一个字符串r。题目要我们求原字符串b中“1”的最小个数mn和最大个数mx，所以就是要我们讨论b的“0”“1”情况 我们可以比较r中的第i个字符x与第i+1个字符y，因为现在导致变化的是b中的第i个字符t的减少与第i+k个字符q的增加，若x等于y，则t等于q，反之亦然。所以通过两两比较，最终可以将b分为k组，第i组中包含了下标模k为i的字符。而每组中分为对立的两部分，mn就是较小的部分相加，mx就是较大的部分相加。但是要注意检验，检验前k个数即可（后面的随之成立），若模二于r[0]不同，则改变对立两部分差值最小的那一组。（代码略为冗杂）

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],b[N],c[N],t[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		int n,k;
		cin>>n>>k;
		string s;
		cin>>s;
		for(int i=0;i<n-k+1;i++)
		{
			t[i+1]=s[i]-'0';
		}
		if(k==1)
		{
			int sum=0;
			for(int i=1;i<=n-k+1;i++)
			{
				sum+=t[i];
			}
			printf("%d %d\n",sum,sum);
			continue;
		}
		for(int i=1;i<=k;i++)
		{
			a[i%k]++;
			c[i]=1;
		}
		for(int i=k+1;i<=n;i++)
		{
			if(t[i-k+1]!=t[i-k])
			{
				if(c[i-k]==1)
				{
					b[i%k]++;
					c[i]=2;
				}
				else
				{
					a[i%k]++;
					c[i]=1;
				}
			}
			else
			{
				if(c[i-k]==1)
				{
					a[i%k]++;
					c[i]=1;
				}
				else
				{
					b[i%k]++;
					c[i]=2;
				}
			}
		}
		bool flag=0;
		int ansmx=0,ansmn=0;
		for(int i=0;i<k;i++)
		{
			ansmx+=max(a[i],b[i]);
			ansmn+=min(a[i],b[i]);
		}
		int mn=0x3f3f3f3f;
		for(int i=0;i<k;i++)
		{
			mn=min(mn,abs(a[i]-b[i]));
		}
		int summn=0,summx=0;
		for(int i=1;i<=k;i++)
		{
			if(a[i%k]>=b[i%k])
			{
				summx++;
			}
			if(a[i%k]<b[i%k])
			{
				summn++;
			}
		}
		if(summn%2!=t[1])
		{
			
			printf("%d ",ansmn+mn);
		}
		else
		{
			printf("%d ",ansmn);
		}
		if(summx%2!=t[1])
		{
			printf("%d\n",ansmx-mn);
		}
		else
		{
			printf("%d\n",ansmx);
		}
	}
	return 0;
}

前情提要：每一个 $r$ 就对应着它所管辖的 $s$ 的区间异或和。

先证明一下下文的两个结论：

1.整个 $s$ 只需要确定前 $k$ 个字符即可唯一确定：考虑 $[2,k+1]$ 这一个区间，因为 $[2,k]$ 已经被确定，所以 $k+1$ 可以被唯一确定。此时，因为 $[3,k+1]$ 已经被确定，所以 $k+2$ 可以被唯一确定，以此类推，故 $s$ 只需要确定 $s$ 的前 $k$ 个字符即可。

2.整个 $s$ 被拆分成 $k$ 条链，其中每条链形如 $s_{i}->s_{i+k}->s_{i+2k}->\dots$，且只需要知道链中的任何一个数即可推出整条链：考虑相邻的两项 $s_{i+ak}$ 与 $s_{i+(a+1)k}$，以前者为开头的区间为 $[s_{i+ak},s_{i+(a+1)k-1}]$，以后者为结尾的区间为 $[s_{i+ak+1},s_{i+(a+1)k}]$，两者取交得到 $[s_{i+ak+1},s_{i+(a+1)k-1}]$，设其区间异或和为 $x$。对于前一个，对应的 $r=s_{i+ak}\oplus x$，对于后者，其对应的 $r=x\oplus s_{i+(a+1)k}$，两者取异或得 $s_{i+ak}\oplus s_{i+(a+1)k}$。所以知道其中一个后就能通过所对应的 $r$ 的异或算出另一个。所以整条链只用知道一个数就能推出所有数。

知道这两点后，我们就只用去考虑 $[1,k]$ 的数怎么填划算了，将每个数填入 $1$ 或 $0$ 时对答案的贡献算出来，贪心的去取最少/最多的 $1$。

但这样有个问题，取出来的状态有可能不符合要求。

我们思考：一条链上的所有点是被“捆绑”在一起的，他们所对应的区间有都是相邻的，所以只要不符合要求就一定是全部不符合要求（这一点可以自己想想）。

同理，只要改一条链上的一个点，那么所有点都会被改变，所有的区间也会被反转，此时一定符合要求。

所以考虑“撤销”一个 $1$ 或“新建”一个 $0$，取对答案贡献最小的即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
int val[200005];
bool r[200005];
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,k;
		cin>>n>>k;
		for(int i=1;i<=n-k+1;i++){
			char tmp;
			cin>>tmp;
			r[i]=tmp-'0';
		} 
		int base=0;
		for(int i=1;i<=k;i++){
			int flag=0,cnt0=0,cnt1=0;//假设链上第一个数填1时，链上0和1的数量。 
			for(int j=i;j<=n;j+=k){
				if(flag){
					cnt0++;
				}
				else{
					cnt1++;
				} 
				if(r[j]!=r[j+1]){
					//r[j]!=r[j+1]，则r[j]^r[j+1]=1，因为[j+1,j+k-1]这段区间异或起来后抵消，所以s[j]!=s[j+k] 
					flag^=1;
				}
			}
			base+=cnt0;
			val[i]=cnt1-cnt0;
		} 
		int o=0,ans1=base,ans2=base,mi=inf;
		//ans1最小，ans2最大，一定要赋值为base（假设前k个数都是1）
		//o用于判断这么填1是否符合第一个r 
		for(int i=1;i<=k;i++){
			if(val[i]<0){
			//val[i]<0说明在这条链上的0更多，所以给这里填1
			///同时base+val[i]相当于把统计时val[i]中的-cnt0抵消，这样得出这条链上1的个数 
				ans1+=val[i];
				o^=1;
			}
		}
		if(o!=r[1]){
			//这么填不符合，因为后面的会随链的第一个变化而变化，所以直接找[1,k]中修改后影响最小的 
			for(int i=1;i<=k;i++){
				mi=min(mi,abs(val[i]));
			}
			//改了之后，不论是将1变成0还是将0变成1，都会导致结果增大，所以直接加上绝对值 
			ans1+=mi;
		}
		//和上面一样了 ，不再解释 
		o=0,mi=inf;
		for(int i=1;i<=k;i++){
			if(val[i]>0){
				ans2+=val[i];
				o^=1;
			}
		}
		if(o!=r[1]){ 
			for(int i=1;i<=k;i++){
				mi=min(mi,abs(val[i]));
			}
			ans2-=mi;
		}
		cout<<ans1<<" "<<ans2<<"\n";
	}
	return 0;
}

显然地，只要确定 $s$ 的前 $k$ 个字符，整个 $s$ 就确定了。进一步地，能够发现，对于每个 $1 \le i \le k$，$s_i$ 确定后，能确定的字符有 $s_{i+k},s_{i+2k},\dots$，故整个字符串被拆成 $k$ 条链，对于每条链，只要确定链头，整条链便能确定，且各条链之间相互独立。

故对于每条链，我们分别处理出当链头为 $0$ 或 $1$ 时，整条链中 $1$ 的数量。采用类似 CSP-S 2025 T1 的反悔贪心做法，先贪心地对每条链选择 $1$ 更多/更少的方案，再进行调整以满足 $r$ 的限制。

复杂度 $O(n)$。

:::success[赛时代码]

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int r[MAXN], val[MAXN], n, k, t, base;
void solve(){
	cin >> n >> k;
	for (int i = 1; i <= n - k + 1; i++){
		char tmp;
		cin >> tmp;
		r[i] = tmp - '0';
	}
	base = 0;
	for (int i = 1; i <= k; i++){
		int cur = 0, cnt0 = 0, cnt1 = 0;
		for (int j = i; j <= n; j += k){
			if (cur){
				cnt0++;
			}
			if (r[j] != r[j + 1]){
				cur ^= 1;
			}
		}
		cur = 1;
		for (int j = i; j <= n; j += k){
			if (cur){
				cnt1++;
			}
			if (r[j] != r[j + 1]){
				cur ^= 1;
			}
		}
		base += cnt0;
		val[i] = cnt1 - cnt0;
	}
	int o = 0, minans = base, maxans = base, minn = INF;
	for (int i = 1; i <= k; i++){
		if (val[i] < 0){
			minans += val[i];
			o ^= 1;
		}
	}
	if (o != r[1]){
		for (int i = 1; i <= k; i++){
			minn = min(minn, abs(val[i]));
		}
		minans += minn;
	}
	o = 0, minn = INF;
	for (int i = 1; i <= k; i++){
		if (val[i] > 0){
			maxans += val[i];
			o ^= 1;
		}
	}
	if (o != r[1]){
		for (int i = 1; i <= k; i++){
			minn = min(minn, abs(val[i]));
		}
		maxans -= minn;
	}
	cout << minans << " " << maxans << endl;
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while (t--){
		solve();
	}
	return 0;
}

:::

题解：P14979 [USACO26JAN1] Sliding Window Summation S

思路

把窗口奇偶性串 $r$ 当成差分约束：

1. 设前缀异或数组 $s[0\ldots n]$，$s[0]=0$，则

   $$r_i = s_{i+K} \oplus s_i.$$

   一条边 $i \to i+K$，权 $r_i$。

2. 并查集按奇偶合并后，每个连通块颜色可 $0$ 可 $1$。

   • 最小 $1$ 的个数 $= \sum \min(\text{cnt}_0, \text{cnt}_1)$。
   • 最大 $1$ 的个数 $= \sum \max(\text{cnt}_0, \text{cnt}_1)$。

代码

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

int arr1[1000010], arr2[1000010], arr3[1000010], arr4[1000010];

int main() {
	int T;
    cin >> T;
    while (T--) {
    	int n, k;
        cin >> n >> k;
        for (int i = 1; i <= k; i++) {
            arr2[i] = i;
            arr3[i] = arr4[i] = 0;
        }
        for (int i = 0; i <= n - k; i++) {
            char ch;
            cin >> ch;
            while (ch != '0' && ch != '1') cin >> ch;
            arr1[i] = ch;
            if (i)
                arr2[i + k] = arr2[i] * ((arr1[i] ^ arr1[i - 1]) ? -1 : 1);
        }
        for (int i = 1; i <= n; i++) {
            if (arr2[i] > 0)
                arr3[arr2[i]]++;
            else
                arr4[-arr2[i]]++;
        }
        int res = 0;
        vector<int> t;
        if ((k ^ arr1[0]) & 1)
            swap(arr3[1], arr4[1]);
        for (int i = 1; i <= k; i++) {
            res += arr3[i];
            t.push_back(arr4[i] - arr3[i]);
        }
        sort(t.begin(), t.end());
        int l = res, r = res;
        for (int i = 0; i + 1 < t.size(); i += 2)
            if (t[i] + t[i + 1] < 0)
                l += t[i] + t[i + 1];
        reverse(t.begin(), t.end());
        for (int i = 0; i + 1 < t.size(); i += 2)
            if (t[i] + t[i + 1] > 0)
                r += t[i] + t[i + 1];
        cout << l << ' ' << r << endl;
    }
}