完善程序-2

  1. (取石子)

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

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

提示:

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

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

试补全程序。

代码说明:

~ 表示二进制补码运算符,它将每个二进制位的 0 变为 1、1 变为 0;
而 ^ 表示二进制异或运算符,它将两个参与运算的数中的每个对应的二进制位一一进行比较,若两个二进制位相同,则运算结果的对应二进制位为 0 ,反之为 1。
ull 标识符表示它前面的数字是 unsigned long long 类型。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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;
}	
Scroll to Top