1718: CSP-S19 取石子（完善程序）

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,1≤b[i]≤64)。

如果先取石子的人必胜，那么输出 Win，否则输出 Loss。

提示：

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

status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。

试补全程序。

代码说明：

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

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

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

#include <cstdio>

#include<algorithm>

using namespace std;

const int maxn = 64;

int n, m;

int a[maxn], b[maxn];

unsigned long long status, trans;

bool win;

int main(){

   scanf("%d%d", &n, &m);

   for (int i = 0; i < n; ++i)

       scanf("%d%d", &a[i], &b[i]);

   for(int i = 0; i < n; ++i)

       for(int j = i + 1; j < n; ++j)

           if (a[i] > a[j]){

               swap(a[i], a[j]);

               swap(b[i], b[j]);

           }

   status = ①;

   trans = 0;

   for(int i = 1, j = 0; i <= m; ++i){

       while (j < n && ②){

           ③;

           ++j;

       }

       win = ④;

       ⑤;

   }

   puts(win ? "Win" : "Loss");

   return 0;

}

1.①处应填（ )

A. 0

B. ~0ull

C. ~0ull^1

D. 1

2.②处应填（ )

A. a[j] < i

B. a[j] == i

C. a[j] !=i

D. a[j]>1

3.③处应填（ )

A. trans |=1ull << (b[j] - 1)

B. status |=1ull << (b[j] - 1)

C. status +=1ull << (b[j] - 1)

D. trans +=1ull << (b[j] - 1)

4.④处应填（ )

A. ~status| trans

B. status & trans

C. status | trans

D. ~status & trans

5.⑤处应填（ )

A. trans =status | trans ^ win

B. status = trans >> 1 ^ win

C. trans =status ^ trans | win

D. status = status << 1 ^ win