作者归档：MedalPluS

关于MedalPluS

智商不足的退役码农选手(╯‵□′)╯︵┻━┻

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)

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