Family Photos
由 $a_1 - b_2 >= a_2 - b_1$ 知 $a_1 + b_1 >= a_2 + b_2$,对于其它情况分类讨论即可。
对于小$B$,他每次都只能选正序排序后,每个二元组中较小的哪个。
当 $a_1 - b_2 < a_2 - b_1$,
由于每对照片只有取了第一张才能取第二张,所以如果 $a_1 - b_2 > 0$,小$A$还是会取第一张,
同理我们也可以分析出 $b_1 > a_2$ 时,就算会亏,小$A$也会在小$B$之后选,
反之,双方就宁可游戏结束也不选了,因为两边都不赚。
所以本题的关键在于只要有一方想玩,那就得玩下去。
01 on Tree
由于从根往下考虑难以消除后效性,我们很$trick$的从子节点开始合并,并向上传递答案。
往对于两棵子树$a,b$记录它们包含的$0,1$个数,邻项计算将它们哪一个排在前面会产生的逆序对对数 $a_1 * b_0 < a_0 * b_1$,
推式子可得有$\frac{a1}{a0} < \frac{b1}{b0}$,维护一个优先队列,用并查集将子节点和父节点合并即可。
嘉年华奖券
不难发现这个抽奖的过程中,工作人员必然会取中位数来最小化当前轮次的奖励。
稍微化简一下,就有 $\sum_{\frac{n}{2}+1<=i<=n} a_i - \sum_{1<=i<=\frac{n}{2}} a_i$,其中 $a$ 序列正序排序。
简单构造后,用双指针维护一下就可以了。
Shik and Copying String
用队列来维护当前折线的每个拐点即可,其中靠近队首表示靠下的拐点,反之是靠上的拐点。
蔬菜
好复杂的题目谔,费用流模型,考虑时光倒流,问题变为 :
每天都会加入一些菜(原来会变质的菜),菜可以无限期保存,但每天最多出售 $m$ 个菜,问最大总收益。
这样建出来的图只有源边有权值,其余边的权值均为 $0$。
在同一种菜中,出售那颗的获益都是一样的,故使用堆维护各种菜即可。当售空时,则从堆中取出。
当加入菜时,若原来这种菜售空,则将其加入堆。这需要维护售空且有持续输入的菜的集合。
序列
至少有 $L$ 个下标相同,即至多有 $K-L$ 个下标不同,依旧是模拟费用流,
费用流模型,建图后发现除了和 $S,T$ 直接相连的边以外,其他边的边权均为 $0$。
我们用堆维护五种转移,取$max$即可。
JAS
本题可以抽象模型,两点间的简单路径必然存在点分树的 $LCA$,
问题相当于求原树最浅的一个点分树深度。
我们用二进制状压维护$i$的子树内所有不满足条件的$d$值,合并两棵子树时,选所有满足条件的最小的 $d_i$ 即可,这可以通过位运算计算。
IIIDX
对于权值互不相等的情况,有一个非常简单的思路:
对于一棵树,把最小的丢给根,然后把长度为第一个孩子的子树大小的一段后缀丢给它递归构造,再取一段长度为第二个孩子的子树大小的一段丢给第二个孩子递归构造,以此类推。
对于有权值相等的情况,
由于遍历顺序是层序遍历,而我们的方式是前序遍历,所以会出问题,
所以我们找到最大的可能权值在排好序的数组中的最小位置,让 $u$ 选择这个位置,然后在 $u$ 后面预留出 $siz_u$ 个位置。
可以维护数组的前缀最小值 $f_i$,线段树上二分即可实现。
Minimizing Edges P
好题,
时间不够了,之后再补吧