10
ACGO巅峰赛#28
本题解包含三道竞赛题：
题目编号 题目标题 难度 T1 Alice的石子合并 普及/提高- T3 Alice的神秘二叉树 普及/提高- T4 Alice的棋盘游戏 普及/提高-
T1 ALICE的石子合并
题目大意
求出合并 n−1n-1n−1 堆石子的最小代价。
解题思路
对于每一堆石子，不管往右还是往左合并，都不会影响其他堆石子的属性 (ai,bi)(a_i,b_i)(ai ,bi )，如果往左合并，则代价为 aia_iai ，如果往右合并，则代价为 bib_ibi ，所以每堆石子的最小代价为 min(ai,bi)min(a_i,b_i)min(ai ,bi )。但第一堆石子和最后一堆石子只能往一个方向合并，所以第一堆的最小代价为 b1b_1b1 ，最后一堆的最小代价为 ana_nan 。一共 nnn 堆石子，合并最小代价前 n−1n-1n−1 堆石子，即去掉最小代价最大的一堆石子，其他 n−1n-1n−1 堆石子的最小代价和即为最小总代价。
参考代码
T3 ALICE的神秘二叉树
题目大意
给出一棵二叉树的中序遍历和层序遍历，求出先序遍历。
解题思路
假设 inxin_xinx 为根节点，则先序遍历的结果为 inx+[in1,in2,...,inx−2,inx−1]in_x+[in_1,in_2,...,in_{x-2},in_{x-1}]inx +[in1 ,in2 ,...,inx−2 ,inx−1 ] 的先序遍历 +[inx+1,inx+2,...,inn−1,inn]+[in_{x+1},in_{x+2},...,in_{n-1},in_n]+[inx+1 ,inx+2 ,...,inn−1 ,inn ] 的先序遍历。
针对 [in1,in2,...,inx−2,inx−1][in_1,in_2,...,in_{x-2},in_{x-1}][in1 ,in2 ,...,inx−2 ,inx−1 ]，假设 inkin_kink 为根节点，先序遍历的结果为 ink+[in1,in2,...,ink−2,ink−1]in_k+[in_1,in_2,...,in_{k-2},in_{k-1}]ink +[in1 ,in2 ,...,ink−2 ,ink−1 ] 的先序遍历 +[ink+1,ink+2,...,inx−1,inx]+[in_{k+1},in_{k+2},...,in_{x-1},in_x]+[ink+1
,ink+2 ,...,inx−1 ,inx ] 的先序遍历。
针对 [inx+1,inx+2,...,inn−1,inn][in_{x+1},in_{x+2},...,in_{n-1},in_n][inx+1 ,inx+2 ,...,inn−1 ,inn ]，假设 inqin_qinq 为根节点，先序遍历的结果为 inq+[inx+1,inx+2,...,inq−2,inq−1]in_q+[in_{x+1},in_{x+2},...,in_{q-2},in_{q-1}]inq +[inx+1 ,inx+2 ,...,inq−2 ,inq−1 ] 的先序遍历
+[inq+1,inq+2,...,inn−1,inn]+[in_{q+1},in_{q+2},...,in_{n-1},in_n]+[inq+1 ,inq+2 ,...,inn−1 ,inn ] 的先序遍历。
所以，只要知道某个区间 [inl,inl+1,...,inr−1,inr][in_l,in_{l+1},...,in_{r-1},in_{r}][inl ,inl+1 ,...,inr−1 ,inr ] 的根节点，就可以递归求出这个区间的先序遍历。
因为层序遍历的顺序为从根到叶、自左到右，所以区间 [inl,inl+1,...,inr−1,inr][in_l,in_{l+1},...,in_{r-1},in_{r}][inl ,inl+1 ,...,inr−1 ,inr ] 的根节点就是在 levellevellevel 序列中出现最早的键。
idxidxidx 记录每个键在 levellevellevel 序列中的下标，每次查询的时间复杂度为 O(log n)O(log\ n)O(log n)。
参考代码
T4 ALICE的棋盘游戏
题目大意
判断先手是否必胜，并输出首回合必胜的走法。
解题思路
为了方便讲解，假设 isw(i,j,k)isw(i,j,k)isw(i,j,k) 指在 (i,j)(i,j)(i,j) 位置，以前走过 kkk 步时，先手是否能赢。111 表示能，000 表示不能。
求 isw(x,y,z)isw(x,y,z)isw(x,y,z)：
* 如果 2∣k2\mid k2∣k，即下一步是先手走，那么只要 isw(x+1,y,z+1),isw(x−1,y,z+1),isw(x,y−1,z+1),isw(x,y+1,z+1)isw(x+1,y,z+1),isw(x-1,y,z+1),isw(x,y-1,z+1),isw(x,y+1,z+1)isw(x+1,y,z+1),isw(x−1,y,z+1),isw(x,y−1,z+1),isw(x,y+1,z+1) 其中一个为 111，就可以判定 isw(x,y,z)=1isw(x,y,z)=1isw(x,y,z)=1，因为先手走到这一步时可以选择能赢的走法，如果一个能赢的走法都没有，即
isw(x+1,y,z+1)=0,isw(x−1,y,z+1)=0,isw(x,y−1,z+1)=0,isw(x,y+1,z+1)=0isw(x+1,y,z+1)=0,isw(x-1,y,z+1)=0,isw(x,y-1,z+1)=0,isw(x,y+1,z+1)=0isw(x+1,y,z+1)=0,isw(x−1,y,z+1)=0,isw(x,y−1,z+1)=0,isw(x,y+1,z+1)=0，不管怎么走都是自己输，那么 isw(x,y,z)=0isw(x,y,z)=0isw(x,y,z)=0。
* 如果 2∤k2\nmid k2∤k，即下一步是后手走，那么只要 isw(x+1,y,z+1),isw(x−1,y,z+1),isw(x,y−1,z+1),isw(x,y+1,z+1)isw(x+1,y,z+1),isw(x-1,y,z+1),isw(x,y-1,z+1),isw(x,y+1,z+1)isw(x+1,y,z+1),isw(x−1,y,z+1),isw(x,y−1,z+1),isw(x,y+1,z+1) 其中一个为 000，就可以判定
isw(x,y,z)=0isw(x,y,z)=0isw(x,y,z)=0，因为后手走到这一步时可以选择先手输的走法，如果一个先手输的走法都没有，即 isw(x+1,y,z+1)=1,isw(x−1,y,z+1)=1,isw(x,y−1,z+1)=1,isw(x,y+1,z+1)=1isw(x+1,y,z+1)=1,isw(x-1,y,z+1)=1,isw(x,y-1,z+1)=1,isw(x,y+1,z+1)=1isw(x+1,y,z+1)=1,isw(x−1,y,z+1)=1,isw(x,y−1,z+1)=1,isw(x,y+1,z+1)=1，不管怎么走都是先手赢，那么
isw(x,y,z)=0isw(x,y,z)=0isw(x,y,z)=0。
求出 isw(sx,sy,0)isw(sx,sy,0)isw(sx,sy,0) 即可。
参考代码
(不是引战
有帮助，赞一个