【Vijos——又是一年省选季之春分邀请赛】

2018年省选季vijos系列比赛第一场

开始于2018-03-24 18:00
结束于2018-03-24 23:00
共计三题

报名请移步: https://vijos.org/contest/5aa51237d3d8a1371223faba

3.24 14:14 比赛已经部署完毕，快告诉你身边的朋友们吧。
3.24 23:04 比赛已经结束感谢大家的参与，题目已经公开在了题库列表中。

题目简要分析：

第一题：
对于这种最大最小化的双人游戏，最基本的思路是分支定界的搜索，也就是alpha-beta剪枝，这就可以得到60分。
满分做法还需要用到启发式搜索，这里的启发式函数很容易找到：优先选取下一步获利最大（最小）的方案。
代码请参见 这一题的题解区 。

第二题：
这一题考察状态压缩动态规划，记 \(F[i][s]\) 表示 \(i\) 位数中状态是 \(s\) 的方案总数。
重点考虑 \(s\) 要记录什么，当然不需要记每一种数字的使用情况，只需要记有多少奇数被使用过了，以及里面有多少被用了偶数次，再者需要记录所有偶数中有多少用了奇数次就可以了（一个偶数如果没有被使用，它出现的次数依然是偶数——即0次）。这样 \(s\) 的状态总数大概不会超过70个。
将上述动态规划表示为矩阵乘法的形式，就可以快速解决这一题（等于是求一个矩阵A的幂次和）。

第三题：
注意到 \(2^{n-1}\times (n+1)\) 是答案的一个上界，所以不妨把每一个满足要求的数字都记为 \(2\) 的若干次幂乘上一个整数的形式。为了得到一个更大的数字，总是尝试将其中一个因子变成更大的因子（或者将1变成2，也就是再增加一个2）。所以若选择了一个目前最小的方案，则会额外增加不超过 \(\log n\) 个新的方案（注意需要去重）。
用小根堆来实现上面的操作，就可以解决这一题。