Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5462 --石子游戏
5462: 石子游戏
警告!
题目
状态
题解
题目描述
小明与小红正在一棵满二叉树(叶结点深度均相同,非叶结点均有两个儿子)上玩游戏。这棵满二叉树的高度为 $k$,第 $i$ 层有 $2^{i-1}$ 个结点,因此这棵树共有 $n$ 个结点。 树上的结点从 $1 \sim 2^k-1$ 进行编号,$1$ 号点为根结点,并且对于非叶结点 ,它的两个儿子分别为 $2i$ 与 $2i+1$. 游戏开始前每个结点上都放有一定数量的石子,$i$ 号点上的石子数量为 $a_i$.游戏开始后,小明和小红轮流行动,小明先手。当前行动的人需要先选择一个树中的结点 $u$ 并且要满足 $u$ 上还有石子。接下来,若 $u$ 是个叶子结点,则他需要彻底移除至少一个 $u$ 上的石子;若 $u$ 是个非叶结点,则他需要移除至少一个 $u$ 上的石子,并将这些石子移动到 的其中一个儿子上(一次操作不能分开移动,必须移动至同一个儿子)。无法操作者即为负。 假设 小明和小红都足够聪明,以最优策略玩这个游戏,请你求出 小明有多少种第一步的操作方式能够让 小明获胜。
输入
第一行一个整数 $T$ 表示数据组数。 每组数据第一行一个整数 $k$ 表示树高。 接下来 $k$ 行,第 $i$ 行 $2^{i-1}$ 个非负整数表示初始时第 $i$ 层结点上的石子数 $a_i$(按标号顺序给出)。
输出
样例输入输出
输入#1
复制
3 1 1 2 1 0 0 3 1 2 2 4 4 4 4
输出#1
复制
1 0 6
提示
对于 $30\%$ 的数据,$T = 1$,$k \leq 2$,$a_i \leq 5$。 对于 $60\%$ 的数据,$T \leq 5$,$k \leq 8$,$a_i \leq 10^5$。 对于 $100\%$ 的数据,$T \leq 10$,$1\leq k \leq 16$,$0\leq a_i \leq 10^6$。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
未评定
标签
博弈论
点击显示
if ($pr_flag) { ?>
递交数
1
已通过
1
} ;?>
通过率
100%
时间限制
1 秒
内存限制
128 MB
来源
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和