记录编号	596264	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO24 Open Gold]Cowreography	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	0.297 s
提交时间	2024-10-23 21:25:48	内存使用	5.15 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
const int N = 1000005;

int n, k;
ll ans = 0;
char a[N], b[N];
multiset<pair<int, int>> s[2];

int main(){
	freopen("cowreography.in","r",stdin);
	freopen("cowreography.out","w",stdout); 
	scanf("%d%d%s%s",&n,&k,a+1,b+1);
	for(int i=1;i<=n;i++){
		if(a[i]!=b[i]){
			int x=a[i]-'0';
			if (s[!x].empty())s[x].insert(mp(i%k,i));
            else{
                auto it=s[!x].lower_bound(mp(i%k, 0));
                if(it==s[!x].end())it=s[!x].begin();
                ans+=(i-(it->second)-1)/k+1,s[!x].erase(it);
            }
		}
	}
	printf("%lld",ans);
	return 0;
}