2-11 Eat the chip
思路:题意可知,a从下往上走,b从上往下走,我们可以思考一个问题,在某一个回合,如果a和b在同一列中(a是Alice,b是Bob),一方怎么走,另外一方就跟着这一方走,所以同一列的时候是该回合后手的必胜态,先手的必败态。于是可以递推:如果在走到边界的时候有机会仍然保持b在a的上方,那么有机会分出胜负,因为一方不可以走出边界,所以ya-yb一定会发生变化,直到xa-xb = 0
import sys
#file I/O
#sys.stdin = open('input.txt', 'r')
#sys.stdout = open('output.txt', 'w')
#faster I/O
input = sys.stdin.readline
sys.setrecursionlimit(30)
def print(ans='',end = '\n'):
sys.stdout.write(str(ans) + end)
def solve() -> None:
n,m,xa,ya,xb,yb = map(int,input().split())
flag = bool((xb - xa) % 2)
if not flag:
winner = "Bob"
if xa >= xb:
win = False
elif ya == yb:
win = True
else:
if yb > ya:
n_turn = yb - 1
else:
n_turn = m - yb
win = xb - 2 * n_turn >= xa
else:
winner = "Alice"
xa += 1
ya += 0 if yb - ya == 0 else 1 if yb - ya > 0 else -1
if xa > xb:
win = False
elif ya == yb:
win = True
else:
if ya < yb :
n_turn = m - ya
else:
n_turn = ya - 1
win = xb - 2 * n_turn >= xa
print(winner if win else "Draw")
T = int(input())
for _ in range(T):
solve()
标签:思维,xa,--,win,yb,xb,else,ya,Codeforce
From: https://www.cnblogs.com/howardsblog/p/18013393