URAL2104 Game with a Strip（前缀和/博弈/dfs）

Game with a Strip

Time limit: 2.0 second
Memory limit: 64 MB

There is a strip 1 × n with two sides. Each square of the strip (their total amount is 2n, n squares on each side) is painted in one of two colors (let’s call them A and B). Alice and Bob play a game. Alice makes the first turn. On each turn, a player can bend the strip in half with the fold passing on the divisions of the squares (i.e. the turn is possible only if the strip has an even length). Bending the strip can be done either inwards or outwards. If the strip has become completely one color after the next turn, then the winner is the player whose color is it (A refers to Alice, B to Bob). If the current player has no legal moves, but no one has won, the game ends with a draw.

Who will win if both players play optimally? This means that each player tries to win; if it is not possible, to achieve a draw.

Input

The first line contains an integer n that is the length of the strip ($1 ≤ n ≤ 5 · 10^5$).

The next two lines contain two strings of letters “A” and “B” with lengths n, describing two sides of the strip. The letters that are under each other, correspond to the different sides of the same square.

Output

If Alice wins, output “Alice”. If Bob wins, output “Bob”. If the game ends with a draw, output “Draw”.

Samples

input

4
BBAA
BABB
3
AAA
BBB
2
AA
BB

output

Bob
Draw
Alice

Notes

In the first example, Alice starts the game with the strip BBAA/BABB. After her turn she can get the strip BB/AA or BB/AB. In both cases, Bob can win by getting the strip B/B.

In the second example, Alice can’t make even the first turn, so the result is a draw.

In the third example, Alice wins by the first move, getting the stripe A/A from the strip AA/BB.

链接

https://cn.vjudge.net/problem/URAL-2104

题意

长度为1*n的卡片，有正反两面，每面都有n块A和B两种颜色，现在每次可以向里折或者向外折，长度减半，如果长度为奇数那么就不能在折了。现在Alice和Bob开始玩游戏，Alice先开始折，如果下一次卡片正反面都为A那么Alice赢，都为B那么Bob赢，如果折到卡片不能再折了还没分出胜负就是平局，假定均采取最佳策略，问最后谁赢。

题解

翻折等效于覆盖：即[1,2N]翻折后本来应该是[N,1]或者[2N,N+1]；但是我们实际上不能模拟翻转操作（复杂度有点高，虽然好像NlogN也可以过）。这里，我们考虑翻折操作等效于覆盖操作后为[1,N]或者[N+1,2N]。
判定一个区间是否颜色全部为‘A’，我们用前缀和判定，如果suma[R]-sum[L-1]==R-L+1，则全为‘A’； ‘B’同理。
然后对于当前区间，我们考虑两种子情况：两种子情况都不利，则不利；有一个有利，则有利。（博弈的思想
——参考自：传送门

用三种状态1、2、3分别表示Alice赢，Bob赢，平局；把正反面转化为左右两个区间。

代码

Status	Accepted
Time	62ms
Memory	9200kB
Length	1299

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1000010;
char s[maxn];
int suma[maxn], sumb[maxn];

int dfs(int l, int r, int status)
{
    if ((r - l + 1) % 2 != 0) // 奇数，不可翻折
        return 3;
    if (suma[r] - suma[l - 1] == (r - l + 1)) // 全为A
        return 1;
    if (sumb[r] - sumb[l - 1] == (r - l + 1)) // 全为B
        return 2;
    int mid = (l + r) >> 1;
    int left = dfs(l, mid, 3 - status);
    int right = dfs(mid + 1, r, 3 - status);
    if (left == status || right == status) // 至少一个必胜
        return status;
    if (left == right && left == 3 - status) // 均为必败
        return 3 - status;
    return 3; // 平局
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        scanf("%s", s + 1);
        scanf("%s", s + n + 1);
        memset(suma, 0, sizeof(suma));
        memset(sumb, 0, sizeof(sumb));
        for (int i = 1; i <= 2 * n; ++i) // 前缀和
        {
            suma[i] += (suma[i - 1] + (s[i] == 'A' ? 1 : 0));
            sumb[i] += (sumb[i - 1] + (s[i] == 'B' ? 1 : 0));
        }
        int ans = dfs(1, 2*n, 1);
        if (ans == 1)
            printf("Alice\n");
        else if (ans == 2)
            printf("Bob\n");
        else
            printf("Draw\n");
    }
    return 0;
}

The end.
2018-08-29 星期三