0%

数据结构专题复习

列一下一些有点意思/自己降智思考了很长时间的题。

水の数列:

直接离线维护一下答案,然后rmq维护一下区间max,目前好像被卡空间了?毒瘤

XR-1 逛森林:优化建图没写过,先放一放

NOI 2010 超级钢琴:套路题,优先队列维护可选决策最大值

POI 2015 LOG:

不会,看了策略之后会了。

策略就是设定一个“每轮选择的”表格,然后往表格里面填数,并且一行不能填同一个位置的数。

考虑>=s的数,这些数肯定可以放进去s个,也就是每行(c个)的前num个放完这些数之后都被占了。

考虑<s的数,易证都可以造成贡献,那就看(c-num)*s是否不比small_sum大就可以了,数据结构随便维护一下。


USACO17 JAN Promotion Counting P

无脑线段树合并的就8说了

考虑我们如何计算一个子树内的答案,直接计算好像有点麻烦。

回顾一下我们如何快速计算一个东西的祖先的答案,大概长这个亚子:

1
2
3
4
def dfs (int u)
update(u)
for (v in g[u]) dfs(v)
reset(u)

那子树也是异曲同工,只不过要做一点点修改。

因为你仔细思考一下发现:诶,我是不是只需要维护dfs前和dfs后的净差就可以了?答案是肯定的。

所以代码也很好写,大概长这样,感觉想懂了之后很好理解,比线段树合并好写/快多了