Letter Picking

Created by LXC on Wed Aug 9 15:52:29 2023

https://codeforces.com/problemset/problem/1728/D

ranting: 1800

tag: constructive algorithms, dp, games, two pointers

problem

给出一个字符串，现在Alice和Bob又在博弈。

两个人都有一个空字符串。

二者轮流选择拿走当前字符串的最左端或这最右端，然后拼接在自己串的首部。

Alice先手。

二者都发挥最佳实力，最后谁的串字典序大谁就赢。

字符串长度n，n为偶数，且长度不超过2000

solution

经典博弈dp。但要注意的是这个每次拿字符要放在首位。

我们定义$f_{i,j}$为当前子字符串s[i...j]让Alice先手，最后的胜负情况。如果为-1则Alice赢，0则平局，1则Bob赢。

我们先让Alice动手一次，然后Bob接着动手一次。那么他们的选取组合有四种：

• Alice选择s[i]，Bob选择s[i+1]，子问题为$f_{i+2, j}$。其结果非0时，根据字典序的定义，s[i]和s[i+1]的大小关系已经不重要了，直接由$f_{i+2, j}$决定胜负；否则s[i]和s[i+1]的大小关系决定胜负。
• Alice选择s[i]，Bob选择s[j]，子问题为$f_{i+1, j-1}$。
• Alice选择s[j]，Bob选择s[j-1]，子问题为$f_{i, j-2}$。
• Alice选择s[j]，Bob选择s[i]，子问题为$f_{i+1, j-1}$。

Alice有两中选择，Bob在Alice选完后也有两次选择。

Alice想要赢，Bob不想Alice赢，所以Bob会选择较大的状态值，而Alice会选择较小的状态值。

状态转移看代码。

code

#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;

// 反向获取
void sol() {
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<int>> dp(
        n, vector<int>(n, -2));  // 面对s[l...r]，a是否会赢。-1a，0d，1b
    auto cmp = [](char x, char y) {
        if (x < y)
            return -1;
        if (x > y)
            return 1;
        return 0;
    };
    auto dfs = [&](auto self, int l, int r) {
        if (l > r)
            return 0;
        if (dp[l][r] != -2)
            return dp[l][r];
        int d1 = self(self, l + 2, r), d2 = self(self, l + 1, r - 1),
            d3 = self(self, l, r - 2);
        int c1 = cmp(s[l], s[l + 1]), c2 = cmp(s[l], s[r]),
            c3 = cmp(s[r], s[l]), c4 = cmp(s[r], s[r - 1]);
        c1 = d1 ? d1 : c1;
        c2 = d2 ? d2 : c2;
        c3 = d2 ? d2 : c3;
        c4 = d3 ? d3 : c4;
        return dp[l][r] = min(max(c1, c2), max(c3, c4));
    };
    int rt = dfs(dfs, 0, n - 1);
    if (rt == -1) {
        cout << "Alice\n";
    } else if (rt == 1) {
        cout << "Bob\n";
    } else {
        cout << "Draw\n";
    }
}
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;
}