前言
泻药, 吉司机线段树学不动
冷静的利用时间已经变成了不冷静的浪费时间, 干脆打两道 \(\rm{C}\) 冷静一下
思路
看到 \(\rm{MEX}\) 了, 无敌 , 看到 \(2, 1, 0\) 了, 无敌
但是应该不是这个方向
先转化题意
\(\textrm{Alice, Bob}\) 轮流进行游戏, \(\textrm{Alice}\) 每次取出数组中的一个数放进结果数组中, \(\textrm{Bob}\) 每次删除数组中的一个数, \(\textrm{Alice}\) 希望最大化 \(\rm{MEX}\) , 而 \(\textrm{Bob}\) 希望最小化, 求最终的游戏得分
好的也是抄了一遍题
首先玩一下样例, 你发现 \(\rm{Alice}\) 应当从小到大取数, 而 \(\rm{Bob}\) 也应当这样取来干扰 \(\rm{Alice}\) , 特别的是一种数只取一次
但是你发现显然这样是错的
给出一组 \(\rm{hack}\)
0 0 1 1 2
\(\mathcal{O} (n)\) 做法
按照我们的方法, \(\rm{Alice}\) 将会取到 \(0, 1\) , 最终答案为 \(2\)
但是你发现如果 \(\rm{Alice}\) 开局直接取 \(2\) , 后面也一定能取到 \(0, 1\) 答案更优
我们考虑形式化表示, 如果一个数出现次数 \(\geq 2\) 那么一定是取得到的, 我们最初还可以取一个出现次数为 \(1\) 的, 贪心的取最小的那个肯定是最优的
\(\mathcal{O} (n \log n)\) 做法
你发现能否取到是由单调性的, 考虑二分
那么如何判定是否能取到一个数?
同 \(\mathcal{O} (n)\) 算法的思想一样, 出现了超过一个 \(x\) 使得其出现次数小于 \(2\) 即为不合法
总结
一种博弈问题, 即你取一个, 我取一个, 一定可以通过对称取法取到个数 \(\geq 2\) 的数
然后就是对先手的处理
标签：每日,Alice,Game,textrm,mathcal,rm,Bob,MEX From： https://www.cnblogs.com/YzaCsp/p/18678554