Palindrome Game (hard version)

发表于 分类于 ，

    **简易版和繁难版的唯一区别是，简易版中的给定字符串 $s$ 最初是一个回文字符串，而繁难版中的这一条件并不总是正确的。

    回文字符串是指从左到右和从右到左读法相同的字符串。例如，"101101 "是一个回文字符串，而 "0101 "不是。

    爱丽丝和鲍勃正在一个长度为 $n$ 的字符串 $s$ 上玩游戏，这个字符串由字符 "0 "和 "1 "组成。双方轮流玩，爱丽丝先玩。

    在每个回合中，玩家可以执行以下操作之一：

    1. 选择任意 $i$ ( $1 \le i \le n$ )，其中 $s[i] =$ 为'0'，并将 $s[i]$ 改为'1'。0"，并将 $s[i]$ 改为 "1"。支付 1 美元。

    2. 反转整个字符串，支付 0 美元。只有当字符串目前***不是回文字符串，并且上一次操作不是反转时，才允许进行此操作。也就是说，如果爱丽丝反转了字符串，那么鲍勃下一步就不能反转，反之亦然。

    反转字符串是指将字符串中的字母从最后一个重新排序到第一个。例如，"01001 "在反转后会变成 "10010"。

    当字符串中的每个字符都变成 "1 "时，游戏结束。到此为止，花费最少的玩家获胜，如果双方花费相同，则为平局。如果双方都以最佳方式进行游戏，输出结果是 Alice 赢、Bob 赢还是平局。

Palindrome Game (hard version)

Created by LXC on Tue May 7 23:11:15 2024

https://codeforces.com/problemset/problem/1527/B2

ranting: 1900

tag: constructive algorithms, games

problem

**简易版和繁难版的唯一区别是，简易版中的给定字符串 $s$ 最初是一个回文字符串，而繁难版中的这一条件并不总是正确的。

回文字符串是指从左到右和从右到左读法相同的字符串。例如，”101101 “是一个回文字符串，而 “0101 “不是。

爱丽丝和鲍勃正在一个长度为 $n$ 的字符串 $s$ 上玩游戏，这个字符串由字符 “0 “和 “1 “组成。双方轮流玩，爱丽丝先玩。

在每个回合中，玩家可以执行以下操作之一：

  1. 选择任意 $i$ ( $1 \le i \le n$ )，其中 $s[i] =$ 为’0’，并将 $s[i]$ 改为’1’。0”，并将 $s[i]$ 改为 “1”。支付 1 美元。
  2. 反转整个字符串，支付 0 美元。只有当字符串目前***不是回文字符串，并且上一次操作不是反转时，才允许进行此操作。也就是说，如果爱丽丝反转了字符串，那么鲍勃下一步就不能反转，反之亦然。

反转字符串是指将字符串中的字母从最后一个重新排序到第一个。例如，”01001 “在反转后会变成 “10010”。

当字符串中的每个字符都变成 “1 “时，游戏结束。到此为止，花费最少的玩家获胜，如果双方花费相同，则为平局。如果双方都以最佳方式进行游戏，输出结果是 Alice 赢、Bob 赢还是平局。

solution

分析面对回文串时，先手与后手所需要的钱数。

然后分析非回文串，先手可以通过反转操作，不断的让后手付钱，最后让先手面对回文串，或让后手面对回文串。二者取最优。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    auto ans = [&](int u, int v) {
        // cout << u << " " << v << endl;
        if (u > v) cout << "BOB\n";
        else if (u < v) cout << "ALICE\n";
        else cout << "DRAW\n";
    };
    if (n%2) {
        int x = 0, y = 0, c = 0;
        if (s[n/2] == '0') c = 1;
        for (int i=0; i<n/2; i++) {
            if (s[i] != s[n-i-1]) x++;
            else if (s[i] == '0') y+=2;
        }
        // cout << "x: " << x << " y: " << y << " c: " << c << endl;
        int a = 0, b = 0;
        auto add = [&](int u, int v)->pair<int,int> { // 奇数回文，先手u，后手v
            if (c) {
                u += 1;
                v += y;
            } else {
                u += y;
                v += 0;
            }
            return pair<int,int>{u, v};
        };
        if (x == 0) {
            auto [u, v] = add(a, b);
            ans(u, v);
        } else {
            auto [v1, u1] = add(b+x-1, a+1);
            auto [u2, v2] = add(a, b+x);
            if (u1<v1) ans(u1, v1);
            else ans(u2, v2);
        }
    } else {
        int x = 0, y = 0, c = 0;
        if (s[n/2-1] == s[n/2] && s[n/2] == '0') c = 1;
        for (int i=0; i<n/2; i++) {
            if (s[i] != s[n-i-1]) x++;
        }
        for (int i=0; i<n/2-1; i++) {
            if (s[i] == s[n-i-1] && s[i] == '0') y+=2;
        }
        // cout << "x: " << x << " y: " << y << " c: " << c << endl;
        int a = 0, b = 0;
        auto add = [&](int u, int v)->pair<int,int> { // 偶数回文，先手u，后手v
            if (c) {
                if (y) {
                    u += y+1;
                    v += 1;
                } else {
                    u += 2;
                    v += 0;
                }
            } else {
                u += y;
                v += 0;
            }
            return pair<int,int>{u, v};
        };
        if (x == 0) {
            auto [u, v] = add(a, b);
            ans(u, v);
        } else {
            auto [v1, u1] = add(b+x-1, a+1);
            auto [u2, v2] = add(a, b+x);
            if (u1<v1) ans(u1, v1);
            else ans(u2, v2);
        }
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}