开发做游戏的网站,石碣网站建设,计算机网站建设招聘,加盟型网站建设F Christmas Game
题意#xff1a;
给一棵n个节点树#xff0c;每个点上都有权值#xff0c;两个人轮流操作#xff0c;每次可以将一个点的权值给他的父亲节点#xff0c;#xff08;父亲节点与当前点的深度差必须为k#xff09;#xff0c;当有一方不能操作时即为输…F Christmas Game
题意
给一棵n个节点树每个点上都有权值两个人轮流操作每次可以将一个点的权值给他的父亲节点父亲节点与当前点的深度差必须为k当有一方不能操作时即为输掉。问依次以n个点为根的情况下先手能否赢
题解
博弈论 我第一反应是尼姆博弈 我们把节点相对于根的深度分为奇数和偶数 我们这里说的步数是指一个节点上的所能走的步数因为每次走的长度是固定的必须向上走深度为k 如果把一些权值从一个偶数步移动到奇数步那么对面可以重复一样的行为这样输的一定是先手因为后手可以模仿先手 所以先手想赢必须走奇数步换句话说偶数步不会对比赛结果有影响可以舍弃 奇数步是如何定义的呢我们刚才说了和k有很大的关系如果当前节点x的深度为depx的奇偶性是dep/x(向下取整) 我们现在拿到所有奇数步的结果怎么判断胜负 经典博弈问题NIM游戏 a1⊕a2⊕…⊕an不为零时当前玩家有一个获胜策略。 总结一下 如果奇数步上所有值的xorsum不为零则先手获胜获胜策略。
代码
我一开始写的dfs直接暴力超时了
#includebits/stdc.h
typedef long long ll;
using namespace std;
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn1e58;
vectorintedge[maxn];
int a[maxn];
int root;
int dep[maxn];
int cnt0;
int x0;
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 i0;iedge[now].size();i){int vedge[now][i];if(v!fa)dfs(now,v);}
}
//void solve(int now){
// int x0;
// int y0;
// int i,j2*k;
// int lastk;
// for(ik;in;ik)
// {
// for(jlast1;ji;j)
// {
// for(int k1;kn;k)
// if(a[j]k)
// {
//
// }
// }
// lasti;
// }
//// for(int ik1;icnt;y,i)
//// {
//// for(int j1;jn;j)
//// if(a[j]i)
//// {
//// if(y1)
//// {
//// x^a[j];
//// }
//// else
//// {
//// continue;
//// }
//// }
//// }
//}
int main()
{//cinnk;nread();kread();for(int i1;in;i){int u,v;uread();vread();//cinuv;edge[u].push_back(v);edge[v].push_back(u);}for(int i1;in;i)cina[i];for(int i1;in;i){rooti;x0;memset(dep,0,sizeof(dep));cnt0;dep[0]-1;dfs(0,root);if(x0)cout0 ;else cout1 ;}return 0;
}
然后我在想简化的话就不能对每个点跑一次dfs跑一次换根是不是可以然后我看了看别人的代码。。。没看啥意思
#include cstdio
#include vector
using namespace std;
vectorint 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 i0;imp[x].size();i)if(mp[x][i]!fa){dfs(mp[x][i],x);for(int j0;j2*k;j)//mp[x][i]是x的第i个子节点 dp[x][j]^dp[mp[x][i]][(j2*k-1)%(2*k)];}
}
void dfss(int x,int fa)
{for(int i0;imp[x].size();i)if(mp[x][i]!fa){for(int j0;j2*k;j){//mp[x][i]是x的第i个子节点 ans[mp[x][i]][j](ans[x][(j2*k-1)%(2*k)] ^ dp[mp[x][i]][(j2*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 i0;in-1;i){scanf(%d%d,u,v);mp[u].push_back(v);mp[v].push_back(u);}for(int i1;in;i)scanf(%d,a[i]);dfs(1,0);for(int i0;i2*k;i)ans[1][i]dp[1][i];dfss(1,0);for(int i1;in;i){now0;for(int jk;j2*k;j)now^ans[i][j];if(now)now1;if(i!n)printf(%d ,now);else printf(%d\n,now);}return 0;
}
