K-periodic Garland
给定一个长度位\(n\)的\(01\)串，每次操作可以将\(1\)变为\(0\)或者将\(0\)变为\(1\)，现在你需要通过操作使得所有\(1\)之间的距离为\(k\)，求最少的操作次数，注意全为\(0\)也算
\(1<=n<=1e6,1<=k<=n\)
\(dp\) / 贪心 : 最大子段和思想
方法一：\(dp\) \(O(n)\)
状态表示：\(f[i][0/1]\)：代表将区间\([1,i]\)变为合法串的最小操作次数，且第\(i\)位为\(0/1\)
状态转移：
- 贪心考虑只有两种情况的时候我们可以将第\(i\)位变成\(1\)：
- 若第\(i-k\)位也是\(1\)，我们可以考虑将第\(i\)位变为\(1\),那么我们需要将\([i-k+1,i-1]\)中的所有1变为0
- 我们同样可以考虑使第\(i\)位前面所有的1变为0，从第\(i\)位的\(1\)重新当作起始位置，那么我们需要将前面所有的1变为0
- 同时如果该位本身不是\(1\)，我们需要将其变为\(1\)
\(f[i][1]=min(f[i][1]+pre[i-1]-pre[i-k],pre[i-1]) + (s[i]=='0')\)
- 同样只有两种情况我们可以将第\(i\)位变为\(0\)：
- 第\(i-1\)位是1的情况
- 第\(i-1\)位是0的情况
- 如果第\(i\)位不是0，我们需要将其变为0
\(f[i][0]=min(f[i-1][1],f[i-1][0])+(s[i]=='1')\)
状态初始：\(f[i]=0\)
方法二：贪心 + 枚举对\(k\)余数 \(复杂度：调和级数O(nlogn)\)
由题意可知这些\(1\)一定是连续的且距离间隔\(k\)，这说明1所处的位置对\(k\)取模的模数是相同的，且这些1连续，所以我们可以考虑根据对\(k\)的余数来枚举\(1\)的起始位置，所以我们不妨先将所有的1变为0
我们设\(cnt\)：可以减免的答案贡献，或者说从起始位置到现在1的前缀和数量与0的前缀和数量之差；
- 对于某一位来说，我们需要其为1，并且其本身已经为1，说明我们原本不用将其变为0，所以这部分答案可以减免，\(cnt\)++，
- 对于某一位来说，我们需要其为1，但是其本身为0，说明我们这部分答案不能减免，\(cnt\)--，
- 如果\(cnt<0\)，说明从起始位置开始0的数量已经比1的数量多了，也就是说我们将这些前面位置都变成1就比全部变为0吃亏，倒不如全部变为0，借用最大子段和的思想我们直接舍弃前面的部分，将该位置重新当成起始位置，\(cnt=0\)
- 我们在枚举过程中始终维护\(cnt\)的最大值即可
时间复杂度为调和级数：\(O(nlogn)\)
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 1e6 + 10, M = 4e5 + 10;
int n, k;
int f[N][2];
int pre[N];
void solve()
{
cin >> n >> k;
string s;
cin >> s;
s = " " + s;
for (int i = 1; i <= n; ++i)
pre[i] = pre[i - 1] + (s[i] == '1');
for (int i = 1; i <= n; ++i)
{
f[i][1] = min(f[max(0ll, i - k)][1] + pre[i - 1] - pre[max(0ll, i - k)], pre[i - 1]) + (s[i] == '0');
f[i][0] = min(f[i - 1][1], f[i - 1][0]) + (s[i] == '1');
}
cout << min(f[n][0], f[n][1]) << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 1e6 + 10, M = 4e5 + 10;
int n, k;
void solve()
{
cin >> n >> k;
string s;
cin >> s;
s = " " + s;
int ans = 0;
for (int i = 1; i <= n; ++i)
if (s[i] == '1')
ans++;
int maxx = -INF;
for (int i = 1; i <= k; ++i)
{
int cnt = 0;
for (int j = i; j <= n; j += k)
{
if (s[j] == '1')
cnt++;
else
cnt--;
if (cnt < 0)
cnt = 0;
maxx = max(cnt, maxx);
}
}
cout << ans - maxx << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}