A. trade
暴力 dp, 复杂度 $O(n^2)$.
然后 70 分等死.
考试快结束的时候, 突发奇想.
快速改了滚动数组, 将第二维的上界设为 1000.
即只考虑同时存 1000 个货物, 然后突然过了大样例.
其实只是想多偷一点分, 然后就 A 了, 就非常偷税.
所以正解其实是基于堆操作的反悔贪心.
考试时确实想了这方面, 但没有构造出来合适的方法.
用一个小根堆来实现操作:
对于每一个货物,
如果当前货物价值不大于堆顶, 直接将当前货物入堆.
如果当前货物价值大于堆顶, 那么将堆顶买入并在当前卖出, 累加答案, 弹出堆顶, 并在堆中加入两个当前的货物.
设堆顶 / 当前货物价值分别为 $v_a$,$v_b$, 之后出现货物 $v_c$.
第一个货物的含义是: 可以在之后的操作中, 进行反悔操作, 不在 b 处卖出而在 c 处卖出, 那么新的贡献为 $v_c-v_b$, 与使 b 入堆相符合.
第二个货物的含义是: 当反悔操作进行后, 货物 b 被解放出来, 可以重新当作一个货物被买入.
然而这个贪心的前提是货物 a 一旦买入就不能反悔这个贪心原则是正确的.
可以发现如果在时刻 a 没有卖出货物时, 如果买入 a 有贡献一定更优.
B. sum
一些式子是显然的.
设 $(n,m)$ 为 n 行 m 列的答案.
那么 $(n,m)$ 可以快速地转移到 $(n,m+1)$,$(n,m-1)$,$(n+1,m)$.
移项之后 $(n,m)$ 转移到 $(n-1,m)$ 的式子也是简单的.
然后发现本题可以离线, 就可以莫队了.
很难想到, 维护区间问题的莫队在这里得到了这么巧妙的应用.
莫队算法常可以维护一些二维或多维改变量影响答案的问题.
其较小的曼哈顿距离生成树的确实很有用.
C. building
可以用并查集维护联通块的个数.
当合并两个不同的集合, 答案减少 1.
因为保证行或列的长度为 1, 不同矩形间边的个数是合法的.
给所有的建筑按 $x_1$ 排序, 当处理到横坐标 $x_1$ 时将这个建筑与其它建筑联通块合并.
开一些 $vector$, 表示这一行 / 这一列有哪些建筑块.
对于一个建筑块, 只在它的边界坐标上插入 $vector$.
在 $vector$ 上二分就可以保证只扫每个边一次, 所以复杂度是合法的.
来源: http://www.bubuko.com/infodetail-3230869.html