题目：E. Game With String
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output
Alice and Bob play a game. Initially they have a string s1,s2,…,sn, consisting of only characters . and X. They take alternating turns, and Alice is moving first. During each turn, the player has to select a contiguous substring consisting only of characters . and replaces each of them with X. Alice must select a substing of length a, and Bob must select a substring of length b. It is guaranteed that a>b.
For example, if s=…X… and a=3, b=2, then after Alice’s move string can turn only into XXXX… And if it’s Bob’s turn and the string s=…X…, then after Bob’s move the string can turn into XX.X…, .XXX… or …XXX.
Whoever is unable to make a move, loses. You have to determine who wins if they both play optimally.
You have to answer q independent queries.
Input
The first line contains one integer q(1≤q≤3⋅105) — the number of queries.
The first line of each query contains two integers a and b (1≤b<a≤3⋅105).
The second line of each query contains the string s(1≤|s|≤3⋅105), consisting of only characters . and X.
It is guaranteed that sum of all |s| over all queries not exceed 3⋅105.
Output
For each test case print YES if Alice can win and NO otherwise.
You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).
Example
| Input |
|---|
| 3 3 2 XX......XX...X 4 2 X...X.X..X 5 3 .......X..X |
| Output |
| YES NO YES |
Note
In the first query Alice can select substring s3…s5. After that s turns into XXXXX…XX…X. After that, no matter what move Bob makes, Alice can make the move (this will be her second move), but Bob can’t make his second move.
In the second query Alice can not win because she cannot even make one move.
In the third query Alice can choose substring s2…s6. After that s turns into .XXXXX.X…X, and Bob can’t make a move after that.
思路：
1.对于一段连续的点，它一共有四种状态：(1) len<b; (2) b≤len<a; (3) a≤len<2b; (4) len≥2b;（至于会有2*b小于a的情况，其实不用特殊考虑，就当第三种状态没有~）
2.状态一没什么好说，谁都不能放；只要出现状态2，Bob一定赢；状态3是只能一个人放这个位置；状态4出现两次及以上Bob一定赢，因为利用一个状态4，Bob可以创造出状态2；
3.不考虑状态4和2，状态3奇数Alice赢，偶数Bob赢；
4.如果有一个状态4，那Alice第一步一定放在状态4；而状态4可以被分成两个状态1、一个状态1和一个状态3、两个状态3(Alice不会找死自己分出状态2哒)。而如果此时状态3为奇数，我们需要创造出一个1和3(或者没有状态4,Alice也能赢)；如果状态3为偶数，我们则需要创造出两个状态1或者两个状态3；
5.整理思路的时候不要想复杂，只需判断当前状态，是否能达到必胜或者达到必输的要求即可。
(头铁的我对状态4出现一次时，疯狂对len进行分类讨论，结果极其复杂…好的思路真的让人神清气爽)
代码：
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#include<iostream>
using namespace std;
string s;
int a,b;
void game(){
int n2=0,n3=0,n4=0,l,cnt=0;
for(int i=0;i<=s.length()&&!n2&&n4<2;i++){
if(i<s.length()&&s[i]=='.') cnt++;
else{
if(cnt>=b&&cnt<a) n2++;
else if(cnt>=a&&cnt<2*b) n3++;
else if(cnt>=2*b) {n4++;l=cnt;}
cnt=0;
}
}
bool _11=l>=2*b&&l<=(a+2*b-2);
bool _13=l>=2*a&&l<(a+3*b-1);
bool _33=l>=3*a&&l<=(a+4*b-2);
if(n2||n4>1) cout<<"NO
";
else if((!(n3&1)&&(_11||_33))||(n3&1&&(!n4||_13))) cout<<"YES
";
else cout<<"NO
";
}
int main(){
IOS;
int q;
cin>>q;
for(int i=0;i<q;i++){
cin>>a>>b>>s;
game();
}
return 0;
}