巧克力棒

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1423 字
10轮游戏。每轮盒中有若干根巧克力棒，两人轮
一本通
练习
正文

/*
原题：T1667「一本通 6.7 练习 2」巧克力棒
题意：10 轮游戏。每轮盒中有若干根巧克力棒，两人轮流：要么从盒中取出若干根，
要么把一根已取出的棒吃掉正整数长度；无法操作者输。TBL 先手，问胜负。
思路：把"取出若干根"看成新开一个尼姆局面。取出的棒若异或和为 0，则对手面对必败局面，
而对手再取棒只会再开新局面，仍可用同样的办法应对。于是关键化为：
只要存在一个非空子集，其长度异或和为 0（即这些长度在 GF(2) 上线性相关），先手就必胜；
若全体长度线性无关，则无论取哪一组异或都非 0，先手必败。
用线性基逐个插入即可判定：插入时出现"约简为 0"即说明线性相关。
复杂度：每轮 O(N·log L)，空间 O(log L)
易错点：1) 判据是"存在子集异或为 0"，不是"总异或为 0"，要用线性基检测相关性；
2) 输出约定为：先手胜输出 YES，先手败输出 NO（题面"若胜则输出 NO"一句系抓取错乱，
以样例为准：长度集合线性无关时先手败，输出 NO）；
3) 每轮 2 行输入，先读根数再读各根长度，共 10 轮。
*/
#include <bits/stdc++.h>
using namespace std;
const int BITS=31;
bool dependent(const vector<long long>& v){
    // 线性基：插入时若能被已有基线性表示，则说明存在非空子集异或和为 0
    long long basis[BITS];
    for(int i=0;i<BITS;i++){
        basis[i]=0;
    }
    for(long long x:v){
        long long cur=x;
        for(int i=BITS-1;i>=0;i--){
            if((cur>>i)&1LL){
                if(basis[i]==0){
                    basis[i]=cur;
                    break;
                }
                cur^=basis[i];
            }
        }
        if(cur==0){
            return true;
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long N;
    while(cin>>N){
        vector<long long> a(N);
        for(long long i=0;i<N;i++){
            cin>>a[i];
        }
        bool win=dependent(a);
        if(win){
            cout<<"YES\n";
        }else{
            cout<<"NO\n";
        }
    }
    return 0;
}
巧克力棒

正文

一本通·提高篇的其它内容
