None

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

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

接下来 n 行。第i行有两个正整数 a[i]和 b[i]。1≤a[i]≤107,b[i]≤64

如果先取石子的人必胜,那么输出“Win”,否则输出“Loss”

提示:

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

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

代码说明:

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

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

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

试补全程序

① 处应填( )

A

0

B

~0ull

C

~0ull^1

D

1

赣ICP备20007335号-2