傳送門
文章目錄
題意：
思路：
我們將每一段...拿出來看成若干段，將其分成以下四種情況：
(1)len<b(1)len<b(1)len<b
(2)b≤len<a(2)b\le len<a(2)b≤len<a
(3)a≤len<2?b(3)a\le len<2*b(3)a≤len<2?b
(4)len≥2?b(4)len\ge 2*b(4)len≥2?b
我們依次考慮這四種線段。
(1)(1)(1)首先線段111是無用線段，不需要考慮。
(2)(2)(2)線段222只能由后手操作，如果存在線段222，那么后手必勝。
證明：因為先拋去線段222，使用其他的線段進行游戲，結果無非兩個，先手不能操作和后手不能操作。先手不能操作那么后手必勝，后手不能操作的時候說明線段已經用光了，這個時候拿出線段222來使得后手仍能操作，后手必勝。
(3)(3)(3)線段333二者只能操作一次，那么如果只存在線段333的話，由偶數段線段333的時候后手必勝，有奇數段線段333的時候先手必勝。
比較顯然，不加以證明。
(4)(4)(4)線段444如果存在至少兩條的時候，后手必勝。
證明：由于后手可以從線段444中截出來一段線段222，所以先手動的時候最多能操作一個線段444來使得其不能被分出來線段222，所以如果有至少兩個線段444那么后手必勝。
現在討論只有一個線段444的時候怎么辦。
首先先手肯定是要操作線段444的，不然被后手拿出來線段222就必敗了。那么我們可以枚舉先手將線段444分成的兩段的長度，如果兩段中有一段是線段222或者線段444，那么肯定是不行的。那么只剩下線段111和線段333了，只需要判斷以下線段333的個數即可。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int a
,b
,n
;
char s
[N
];int get(int cnt
) {if(cnt
<b
) return 1;else if(cnt
<a
) return 2;else if(cnt
<2*b
) return 3;else return 4;
}int main()
{
int _
; scanf("%d",&_
);while(_
--) {int x
,y
,z
; x
=y
=z
=0;scanf("%d%d%s",&a
,&b
,s
+1);n
=strlen(s
+1);int len
=0;for(int i
=1;i
<=n
;i
++) {if(s
[i
]=='X') continue;int cnt
=0;while(i
<=n
&&s
[i
]=='.') i
++,cnt
++; i
--;if(cnt
<b
) continue;else if(cnt
<a
) x
++;else if(cnt
<2*b
) y
++;else z
++,len
=cnt
;}if(x
||z
>1) puts("NO");else {if(!z
) {if(y
%2==0) puts("NO");else puts("YES");} else {bool flag
=false;for(int st
=0;st
+a
<=len
;st
++) {int l
=st
,r
=len
-st
-a
;int id1
=get(l
),id2
=get(r
);if(id1
==2||id2
==2||id1
==4||id2
==4) continue;int now
=y
+(id1
==3)+(id2
==3);if(now
%2==0) {flag
=true;break;}}if(flag
) puts("YES");else puts("NO");}}}return 0;
}
總結
以上是生活随笔為你收集整理的Educational Codeforces Round 73 (Rated for Div. 2) E. Game With String 思维博弈 好题（2500)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
