# 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. 判定一个区间是否颜色全部为‘A’，我们用前缀和判定，如果suma[R]-sum[L-1]==R-L+1，则全为‘A’； ‘B’同理。
2. 然后对于当前区间，我们考虑两种子情况：两种子情况都不利，则不利；有一个有利，则有利。 （博弈的思想

——参考自：传送门

### 代码

StatusAccepted
Time62ms
Memory9200kB
Length1299
#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 星期三