Alice 和 Bob 玩游戏,给定一个长度为 n 的数组 a。每次操作,将数组截断分为两部分,并且保留求和较大的部分;如果两部分求和相等,保留左半部分。Alice 先手,双方轮流对数组操作,最终无法操作者败,双方都想获胜。不仅如此,必胜者想要最后留下最大的数字,必败者想要最后留下最小的数字。问:两者足够聪明,Alice 和 Bob 谁将获胜,并且最终剩下的数字是什么?
voidinit(){ 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); } }
voidmove_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; }
voidmove_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; }
voidmove_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; }
voidmove_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; }
voidsolve(){ 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; }