CSAcademy Beta Round #3 a-game

时间:2023-02-01 23:53:07

题目连接 a-game

大意:有一个只包含A和B的字符串,两个人分别取这个串的子串,但是每一次取不能与之前取到过的子串有交集,最后谁取到的所有串中A的总数量少的判为胜。如果一样,则为平手。

给出这样的字符串,判断结果。

分析:考虑只包含A字母的情况,推一下可以得出奇数个A先手必败,偶数个A两者可以平手。再考虑原问题的情况,先去取包含A的串显然是很傻的做法,故而在最优策略下,两者应该在先取完所有的B,再去取A。继续思考,可以发现,被A字母隔开的每一串连续的B其实是独立的。因为在还有B的情况下去取跨过了中间隔开的A的既有A又有B的串不是明智的选择。综合只有A的情况一起考虑,发现如果A有偶数个,则其实怎么取B都无所谓了,取完B后无论先手是否转为接下来的后手还是维持先手,都只能平手。但是如果A有奇数个,因为在只有A的情况下,先手必败,所以在最优策略下,原来的先手一定要想办法将自己在取完B只有A时转为后手。再看看那一串串的B,发现其实这个就是Nim游戏,如果先手能够赢了B字母所代表的Nim,则可以在没有B,还剩下奇数个A的情况下将自己转为这时的后手,最终获胜。

 

所以算法就是,统计A字母的数量,偶数直接输出平局。分离出所有的B串,做它们的异或和,如果不为0,则游戏的先手必胜,否则必败。

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <string>
 5 #include <string.h>
 6 #include <stdio.h>
 7 #include <math.h>
 8 #include <queue>
 9 #include <stack>
10 #include <map>
11 #include <set>
12 using namespace std;
13 const int N=123456;
14 char s[N];
15 int main () {
16     int n;
17     scanf("%d",&n);
18     scanf("%s",s+1);
19     vector<int> v;
20     int cnt=0;
21     int ca=0;
22     for (int i=1;i<=n;i++) {
23         if (s[i]=='A'){
24             ca++;
25             if (s[i-1]=='B')
26                 v.push_back(cnt);
27             cnt=0;
28         }
29         else cnt++;
30     }
31     if (cnt!=0);
32         v.push_back(cnt);
33     int sum=0;
34     for (int i=0;i<v.size();i++){
35         sum^=v[i];
36     }
37     if (ca%2==0)
38         puts("-1");
39     else if (sum)
40         puts("A");
41     else
42         puts("B");
43     return 0;
44 }