Alice and Bob

前往 算竞题解 分类 || 前往 算竞模板 分类

原题链接

Alice and Bob 2023“钉耙编程”中国大学生算法设计超级联赛（6）

Alice and Bob 2023杭电多校 补题

Alice and Bob 2023杭电多校 Virtual Judge

简明题意

Alice 和 Bob 玩游戏，给定一个长度为 nn 的数组 aa。每次操作，将数组截断分为两部分，并且保留求和较大的部分；如果两部分求和相等，保留左半部分。Alice 先手，双方轮流对数组操作，最终无法操作者败，双方都想获胜。不仅如此，必胜者想要最后留下最大的数字，必败者想要最后留下最小的数字。问：两者足够聪明，Alice 和 Bob 谁将获胜，并且最终剩下的数字是什么？

多组测试数据，n≤3000n \le 3000 ，∑n≤10000\sum{n} \le 10000 。

解题思路

状态转移方程

博弈论通常可以分为三种：dpdp 胜负态转移，SGSG 函数转移，SGSG 函数推结论，以及各种奇奇怪怪的博弈题。这道题不仅要我们求出胜负态，还要求我们求最终剩下的数字，似乎用意很明显，想要卡掉结论，那么我们可以尝试考虑 dpdp 。

我们使用 dpdp 数组保存博弈的状态，dp[l][r]=(win,  point)dp[l][r] = (win,~~point) 表示剩余区间为 a[l..r]a[l..r] 时最终的胜负状态 winwin 和最终剩下的点数 pointpoint ，那么很容易得到状态转移方程：

