CSP-S 2019 初赛 取石子

题面：

代码：

// 一般，我们用bool f[64]，f[i]表示有i个石子，先手是否有必胜策略
// 状态图，必败状态 <--->  必胜状态
// 对于i个石子，存在规则j，使得
// f[i - b[j]]=false 必败状态  -----通过规则j，转移到--->   f[i]=true必胜状态 
// i可以从很多的状态[i-b[j]]转移过来，只要有一个是必败的就可以，所以用或运算

// b[i]<=64，最多64个石子，仅需考虑f[i-1, ..., i-64]的取值即可
// 将此部分状态进行压缩
// status用于记录i个石子，i-1, ...,i-64 是否存在必胜策略
// 二进制右起第j位的值，表示[i-j]个石子是否有必胜策略

#include <bits/stdc++.h>

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]);

    // 以a[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]);
            }

    // 状态初始化
    // 0000000000           0ull
    // 1111111111          ~0ull
    // 1111111110          ~0ull ^ 1 表示0个石子的情况，先手必败
    status = ~0ull ^ 1;    
    trans = 0;

    for(int i = 1, j = 0; i <= m; ++i){
        while (j < n && a[j] == i){         
            // 枚举到符合条件的规则
            // 把规则j维护到trans里，二进制新增 用或 |
            trans |= 1ull << (b[j] - 1);    
            ++j;
        }

        //  status         表示先手必胜的状态
        // ~status         表示先手必败的状态，从先手必败的状态转移过来(状态图)
        // ~status & trans 与一下，二进制&，都是1，就才是1
        // 结果是 1，或者是 0
        win = ~status & trans;               

        // 把当下状态的结果，添加到status的右起第一位
        // i个石子，必胜或者必定，添加到status
        status = (status << 1) ^ win;   
    }

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

    return 0;
}   

/*
输入：
1 1 
1 1
输出：
Win

输入：
1 2
1 1
输出：
Loss

*/