6239: [2019CSP提高程序阅读2]:取石子

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

 Alice和Bob两个人在玩取石子游戏,他们制定了n条取石子的规则,第i条规则为:如果剩余的石子个数大于等于a[i]且大于等于b[i],那么她们可以取走b[i]个石子。他们轮流取石子。如果轮到某个人取石子,而她们无法按照任何规则取走石子,那么他就输了,一开始石子有m个。请问先取石子的人是否有必胜的方法?

输入格式

输入第一行有两个正整数,分别为规则个数n(1≤n≤64),以及石子个数m(≤10^7)。

输出格式

接下来n行。第i行有两个正整数a[i]和b[i]。(1≤a[i]≤10^7,1b[i]≤64)如果先取石子的人必胜,那么输出“Win”,否则输出“Loss”

提示:

可以使用动态规划解决这个问题。由于b[i]不超过,所以可以使用位无符号整数去压缩必要的状态。

Status是胜负状态的二进制压缩,trans是状态转移的二进制压缩。



试补全程序。



代码说明:

“~”表示二进制补码运算符,它将每个二进制位的0变成1、1变为0;



而“^”表示二进制异或运算符,它将两个参与运算的数重的每个对应的二进制位一一进行比较,若两个二进制位相同,则运算结果的对应二进制位为0,反之为1。



U11标识符表示它前面的数字是unsigned long long 类型。



输入样例 复制

2 10
2 4
3 5

输出样例 复制

Loss