题目链接

题目大意

给你一个01串,先后手依次进行操作。操作有两种:

  1. 将序列中的一个0改成1,并付出1点代价。
  2. 翻转序列(当序列不为回文串时),并付出0点代价。翻转序列的前一步不能是翻转序列。

现在Alice先手进行操作,Bob后手进行操作。当整个序列变成全1串时,游戏结束。求解游戏结束时,两者中代价较小的一方。

输出先手胜/后手胜/平局。

解题思路

本题有一个前置的easy版本的题目(参考cf链接中的b1)即给出的01串必定是回文串

我们先考虑简单版本下的解决方法:

  1. 当给出全1串时,平局。
  2. 当给出给出的串只有一个0时,后手胜。
  3. 当给出的串长是偶数,后手胜。
  4. 当给出的串长是奇数且中间为1时,后手胜。
  5. 当给出的串长是奇数且中间为0时,先手胜。

下面给出上述结论的简易证明。

  1. 显然
  2. 若只有一个0,必定在串长为奇数的中间(因为回文串限制)。此时先手只能更改其为1,后手胜。
  3. 1001举例,先手只能修改,变为1101;此时后手可以翻转,而先手被迫再次修改1111。游戏结束,先手2分后手0分,后手胜。(复杂情况同理,不再赘述)
  4. 此时中间的1可以抹除。等同于偶数情况,后手胜。
  5. 先手改动中间的0为1,此时相当于4.中的情况,只是转变了先后手,原先的先手必胜。

未完待续。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e6+7;
int T;
int n,m,k;
char a[N];

signed main(){
    cin>>T;
    while(T--){
        cin>>n;
        cin>>a;
        int cnt=0;
        for(int i=0;i<n;i++){
            if(a[i]=='0'){
                cnt++;
            }
        }
        //cout<<cnt<<endl;
        if(cnt==0){
            cout<<"DRAW\n";
        }
        else if(cnt==1 || n%2==0){
            cout<<"BOB\n";
        }
        else if(n%2==1 && a[(n-1)/2]=='0'){
            cout<<"ALICE\n";
        }
        else{
            cout<<"BOB\n";
        }
    }
    return 0;
}
分类: 补题

0 条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注