2022.7.18 模拟赛题解
草莓蛋糕
赛时写了两个 log 的线段树分治+平衡树上二分的做法,没有前途(毕竟线段树分治就一个 log 了,O(1) 计算不太可能)。
“时间分治不了就序列分治”
但有个 max,不太好合并两边的贡献。
发现 等价于 。
于是设 a 类的权值为 ,b 类的权值为 ,这样通过权值的大小就可以知道贡献取哪边。
可以将原序列按照权值排序,这样统计来自两个分治区间的贡献十分容易(因为如果知道哪边选 a 哪边选 b 贡献取什么可以确定,只需要分别维护 的最小值)。
线段树维护即可。
code: http://47.92.197.167:5283/submission/102034
矩阵补全
FWT 实际上就是把每个数替换成一个满足某个条件的集合的和,这样按位乘起来就相当于在这两个集合中任选一个数,而 iFWT 就是将这些乘积放回到对应的位置上去,于是 FWT 实际上是可以给每一位进行不同的操作的(或,异或,与),可以认为在对这一位进行操作的时候所有高位的影响已经排除,只按这一位操作就能达到期望的结果。