題目鏈接：點擊查看

題目大意：給出 $n$ 個數(shù)字，現(xiàn)在要求將其構(gòu)造成一棵有根樹，使得博弈的后手必勝

博弈規(guī)則如下：兩人輪流操作，每次選擇一個點，然后將當(dāng)前點的部分（可以是全部）點權(quán)交付給其父節(jié)點

更具體的來說，每次選擇一個點 $x$，再選擇一個 $y$ 滿足 $a_x>=y>0$，執(zhí)行操作 $a_x?=y,a_{fa}+=y$

無法執(zhí)行操作的人失敗，問是否可以構(gòu)造

題目分析：考慮逐步分析

假設(shè)根節(jié)點的深度為 $0$，那么對于樹上的偶數(shù)節(jié)點來說實際上是無效的

因為假如先手對偶數(shù)節(jié)點操作，后手可以模仿先手進(jìn)行操作，局面不變

假如先手對奇數(shù)節(jié)點操作，因為實際執(zhí)行的操作是將奇數(shù)位置的數(shù)字扔到了偶數(shù)位置上，結(jié)合上面的結(jié)論，相當(dāng)于將奇數(shù)節(jié)點的數(shù)值直接扔掉了

到此為止就是一個裸的尼姆博奕了，問題轉(zhuǎn)換為了求出 $n$ 個數(shù)中是否存在著一個序列滿足異或和為 $0$，用線性基來實現(xiàn)就可以了

代碼：

// Problem: 焦糖布丁 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/17148/H // Memory Limit: 1048576 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; LL d[65]; bool add(LL x) {for(int i=60;i>=0;i--) {if((x>>i)&1) {if(d[i]) {x^=d[i];} else {d[i]=x;return true;}}}return false; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {memset(d,0,sizeof(d));int n;read(n);bool flag=false;for(int i=1;i<=n;i++) {LL x;read(x);if(!add(x)) {flag=true;}}puts(flag?"Yes":"No");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的牛客 - 焦糖布丁(线性基+博弈)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。