1 solutions
-
0
这道题是一个博弈游戏,题目大致意思就是给一个字符串,然后两人轮流操作,每次操作可以选择一个连续且相同的字符串,字符串长度不能超过k,然后将此段字符串翻转。如果谁操作后字符串全为0或1时,那么他将获胜。 这个博弈有三种结果:1、Alice获胜;2、Bob获胜;3、平局。
先来判断Alice获胜的情况,Alice是先手,当他首先执行一次操作后,如果他没有获胜的话,那么Bob只需在重复一次Alice的操作,那么Alice将无法获胜。这时我们就得出了Alice的获胜情况,即:如果Alice能一次操作直接获胜,那么他必胜,否则将不会获胜。
再来判断Bob获胜的情况,Bob是后手,当Alice第一次操作后没有获胜,到Bob开始。此时Bob就会遇到和Alice同样的处境,即:如果当前不能直接获胜,那么将无法获胜。因为第三步Alice重复Bob的操作,那么Bob将无法获胜。
那么最后平局的情况就显而易见了,当前两步无法确定出胜负的话,那么必定是平局。
#include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cctype> // #include<cmath> #include<vector> #include<stack> #include<queue> #include<map> #include<set> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); #define ll long long #define ull unsigned long long #define endl '\n' typedef pair<char, int> pir; const int mod = 0x7f7f7f7f; const int N = 100010; int x0, x1, y0, y1; bool flag; int main(void){ IOS int n, k; cin >> n >> k; string s; cin >> s; if(s[0] == '0') { flag = false; x0 ++ ; } else { flag = true; x1 ++ ; } for(int i = 1; i < s.size(); i ++ ) { //计算连续相同子字符串的长度及个数 if(s[i] == '0' && !flag) { x0 ++ ; if(x0 > k) { x0 -= k; y0 ++ ; } } else if(s[i] == '0' && flag) { y1 ++ ; x1 = 0; x0 ++ ; flag = false; } else if(s[i] == '1' && flag) { x1 ++ ; if(x1 > k) { //若长度大于k,它就相当于2个及以上的字符串,不能当作一个,因为无法一次翻转 x1 -= k; y1 ++ ; } } else if(s[i] == '1' && !flag) { flag = true; y0 ++ ; x0 = 0; x1 ++ ; } } if(x0) y0 ++ ; if(x1) y1 ++ ; if(y0 == 0 || y1 == 0) { if(n > k) cout << "Bob" << endl; else cout << "Alice" << endl; } else if(y0 == 1 || y1 == 1) { cout << "Alice" << endl; } else if(s == "0101" || s == "1010" || s == "1100" || s == "0110" || s == "0011" || s == "1001") { cout << "Bob" << endl; } else { cout << ":(" << endl; } return 0; }
- 1
Information
- ID
- 6980
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- (None)
- # Submissions
- 34
- Accepted
- 2
- Uploaded By