APIO2017滚粗记

Day 1

先是坐火车到了dulwich hill,然后转轻轨到了比赛地点,robert的办公室果然就是不一样2333

然后发现我似乎早到了?对面站了一个小哥我以为是组织人员(然而确实是的)OVO

于是我去买了一瓶可乐,发现要3.5刀结果我只有3.4刀囧,被迫买了罐装。

然后还有一小时的样子,我想想农药似乎要铂金四了,诸葛亮也要紫色熟练度了,来赢一把爽一爽吧,输了就证明我APIO会滚粗

然后就输了,被血虐。。(好一个flag)

继续阅读

[ioi2012] ideal city

考虑把网格的四条边看成图意义上的四条边,那么问题就相当于一张有环图中的两点之间距离之和

同列/行的格子可以缩在一起,那么就变成了一棵树,树上求距离之和非常简单,点分治+FFT就行了考虑记s[i]表示第i个点为根的子树的权值和,那么这条通往父亲的树边的贡献就是s[i]\times(n-s[i]),时间复杂度O(N)

难点在于转化为树,然后缩环这种思想。