题库 信息学奥赛题库 题目列表 (取石子) Alice和Bob两个人在玩取石子游戏,他们制定...
组合题

(取石子) 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 类型。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

#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 (aa[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] >i
第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
题目信息
完善程序 初赛 2019年
-
正确率
0
评论
192
点击