题解归档 - cf2236B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2236B
• 本地来源：problems/cf2236B/idea.md
• 题目链接：https://codeforces.com/contest/2236/problem/B

思路

pattern:
parity invariant on graph components
claim:
Answer YES iff every residue class modulo k contains an even number of ones.
why:
The operation toggles positions i and i+k, so positions with the same (i-1) mod k form one path component. Toggling an edge of this path preserves the parity of the number of ones in that component.
sufficient:
On a path component, if the number of ones is even, pair adjacent remaining ones by sweeping from left to right; toggling along the path between each pair removes both.
brute/check:
Exhaustive BFS over all strings for n<=8 matches the parity formula.
edge:
If k=n, there are no moves, so every one is alone in its component and the string must already be all zero.

代码

来源：problems/cf2236B/solution.cpp

/* Author: likely
 * Time: 2026-06-19 10:49:39
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll n,k,i,j,pd;
char s[maxn+5];
ll cnt[maxn+5];
int main(){
    ll t;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&k);
        scanf("%s",s+1);
        for(i=0;i<k;i++) cnt[i]=0;
        for(i=1;i<=n;i++) cnt[(i-1)%k]+=s[i]-'0';
        pd=1;
        for(i=0;i<k;i++){
            if(cnt[i]%2){
                pd=0;
                break;
            }
        }
        if(pd) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}