Codeforces Round #642 (Div. 3)
1353E：K-periodic Garland
-
题意：给定一个只有0 1字符的字符串，字符串长度n，数字k。你每次操作都可以令任意一个字符取反（0变为1，1变为0）。字符串需要变为这种状态：相邻两个1字符的位置l, r(l < r)，需要满足r - l = k 。问使给定字符串改变为所需字符串至少需要多少次操作。
-
思路：对于任意的r, l，若有
r - l = k，则r与l应对k同余。题意可以理解为：在字符串中，只存在一个整数m，所有满足i % k = m(i为字符串下标)的字符组成一个子序列。除该子序列的一个子段中所有元素为1外，字符串其他位置均为0。求将原字符串修改为这样的字符串最少需要多少次操作。 我们可以先假定将字符串中所有1改变为0，然后遍历m的所有可能取值，寻找需要操作次数最少的“元素全为1的子段”，然后用该操作次数加上所有字符1的个数就得到了答案。 -
E题代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
char str[maxn];
int main() {
int t, n, k, num_one, num_now, num_min;
scanf("%d", &t);
while (t--) {
scanf("%d %d %s", &n, &k, str);
num_one = 0;
num_min = 0x3f3f3f3f;
for (int i = 0; i < n; i++) {
if (str[i] == '1') {
num_one++;
}
}
for (int i = 0; i < k; i++) {
num_now = 0;
//寻找最小子段和
for (int j = i; j < n; j += k) {
if (str[j] == '0')
num_now++; //0需要变为1，操作一次
else
num_now--; //1不需要改变，但在now_one中计算过了，需要减去。
if (num_now > 0) num_now = 0;
if (num_now < num_min) num_min = num_now;
}
}
num_min += num_one;
printf("%d
", num_min);
}
return 0;
}
1353F: Decreasing Heights
还没补（逃）。