题解 | 信息学奥赛一本通 巧克力棒

思路

博弈的拓展.第一步你必须取出一些巧克力棒.
如果你取出的巧克力棒函数值异或和不为0,你就死了.因为不管你吃巧克力还是再拿巧克力,对方都可以吃巧克力使异或和为0.
异或和为0的话情况就恰恰相反,你赢定了(当然前提是你足够聪明).
所以答案就要看是否存在异或和为0的子序列.复杂度为.

代码

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline void cmax( T &x, T y ){ x < y ? x = y : x; }
template<typename T> inline void cmin( T &x, T y ){ y < x ? x = y : x; }
#define getchar() ( p1 == p2 && ( p1 = bf, p2 = bf + fread( bf, 1, 1 << 21, stdin ), p1 == p2 ) ? EOF : *p1++ )
char bf[1 << 21], *p1(bf), *p2(bf);
template<typename T>
inline void read( T &x ){ char t(getchar()), flg(0); x = 0;
    for ( ; !isdigit(t); t = getchar() ) flg = t == '-';
    for ( ; isdigit(t); t = getchar() ) x = x * 10 + ( t & 15 );
    flg ? x = -x : x;
}

clock_t t_bg, t_ed;
int N, a[22];

signed main(){
    t_bg = clock();
    fp( T, 1, 10 ){
        read(N);
        fp( i, 0, N - 1 ) read(a[i]);
        int ans(1);
        fp( i, 1, (1 << N) - 1 ){
            ans = 0;
            fp( j, 0, N - 1 ) if ( i & ( 1 << j ) ) ans ^= a[j];
            if ( !ans ) break;
        } printf( ans ? "YES\n" : "NO\n" );
    }
    t_ed = clock();
    fprintf( stderr, "\n========info========\ntime : %.3f\n====================\n", (double)( t_ed - t_bg ) / CLOCKS_PER_SEC );
    return 0;
}