题目连接 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 }