题解：P14754 猫石游戏

_burbur_ · 2025-12-14 19:46:09 · 题解

题意

首先 A 和 B 选石头，A 先 B 后，B 只能选连续 k 个 0，问你 A 最多拿多少个石头。

分析：

毋庸置疑这也只是道签到。

做法

找每一段为 0 的区间，用 cnt0 去统计 0 的数量，我是用总体去减去 B 的数量，因为 B 是后拿的，所以当 \lfloor \frac {cnt0}{k} \rfloor \bmod 2=1，B 是拿不到的，所以直接除二向下取整就行了，最后用 n 一减就完了。

注意

答案一定是 k 的倍数，所以最后除个 k 再乘回来就完了。

上 Code

#include<bits/stdc++.h>
using namespace std;
int n,k;
string s;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k>>s;
    int cnt=0;
    for(int i=0;i<n;i++){
        if(s[i]=='0'){
            int j=i;
            while(j<n&&s[j]=='0') j++;
            cnt+=(j-i)/k;
            i=j-1;
        }
    }
    cout<<(n-(cnt/2)*k)/k*k<<endl;
    return 0;
}