@zzzc18 2022-09-10T18:38:51.000000Z 字数 2732 阅读 312

# Educational Codeforces Round 135 D. Letter Picking

Codeforces 区间DP

Alice and Bob are playing a game. Initially, they are given a non-empty string s, consisting of lowercase Latin letters. The length of the string is even. Each player also has a string of their own, initially empty.

Alice starts, then they alternate moves. In one move, a player takes either the first or the last letter of the string s, removes it from s and prepends (adds to the beginning) it to their own string.

The game ends when the string s becomes empty. The winner is the player with a lexicographically smaller string. If the players' strings are equal, then it's a draw.

A string a is lexicographically smaller than a string b if there exists such position i that aj=bj for all j

What is the result of the game if both players play optimally (e. g. both players try to win; if they can't, then try to draw)?

Input
The first line contains a single integer t (1≤t≤1000) — the number of testcases.

Each testcase consists of a single line — a non-empty string s, consisting of lowercase Latin letters. The length of the string s is even.

The total length of the strings over all testcases doesn't exceed 2000.

Output
For each testcase, print the result of the game if both players play optimally. If Alice wins, print "Alice". If Bob wins, print "Bob". If it's a draw, print "Draw".

Example
input

2forcesabba

output

AliceDraw

Note
One of the possible games Alice and Bob can play in the first testcase:

Alice picks the first letter in s: s="orces", a="f", b="";
Bob picks the last letter in s: s="orce", a="f", b="s";
Alice picks the last letter in s: s="orc", a="ef", b="s";
Bob picks the first letter in s: s="rc", a="ef", b="os";
Alice picks the last letter in s: s="r", a="cef", b="os";
Bob picks the remaining letter in s: s="", a="cef", b="ros".
Alice wins because "cef" < "ros". Neither of the players follows any strategy in this particular example game, so it doesn't show that Alice wins if both play optimally.

f[l][r]表示区间[l,r)上的胜负情况，若为true，则Alice赢，否则平局。

#include <bits/stdc++.h>using std::deque;using std::greater;using std::make_pair;using std::pair;using std::priority_queue;using std::sort;using std::vector;const int MAXN = 2E3 + 7;bool f[MAXN][MAXN];char str[MAXN];void solve() {    scanf("%s", str);    int n = strlen(str);    for (int length = 0; length <= n; length += 2) {        for (int l = 0; l < n; l++) {            int r = l + length;            if (r > n) {                break;            }            if (r == l) {                f[l][r] = 0;                continue;            }            bool vlr =                f[l + 1][r - 1] == 0 ? str[l] < str[r - 1] : f[l + 1][r - 1];            bool vrl =                f[l + 1][r - 1] == 0 ? str[l] > str[r - 1] : f[l + 1][r - 1];            ;            bool vll = f[l + 2][r] == 0 ? str[l] < str[l + 1] : f[l + 2][r];            bool vrr = f[l][r - 2] == 0 ? str[r - 1] < str[r - 2] : f[l][r - 2];            f[l][r] = (vlr & vll) | (vrl & vrr);        }    }    if (f[0][n])        puts("Alice");    else        puts("Draw");}int main() {    // freopen("in.in", "r", stdin);    // freopen("out.out", "w", stdout);    int kase;    scanf("%d", &kase);    while (kase--) {        solve();    }    return 0;    return 0;}

• 私有
• 公开
• 删除