F Christmas Game

題意：

給一棵n個節點樹，每個點上都有權值，兩個人輪流操作，每次可以將一個點的權值給他的父親節點，（父親節點與當前點的深度差必須為k），當有一方不能操作時即為輸掉。問依次以n個點為根的情況下，先手能否贏

題解：

博弈論
我第一反應是尼姆博弈
我們把節點相對于根的深度分為奇數和偶數
我們這里說的步數是指一個節點上的所能走的步數，因為每次走的長度是固定的（必須向上走深度為k）
如果把一些權值從一個偶數步移動到奇數步，那么對面可以重復一樣的行為，這樣輸的一定是先手（因為后手可以模仿先手）
所以先手想贏必須走奇數步，換句話說偶數步不會對比賽結果有影響可以舍棄
奇數步是如何定義的呢？我們剛才說了和k有很大的關系，如果當前節點x的深度為dep，x的奇偶性是dep/x(向下取整)
我們現在拿到所有奇數步的結果怎么判斷勝負？
經典博弈問題NIM游戲
a1⊕a2⊕…⊕an不為零時，當前玩家有一個獲勝策略。
總結一下：
如果奇數步上所有值的xorsum不為零，則先手獲勝獲勝策略。

代碼：

我一開始寫的dfs直接暴力超時了

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=1e5+8; vector<int>edge[maxn]; int a[maxn]; int root; int dep[maxn]; int cnt=0; int x=0; int n,k; inline void dfs(int fa,int now){dep[now]=dep[fa]+1;if((dep[now]/k)&1)x^=a[now];for(int i=0;i<edge[now].size();i++){int v=edge[now][i];if(v!=fa)dfs(now,v);} } //void solve(int now){ // int x=0; // int y=0; // int i,j=2*k; // int last=k; // for(i=k;i<=n;i+=k) // { // for(j=last+1;j<=i;j++) // { // for(int k=1;k<=n;k++) // if(a[j]==k) // { // // } // } // last=i; // } //// for(int i=k+1;i<=cnt;y++,i++) //// { //// for(int j=1;j<=n;j++) //// if(a[j]==i) //// { //// if(y&1) //// { //// x^=a[j]; //// } //// else //// { //// continue; //// } //// } //// } //} int main() {//cin>>n>>k;n=read();k=read();for(int i=1;i<n;i++){int u,v;u=read();v=read();//cin>>u>>v;edge[u].push_back(v);edge[v].push_back(u);}for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){root=i;x=0;memset(dep,0,sizeof(dep));cnt=0;dep[0]=-1;dfs(0,root);if(x==0)cout<<0<<" ";else cout<<1<<" ";}return 0; }

然后我在想簡化的話就不能對每個點跑一次dfs，跑一次+換根是不是可以？然后我看了看別人的代碼。。。沒看啥意思

#include <cstdio> #include <vector> using namespace std; vector<int> mp[100005]; int n,k; int a[100005]; int dp[100005][45]; int ans[100005][45]; // void dfs(int x,int fa) {dp[x][0]=a[x];for(int i=0;i<mp[x].size();i++)if(mp[x][i]!=fa){dfs(mp[x][i],x);for(int j=0;j<2*k;j++)//mp[x][i]是x的第i個子節點 dp[x][j]^=dp[mp[x][i]][(j+2*k-1)%(2*k)];} } void dfss(int x,int fa) {for(int i=0;i<mp[x].size();i++)if(mp[x][i]!=fa){for(int j=0;j<2*k;j++){//mp[x][i]是x的第i個子節點 ans[mp[x][i]][j]=(ans[x][(j+2*k-1)%(2*k)] ^ dp[mp[x][i]][(j+2*k-2)%(2*k)] ^ dp[mp[x][i]][j]);} dfss(mp[x][i],x);} } int main() {int u,v,now;scanf("%d%d",&n,&k);for(int i=0;i<n-1;i++){scanf("%d%d",&u,&v);mp[u].push_back(v);mp[v].push_back(u);}for(int i=1;i<=n;i++)scanf("%d",&a[i]);dfs(1,0);for(int i=0;i<2*k;i++)ans[1][i]=dp[1][i];dfss(1,0);for(int i=1;i<=n;i++){now=0;for(int j=k;j<2*k;j++)now^=ans[i][j];if(now)now=1;if(i!=n)printf("%d ",now);else printf("%d\n",now);}return 0; }

總結

以上是生活随笔為你收集整理的F Christmas Game的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。