题目
艾丽斯和鲍勃得到一个长度为 \(n\) 的二进制字符串 \(s\)，以及一个整数 \(k\)（满足 \(1 \le k < n\)）。
如果艾丽斯能够将字符串 \(s\) 中的所有字符都变为零，则艾丽斯获胜。如果艾丽斯在有限步内无法获胜，则鲍勃获胜。
艾丽斯和鲍勃轮流操作，艾丽斯先开始。
- 在艾丽斯的回合，她可以选择字符串 \(s\) 中任意一个长度为 \(k\) 的子序列，然后将该子序列中的所有字符设为零。
- 在鲍勃的回合，他可以选择字符串 \(s\) 中任意一个长度为 \(k\) 的子串，然后将该子串中的所有字符设为一。
注意，如果在游戏进行中任意时候（包括艾丽斯和鲍勃回合之间），字符串全部为零，则艾丽斯获胜。
请判断在最优策略下，谁将获胜。
子序列：字符串 \(s\) 的一个字符集合，字符在 \(s\) 中按顺序出现，但不需要相邻。
子串：字符串 \(s\) 的一个连续字符区间，字符必须是相邻的。
输入格式：
- 第一行包含一个整数 \(t\)（\(1 \le t \le 10^4\)），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数 \(n\) 和 \(k\)（\(2 \le n \le 2 \times 10^5\)，\(1 \le k < n\)）。
- 第二行包含长度为 \(n\) 的二进制字符串 \(s\)。
保证所有测试用例中 \(n\) 的总和不超过 \(2 \times 10^5\)。
思路
令\(cnt\)为\(1\)的个数，
一.当\(cnt <= k\)，\(alice\)获胜, 否则分两种情况讨论
二.当\(n >= 2 * k\)，\(bob\)获胜，因为\(alice\)操作完后，一定会有剩余，而\(bob\)可选择最左边或最右边的字串变为\(1\),且一定不会与原有的\(1\)全部重合，所以在\(bob\)操作完后，总有\(cnt>k\)
三。否则，\(n < 2 * k\)，\(alice\)获胜
方法
如此类博弈，获胜问题时，优先从获胜条件，状态转移考虑，运用递推，递归的思想，进行分类讨论
code
#include <bits/stdc++.h>
using namespace std;int t;
int n, k, cnt, l;
string s;void solve()
{cin >> n >> k;cin >> s;cnt = 0;l = s.size();s = ' ' + s;for(int i = 1;i <= l;i++) if(s[i] == '1') cnt++;if(cnt <= k) {cout<<"alice"<<"\n";return;}if(n >= 2 * k){cout<<"bob"<<"\n";}else{cout<<"alice"<<"\n";}}int main(){ios :: sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> t;while(t--){solve();}return 0;
}