这几天做的POI的题

正规、严谨、精妙。 -POI


发现POI(波兰信息学奥赛)的题都很有意思。于是开刷bzoj上的poi题目(按ac人数降序。。)。顺手写一写题解,加深印象。


BZOJ 1103 : [POI2007]大都市meg

给一棵树,每次可以把树上的一些边标记了,问一个点与根之间需要走多少没有标记的边。

这个可以把这颗树遍历得到一个dfs序每第一次经过一个点的时候记录为+1,第二次经过一个点的时候记录为-1,然后记录每个点第一次经过时在序列里的位置f[i]和第二次经过在序列里的位置l[i],对于查询(x)就是序列中一直到f[x]-1的前缀和,因为真正没走的那些边都+1 -1消掉了,只剩下真正要统计的边了。对于每次标记(a,b) 设a < b 就是序列里 f[b]的位置-1,l[b]的位置+1,就相当于消掉了这条边。另外这道题得手写栈dfs,否则会爆栈。

Continue reading “这几天做的POI的题”

白书第五章(网络流)练习题

一切皆可网络流

图论题,转化到常见模型才是最重要的。


网络流

花了点时间把白书的网络流例题、习题都做了,覆盖的挺全的,主要是建图的技巧吧。
一些简单的题解。


例题:

uva 11248 Frequency Hopping

网络扩容,bzoj上有一道类似的题,就是每次扩展最小割的边,看看够不够。两个优化:

一个是直接在残余网络内增广,一个是不用求最大流,当增广到C就不用增广了。忘记将belong置0,wa了一次。

Continue reading “白书第五章(网络流)练习题”

中考一周年纪念

“很难想象自己一年后的样子呢。”


如果没记错,一年前的今天应该是中考的日子,当时考完感觉很爽。(考完很爽的考试这辈子应该也没几次。) 过了几天后得知happyending,然后就玩了一个暑假,去了好多地方。

时间过得好快呢~

来省理科实验班也一年了吧,现在依然是天天被虐的感觉。

刚开学的时候老师说高一会过得很快,现在看应该是真的。


学OI也有一段时间了,从原来的非常弱变到了现在的很弱。(也是一种进步呢。)

学了许多神奇的算法,认识了许多人,达到了自己想象不到的打字速度。除了这些,收获应该还有许多。


中考,高考。“你觉得对自己很重要的考试,对别人来说也许就只是几天假。”

以上。

每天都对自己充满信心。