win[l][r]={false,  l=rany(anyi∈[l+1,pos+1]!win[i][r],  anyi∈[pos+1,r−1]!win[l][i]),  l≠rwin[l][r] = \left\{ \begin{array}{ll} false & ,~~l = r \\ \text{any}\left( \underset{ i\in[l+1,pos+1] }{\text{any}}!win[i][r],~~ \underset{ i\in[pos+1,r-1] }{\text{any}}!win[l][i] \right) & ,~~l \neq r \\ \end{array} \right.

point[l][r]={a[l],  l=rmax⁡(max⁡i∈[l+1,pos+1]!win[i][r]point[i][r],  max⁡i∈[pos+1,r−1]!win[l][i]point[l][i]),  all(l≠r,  win[l][r])min⁡(min⁡i∈[l+1,pos+1]win[i][r]point[i][r],  min⁡i∈[pos+1,r−1]win[l][i]point[l][i]),  all(l≠r,  !win[l][r])point[l][r] = \left\{ \begin{array}{ll} a[l] & ,~~l = r \\ \max\left( \overset{ !win[i][r] }{\underset{ i\in[l+1,pos+1] }{\max}}point[i][r],~~ \overset{ !win[l][i] }{\underset{ i\in[pos+1,r-1] }{\max}}point[l][i] \right) & ,~~ \text{all}\left( l \neq r,~~ win[l][r] \right) \\ \min\left( \overset{ win[i][r] }{\underset{ i\in[l+1,pos+1] }{\min}}point[i][r],~~ \overset{ win[l][i] }{\underset{ i\in[pos+1,r-1] }{\min}}point[l][i] \right) & ,~~ \text{all}\left( l \neq r,~~ !win[l][r] \right) \\ \end{array} \right.

方程中的 pospos 是 pos[l][r]pos[l][r] 的简写，其定义如下：

∀k∈[l,  pos[l][r]],∑i=lka[i]<∑i=k+1ra[i]∀k∈[pos[l][r]+1,  r],∑i=1ka[i]≥∑i=k+1ea[i]\begin{array}{ll} \forall k \in [l,~~pos[l][r]], & \sum_{i=l}^{k}{a[i]} < \sum_{i=k+1}^{r}{a[i]} \\ \forall k \in [pos[l][r]+1,~~r], & \sum_{i=1}^{k}{a[i]} \ge \sum_{i=k+1}^{e}{a[i]} \\ \end{array}

因为 ∑i=lka[i]−∑i=k+1ra[i]\sum_{i=l}^{k}{a[i]} - \sum_{i=k+1}^{r}{a[i]} 满足单调性，所以 pos[l][r]pos[l][r] 一定存在。又因为 pos[l][r]pos[l][r] 也满足一定的单调性（假设 ll 不变，pospos 随 rr 增长而增长），所以可以使用双指针 O(n2)O(n^2) 预处理 pospos 数组。

上面的 dpdp（winwin 和 pointpoint）式子表示，pospos 将剩余区间 a[l..r]a[l..r] 分割成了两个部分，如果选择任何小于等于 pospos 的位置 kk 分割，可以得到区间 a[k+1..r]a[k+1..r]，否则得到区间 a[l..k]a[l..k]。那么 winwin 状态就表示为子状态有任何非 winwin 状态，pointpoint 状态表示为所有相反子状态的最大或最小值。

优化 DP

上面的这个状态转移方程总的时间复杂度为 O(n3)O(n^3) ，我们现在要考虑优化它。

因为我们需要动态维护区间 min⋅maxmin·max ，单调队列可以做到将时间复杂度优化到 O(n2)O(n^2) 。我们之前已经说明了，当固定 ll 时，pospos 是单调的；同理，固定 rr 时，pospos 也是单调的。同时，在做区间 dpdp 的过程中，如果考虑相同的 ll 边界，rr 和 pospos 满足相同的单调性；另一边同理。这意味着，考虑相同的 ll 边界，我们需要动态维护的 [pos+1,r−1][pos+1,r-1] 区间的两个边界同时满足单调增长，使得我们在做区间 dpdp 的过程中，需要求的区间 min⋅maxmin·max 满足滑动窗口模型；另一边同理。

不过可以预见，由于我们需要动态维护向后和向前的 min⋅maxmin·max ，每步需要维护 44 个单调队列，这道题常数起飞。

代码

下面的代码是正确的，只是卡常被卡的 SSSS 的，我修了好久没修过去。但是思路还是清楚的，大概看下。

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
// Alice and Bob
// Module Version 230418
// Powered by GreatLiangpi
#ifdef ONLINE_JUDGE
#define TEST 1  // Test Switch
#else
// #define TEST 1
#define LOCAL 1  // Debug Switch
#endif
#ifndef LOCAL
#define TEST 1
#endif
#include <bits/stdc++.h>
#define int int64_t
#ifdef TEST
#pragma GCC optimize(2, "inline")  // Optimization Switch
// #pragma GCC optimize(3, "Ofast", "inline")  // Optimization Switch
#define endl '\n'
#endif
#ifdef LOCAL
#define endl " **\n"
#endif
#define tomax(x, y) x = max(x, (y))
#define tomin(x, y) x = min(x, (y))
using namespace std;
#ifdef TEST
const int MAX = 3005;
#else
#ifdef LOCAL
const int MAX = 3005;
#endif
#endif
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1000000007;
int call_count = 0;

int n;
int32_t a[MAX];
pair<bool, int32_t> dp[MAX][MAX];  // {必胜, 最优数字}
int32_t pos[MAX][MAX];
struct HUM {
    int left, right;
    int head, tail;
    pair<int32_t, int32_t> que[MAX];
    // deque<pair<int, int>> que;
    bool empty() { return head == tail; }
    pair<int, int> front() { return que[head]; }
    pair<int, int> back() { return que[tail - 1]; }
    void push_back(const pair<int, int> &x) { que[tail++] = x; }
    void pop_front() { head++; }
    void pop_back() { tail--; }
};
HUM que_left_min[MAX];
HUM que_left_max[MAX];
HUM que_right_min[MAX];
HUM que_right_max[MAX];

#define init_que(q, l, r) (q.left = l, q.right = r, q.head = 0, q.tail = 0)

void init() {
    for (int i = 0; i < n; i++) {
        init_que(que_left_min[i], -1, -1);
        init_que(que_left_max[i], -1, -1);
        init_que(que_right_min[i], n, n);
        init_que(que_right_max[i], n, n);
    }
}

void move_left_min(int idx, int l, int r) {
    HUM &que = que_left_min[idx];
    int &left = que.left;
    int &right = que.right;
    for (int i = right + 1; i <= r; i++) {
        if (not dp[idx][i].first) continue;
        while (not que.empty() and que.back().second > dp[idx][i].second)
            que.pop_back();
        que.push_back({i, dp[idx][i].second});
    }
    for (int i = left; i < l; i++)
        if (not que.empty() and que.front().first == i)
            que.pop_front();
    left = l;
    right = r;
}

int query_left_min(int idx) {
    HUM &que = que_left_min[idx];
    if (que.empty())
        return INF;
    return que.front().second;
}

void move_left_max(int idx, int l, int r) {
    HUM &que = que_left_max[idx];
    int &left = que.left;
    int &right = que.right;
    for (int i = right + 1; i <= r; i++) {
        if (dp[idx][i].first) continue;
        while (not que.empty() and que.back().second < dp[idx][i].second)
            que.pop_back();
        que.push_back({i, dp[idx][i].second});
    }
    for (int i = left; i < l; i++)
        if (not que.empty() and que.front().first == i)
            que.pop_front();
    left = l;
    right = r;
}

int query_left_max(int idx) {
    HUM &que = que_left_max[idx];
    if (que.empty())
        return -INF - 1;
    return que.front().second;
}

void move_right_min(int idx, int l, int r) {
    HUM &que = que_right_min[idx];
    int &left = que.left;
    int &right = que.right;
    for (int i = left - 1; i >= l; i--) {
        if (not dp[i][idx].first) continue;
        while (not que.empty() and que.back().second > dp[i][idx].second)
            que.pop_back();
        que.push_back({i, dp[i][idx].second});
    }
    for (int i = right; i > r; i--)
        if (not que.empty() and que.front().first == i)
            que.pop_front();
    left = l;
    right = r;
}

int query_right_min(int idx) {
    HUM &que = que_right_min[idx];
    if (que.empty())
        return INF;
    return que.front().second;
}

void move_right_max(int idx, int l, int r) {
    HUM &que = que_right_max[idx];
    int &left = que.left;
    int &right = que.right;
    for (int i = left - 1; i >= l; i--) {
        if (dp[i][idx].first) continue;
        while (not que.empty() and que.back().second < dp[i][idx].second)
            que.pop_back();
        que.push_back({i, dp[i][idx].second});
    }
    for (int i = right; i > r; i--)
        if (not que.empty() and que.front().first == i)
            que.pop_front();
    left = l;
    right = r;
}

int query_right_max(int idx) {
    HUM &que = que_right_max[idx];
    if (que.empty())
        return -INF - 1;
    return que.front().second;
}

// #define BRUTE  // 暴力代码开关

void solve() {
    cin >> n;
    init();
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int l = 0; l < n; l++) {
        int s = 0, ss = 0, p = l - 1;
        for (int r = l; r < n; r++) {
            ss += a[r];
            while ((s + a[p + 1]) * 2 < ss) {
                p++;
                s += a[p];
            }
            pos[l][r] = p;
        }
    }
    for (int l = 0; l < n; l++) {
        dp[l][l] = {false, a[l]};
    }
    for (int k = 2; k <= n; k++) {
        for (int l = 0; l <= n - k; l++) {
            int r = l + k - 1;
            int pos = ::pos[l][r];
#ifdef BRUTE // 这是暴力代码
            bool win = false;
            for (int i = pos + 1; i <= r - 1; i++)
                if (not dp[l][i].first)
                    win = true;
            for (int i = l + 1; i <= pos + 1; i++)
                if (not dp[i][r].first)
                    win = true;
            int point = 0;
            if (win) {
                point = -INF - 1;
                for (int i = pos + 1; i <= r - 1; i++)
                    if (not dp[l][i].first)
                        tomax(point, dp[l][i].second);
                for (int i = l + 1; i <= pos + 1; i++)
                    if (not dp[i][r].first)
                        tomax(point, dp[i][r].second);
            } else {
                point = INF;
                for (int i = pos + 1; i <= r - 1; i++)
                    tomin(point, dp[l][i].second);
                for (int i = l + 1; i <= pos + 1; i++)
                    tomin(point, dp[i][r].second);
            }
            dp[l][r] = {win, point};
#else  // 这是优化代码
            move_left_min(l, pos + 1, r - 1);
            move_left_max(l, pos + 1, r - 1);
            move_right_min(r, l + 1, pos + 1);
            move_right_max(r, l + 1, pos + 1);
            int max_ = max(query_left_max(l), query_right_max(r));
            if (max_ <= -INF-1) {
                dp[l][r] = {false, min(query_left_min(l), query_right_min(r))};
            } else {
                dp[l][r] = {true, max_};
            }
#endif
        }
    }
    cout << (dp[0][n - 1].first ? "Alice" : "Bob") << ' ' << dp[0][n - 1].second << endl;
}

int32_t main() {
#ifdef TEST
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef LOCAL
    freopen("8.in", "r", stdin);
    freopen("out.txt", "w", stdout);
    clock_t start_time = clock();
#endif
    cout << fixed << setprecision(2);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

#ifdef LOCAL
    cout << "Used " << call_count << " Function Calls." << endl;
    cout << "Used " << (int)(clock() - start_time) << " Microseconds of Time." << endl;
#endif
    return 0;
}