博弈论-CF1728D
先明确一些事情：
- 对于 str[l, r], 若 A 先手，最后的结果是确定的。（这里的字符串长度为偶数）
现在，我们设 \(f_{l, r}\) 表示对于字符串 [l, r], A 先手的博弈结果。最后要输出的答案则是 \(f_{1, n}\).
我们考虑 \(f_{l, r}\) 怎么用已求出来的小区间答案推出来（也可以说是他的转移方程）：
A 先手，A 在决策时会这么想：（下面的 1 代表选首位，2 代表选末尾）
假设 A 选 1：B 选 1 时游戏结果是 tmp1, B 选 2 时游戏结果是 tmp2. B 一定会选 tmp1 和 tmp2 中对他有利的一个（对 B 来说，优先级是 赢 > 平局 > 输，这里我们简记 min1 为对 B 来说有利的那一个），所以在 A 选 1 的情况下，最后的游戏结果是 min1.
假设 A 选 2：同上面一样的分析，设 A 选 2 时，最后的游戏结果为 min2.
综上，\(f_{l, r}\) 为 min1 和 min2 中对 A 有利的一个。
点击查看代码
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int t;
char a[2001];
int k[2001][2001];//[l, r]: A先手, 游戏最后结果
int main(){
scanf("%d", &t);
while(t--){
scanf("%s", a);
int len = strlen(a);
for(int i = 0; i < 2001; i++){
memset(k[i], 0, sizeof(k[i]));
}
for(int i = 2; i <= len; i+=2){
for(int j = 0; j + i - 1 < len; j++){
//k[j][j + i - 1]
if(i == 2){
if(a[j] == a[j + 1]) k[j][j + 1] = 0;
else k[j][j + 1] = 1;
}
else{
//1, 1
int tmp1 = 2;
if(k[j + 2][j + i - 1] == 0){
if(a[j] < a[j + 1]) tmp1 = 1;
if(a[j] == a[j + 1]) tmp1 = 0;
}
if(k[j + 2][j + i - 1] == 1){
tmp1 = 1;
}
//1, 2
int tmp2 = 2;
if(k[j + 1][j + i - 2] == 0){
if(a[j] < a[j + i - 1]) tmp2 = 1;
if(a[j] == a[j + i - 1]) tmp2 = 0;
}
if(k[j + 1][j + i - 2] == 1){
tmp2 = 1;
}
//2, 1
int tmp3 = 2;
if(k[j + 1][j + i - 2] == 0){
if(a[j] > a[j + i - 1]) tmp3 = 1;
if(a[j] == a[j + i - 1]) tmp3 = 0;
}
if(k[j + 1][j + i - 2] == 1){
tmp3 = 1;
}
//2, 2
int tmp4 = 2;
if(k[j][j + i - 3] == 0){
if(a[j + i - 1] < a[j + i - 2]) tmp4 = 1;
if(a[j + i - 1] == a[j + i - 2]) tmp4 = 0;
}
if(k[j][j + i - 3] == 1){
tmp4 = 1;
}
int min1, min2;
//1:
if(tmp1 == 1 && tmp2 == 1) min1 = 1;
else min1 = 0;
//2:
if(tmp3 == 1 && tmp4 == 1) min2 = 1;
else min2 = 0;
if(min1 == 0 && min2 == 0) k[j][j + i - 1] = 0;
else k[j][j + i - 1] = 1;
}
}
}
if(k[0][len - 1] == 0) cout << "Draw" << endl;
else cout << "Alice" << endl;
}
return 0;
}