#PQJ2602x15048. QOJ 2602_15048

    ID: 2846 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SNOI 2018树状数组

QOJ 2602_15048

2018 陕西省青少年信息学(计算机)奥林匹克集训队试题2 2018 年4 月22 日 区间取数游戏 题目描述 这是一道送分题 Alice 和Bob 在玩一个游戏。游戏是这样的: 给定N 个区间,第i 个区间的范围是l[i]~r[i](包含边界)。 Alice 和Bob 轮流操作(Alice 先手)。 每一次操作,操作方可以选择一个未被删除的区间i,然后把所有满足: 1. 区间i 包含区间j。 且未被删除的区间j 全部删掉。谁不能选,则输掉游戏。 现在,给你N 以及这N 个区间,请判断,在最优决策下,是Alice 胜还是Bob 胜,为 了防止随机输出结果的代码,本题多组数据。 测试数据保证区间和区间只存在包含和不相交两种关系 并且保证所有l[i],r[i]互不相等 送分的关键提示: 给你一棵树,每次在树上删一条边,把远离叶子那一端的节点全部删掉,不能操作者败, 有如下定理: 叶子节点的SG 值为0,中间节点的SG 值为它的所有子节点的SG 值加1 后的异或和。 输入格式 第一行输入T(T<=10),表示T 组数据。 接下来T 组数据,每组数据第一行是N,表示区间个数。 接下来N 行,每行两个正整数l[i],ri,表示第i 个区间的范围。 输出格式 对于每组数据,输出一个结果,如果Alice 胜利,输出”Alice”,否则输出”Bob”(不含 引号)。 输入样例 1 2 1 4 2 3 输出样例 Alice 数据范围 Case N l[i],r[i] 0 10 <=1000000007 1 2 100 3 4 1000 5 6 50000 7 8 9