牛牛的树行棋 题目描述 给定一棵树，树上每一个节点都有一枚棋子。 Alice 和 Bob 在这棵树上玩一个这样子的游戏 ： Alice 和 Bob 轮流操作，每次把一枚棋子移动到其子树内的节点（显然一枚棋子在叶子节点就不能移动了），不能移动的人算输。 问 Alice 先手是否有必胜策略，若先手必胜
展开全文
普通的nim游戏：有n堆石子，石子数a1，a2…，每次可以从一堆拿任意个石子，两个人拿，求先手是否赢 nim游戏结论： 1.求所有堆的石子数ai异或和xorsum，如果xorsum！=0，那么先手有必赢策略，否则没有 2.先手第一步应该怎么拿：从a1中拿a1-（a1^xorsum）个石子是a1变为a
展开全文
solution 求出每个点的sg函数，然后异或起来得到x，如果x为0那么就是先手必败，否则就是先手必胜。 如何求每个点sg函数？对于节点,,(i是j的祖先)。 对于第二问，也就是需要操作一步使得异或和为0。 如果我们把上的一个棋子挪到了上，那么的异或和就会变为，（v位于u的子树中）。也就是说我们要
展开全文
题目大意：给定一棵树，每个结点上都有一个棋子，牛牛和牛妹两个人每次选择任意一个结点的棋子，将棋子移动到该节点子树下的节点位置。(不可以不移动)牛牛先手，牛妹后手。现在假设双方都采用最优策略，请问牛牛能否赢。如果牛牛（先手）能够赢，请问牛牛第一步有多少种不同的必胜策略。我们认为两个策略是不同的，当且仅
展开全文
F、牛牛的树行棋 博弈论sg函数与dfs。前导知识sg函数：SG函数： 首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。 对于任意状态 x ， 定义
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
