CSP-S 2019 第一轮 第41题：完善程序（第 20 题）第 3 空

题目

2. （取石子）

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

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

接下来 $n$ 行。第 $i$ 行有两个正整数 $a[i]$ 和 $b[i]$。$(1 \le a[i] \le 10^7,1 \le b[i] \le 64)$。

如果先取石子的人必胜，那么输出 $\texttt{Win}$，否则输出 $\texttt{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;
}

③处应填（	)

选项

• A. trans |=1ull << (b[j] - 1)
• B. status |=1ull << (b[j] - 1)
• C. status +=1ull << (b[j] - 1)
• D. trans +=1ull << (b[j] - 1)

答案

A

题解

选 A：trans |= 1ull << (b[j] - 1)。

trans 用二进制位记录可用的取石子规则：第 \(b[j]-1\) 位为 1，表示可以取走 \(b[j]\) 个石子（最低位编号为 0）。

当第 j 条规则满足条件时，需要把对应位设为 1：

``cpp trans |= 1ull << (b[j] - 1); ``

其中，1ull << (b[j] - 1) 生成只有目标位为 1 的数，|= 将这一位设为 1，并保留其他位。

不能选 D 的 +=，因为多条规则可能有相同的 b[j]。例如两条规则都允许取 3 个石子，对应掩码都是 100₂：

• 按位或：100 | 100 = 100，正确保留“可以取 3 个”的信息。
• 相加：100 + 100 = 1000，发生进位，错误地变成“可以取 4 个”。

B、C 修改的是胜负状态 status，也不符合此处添加规则的用途。