#P6967. [2018年5月雅礼集训]游戏

    ID: 6798 传统题 3000ms 512MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-博弈论必胜/必败状态递推计算几何扫描线离线与分治离线查询数据结构有序集合贪心区间合并mex 计算构造与建模势能分析CF2600

[2018年5月雅礼集训]游戏

游戏(game)

题目描述

爱丽丝和鲍勃在玩一个游戏。游戏在二维整数平面上进行,平面上有一些障碍点。爱丽丝和鲍勃轮流移动同一个棋子,爱丽丝先移动,鲍勃后移动。每次移动可以将棋子向左或向下移动任意距离,即若棋子当前在(x,y)(x,y),则一次移动可以将棋子移动到(x−a,y)(x-a,y)或(x,y−a)(x,y-a),其中 a为任意正整数。但需要满足以下条件:

  1. 不能移动到障碍点上,移动时也不能穿过障碍点(即要求(x,y)(x,y)到(x−a,y)(x-a,y)之间所有的点都不是障碍点才能从(x,y)(x,y)移动到(x−a,y)(x-a,y))。

  2. 不能移动到横坐标或纵坐标为负数的点上。

如果轮到一名玩家移动时找不到任何一个合法的移动方案,则他输掉游戏。

爱丽丝和鲍勃在同一个棋盘上可能为进行多次游戏,但每次游戏棋子的起点不同。现在小 R 想知道对于某些起点,在爱丽丝和鲍勃都采用最优策略的情况下,谁能赢得游戏。

输入格式

从标准输入读入。第一行一个正整数 TT,表示数据组数。

对于每组数据:

第一行一个非负整数 nn,表示障碍点数量。

接下来 nn 行,每行两个非负整数 xi,yix_i,y_i,表示一个障碍点。

接下来一行一个正整数 qq,表示询问数量。

接下来 qq 行,每行两个非负整数 xi,yix_i,y_i,表示一个询问的起点。

输出格式

向标准输出写出。对于每组数据,输出 qq 行,输出第 i 个询问点为起点时的获胜者。(Alice 或 Bob)

输入样例

1
2
1 1
4 2
4
2 2
1 2
3 4
6 5

输出样例

Alice
Bob
Alice
Bob

数据范围与约定

对于 100%的数据,T≤5,n,q≤105,0≤xi,yi≤109T\le 5,n,q\le 10^{5},0\le x_{i},y_{i}\le 10^{9},输入的障碍点坐标互不相同。

数据编号 nn qq 坐标上界
0 ≤3\le3 5
1—2 ≤10\le10 30
3 0 ≤105\le10^5 10910^9
4—6 ≤20\le20
7—9 ≤105\le10^5