「Fortuna OJ」Apr 15 省选组 – 解题报告

A – 楼房搭建

首先这题的 \(\Theta(n^3)\) 是很好写的,如果要写到 \(\Theta(n^2)\) 的分,我们可以观察到 DP 的过程其实是一个做后缀 min 的过程,所以优化完毕(当然也可以线性规划,但是很难写)。

继续阅读「Fortuna OJ」Apr 15 省选组 – 解题报告

Yali 模拟赛 #1 – 解题报告

A – 神奇的位运算

想了半天,最后一看是离线来维护,直接吐血。

首先大概能想到用本质不同的异或和与区间异或和进行异或得到答案。因为这样可以把出现次数为奇数次的给过滤掉并得到最终的答案。考虑如何得到本质不同的区间异或和,一种方式是使用主席树进行维护,另一种方式是进行离线维护。我们可以在树状数组中维护本质不同的前缀异或:我们把每个数往尽可能近的地方塞,这个时候就需要用 map 来判断要不要移动。

继续阅读Yali 模拟赛 #1 – 解题报告