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后的净差就可以了?答案是肯定的。

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

首先可以想到一个暴力的$O(n^3)$算法:枚举$\text{A}$,$\text{B}$的两个后缀,算出他们的最长公共前缀。

这样显然是对的,但是也显然可以用后缀数组优化。

阅读全文 »

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment