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)

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

 

[bzoj1597][Usaco2008 Mar]土地购买

简单题,为了练习CHT所以来写一下。。结果发现写错了一个地方导致没1AQQ图片20160623113044

这种题N辣么小,肯定是想dp的对吧,但是我们发现并不能连续的做,那么怎么办呢?

我们发现,对于两个土地i,j,如果满足a[i]\geq a[j],b[i]\geq b[j],那么在买i的时候永远可以带上j

继续阅读

[BZOJ3482][COCI2013]hiperprostor

Orz Claris菊苣

对于这道题我们发现q很小,那么大概率是让你在线去做

然后我们知道n,m也很小,大概率是用n,m做一个dp

所以设f[i][j]表示从s出发,到达i,恰好经过jx边的最短路,利用spfa求出。

如果对于任意的i都有f[t][i]=\infty,则答案为无解。

继续阅读