本文共 1462 字，大约阅读时间需要 4 分钟。

昨天晚上状态太差了== 其实这个题非常简单。 hard version需要以easy vesion作为基础

简单题意

现在bob和alice正在玩一个小游戏：

给你个字符串，当所有的0变成了1，那么游戏结束 现在你们有两个操作： 1.将0变成1，但是将会有一点的代价 2.将整个棋盘翻转（不用改变任何字符的意思），这个没有代价，但是条件是需要在字符串非回文的情况下才可以，而且不能连续使用反转的权利（BOB上次用了，你ALICE这次不能用） alice先手，请问双方都使用最佳策略，请输出获胜的一方。

思路

总体思路：保留最后使用反转棋盘的权利

简单版本是给你个一回文串：那么就可以直接记录0的位数，如果是偶数的情况alice每恢复一个位置（战术：破坏回文），那么bob都会恢复回文，最后一步，bob进行翻转，bob取胜 如果0的位数是奇数，那么alice恢复一个位置，就一定是能保证整个字符串是回文串，那么bob只能破坏回文，那么alice恢复回文，最后alice反转，alice获胜。 但是需要考虑的一个情况就是：如果只有一位为0，那么第二种战术失效，谁先手，谁就输掉游戏。 easy version代码

#include
   
    using namespace std;int main(){
   	int T;	cin>>T;	while(T--){
   		int n,t=0;		cin>>n;		getchar();		for(int i=1;i<=n;i++){
   			char c;			cin>>c;			if(c=='0')t++;		}		if(t%2==0||t==1){
   			cout<<"BOB"<
   

那么hard version就在easy version上增加了一点思维上的难度。

先要开一个数组，存一下，判断一下现在的字符串距离回文还需要多少步数。 因为如果不是回文，那么先手具有巨大优势，可以在回文前无数次反转该棋盘。 记录一下t是回文以后的需要反转0的个数 p是将本字符串变成回文需要反转的0的个数

那么记录a和b的相对大小即可，t=0的情况alice必赢

如果t=1，那么a的代价加一 如果t为偶数，那么在这个情况下，t为奇数对alice是有利的，所以如果b不等于0，那么b的代价先减一，（在马上要组成回文串的时候alice插一脚），最后bob的代价+2（因为输了） 如果b等于0，那么a的代价+2 反之，奇数的情况一定是b的代价+1（偶数到最后可以选择反转棋盘，所以就会有两个代价的优先程度，而奇数，先手要让棋盘回文（同时变成偶数，则要抵消一部分），所以只有一个代价的优先程度）

#include
   
    using namespace std;char c[2102100];int check(int n){
   	int res=0;	for(int i=1,j=n;i
    
     >T;	while(T--){
   		int n,t=0;		cin>>n;		getchar();		for(int i=1;i<=n;i++){
   			scanf("%c",c+i);			if(c[i]=='0')t++;		}		int p=check(n);		int a=0;		int b=p;		t-=p;		if(t==0){
   			cout<<"ALICE"<
     
      b)cout<<"BOB"<
     
    
   

转载地址：http://ksjrz.baihongyu.com/