0921考试T2

题目描述：

最近小Z和他的朋友都迷上了一款手机游戏：不服来战。游戏的设定十分简单，在游戏开始时，会给出一排共N个灯，有的灯是开着的有的是关着的，每个灯都有一个分数。而玩家可以进行任意次操作，每次操作改变连续K盏灯的开关状态。尽管机智如小Z也总是没法得到最高分，没法把他的朋友PK下来。于是他来向你请教，希望知道在不同情况下，最高分分别是多少。

思维题吧，我没看出来有啥算法。

我们已知的操作为：对连续的(k)个灯的状态取反。那我们如果对这两个区间，([i, i + k - 1], [i + 1, i + k])，进行这个操作那么我们发现我们只取反了(i, i + k)，这两个灯，中间的那些改变了两次，相当于没有操作。所以我们又得到了一种操作：相距(k)的两个灯可以同时取反。

然后我们其实可以把整个区间的操作变成这种：进行零次或一次操作一和若干次操作二。

那我们看怎么进行操作二就好了呗。

假设现在(n = 10, k = 3)，因为相距(k)的两个灯可以同时操作，我们可以把(n)分为三组([1, 4, 7, 10],[2, 5, 8],[3, 6, 9])。我们可以发现组与组之间的操作时互不影响的。如果这一组里有偶数个“初始时灯是关着的”，那么这一组肯定都可以变为开着的；如果为奇数，那么最后必须剩下一个关着的，我们挑出分值最小的那个让它关着就好了。

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}

const int N = 2005;
int T, n, k, ans;
int a[N], b[N], c[N], tmp[N], vis[N];

int func() {
    int res = 0;
    for(int i = 1;i <= k; i++) {
        int cnt = 0, minn = 1e9;
        for(int j = i;j <= n; j += k) {
            if(!a[j]) cnt ++; 
            res += b[j]; minn = min(b[j], minn);
        }
        if(cnt & 1) res -= minn;
    }
    return res;
}

int main() {

    T = read();
    while(T --> 0) {
        n = read(); k = read();
        for(int i = 1;i <= n; i++) a[i] = read();
        for(int i = 1;i <= n; i++) b[i] = read();
        ans = func();
        for(int i = 1;i <= k; i++) a[i] ^= 1;
        ans = max(ans, func());
        printf("%d
", ans);
    }

    fclose(stdin); fclose(stdout);
    return 0;
}