分类目录归档:公告

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)

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

 

Codeforces Round#372 Div.2

A. Crazy Computer

ZS the Coder is coding on a crazy computer. If you don't type in a word for a c consecutive seconds, everything you typed disappear!

More formally, if you typed a word at second a and then the next word at second b, then if b - a ≤ c, just the new word is appended to other words on the screen. If b - a > c, then everything on the screen disappears and after that the word you have typed appears on the screen.

For example, if c = 5 and you typed words at seconds 1, 3, 8, 14, 19, 20 then at the second 8 there will be 3 words on the screen. After that, everything disappears at the second 13 because nothing was typed. At the seconds 14 and 19 another two words are typed, and finally, at the second 20, one more word is typed, and a total of 3 words remain on the screen.

You're given the times when ZS the Coder typed the words. Determine how many words remain on the screen after he finished typing everything.

继续阅读

[bzoj 1597][Usaco2008 Mar]土地购买

Description

农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3x5的地和一块5x3的地,则他需要付5x5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.

继续阅读

[bzoj 1052][HAOI2007] 覆盖问题

Description

  某人在山上种了N棵小树苗。冬天来了,温度急速下降,小树苗脆弱得不堪一击,于是树主人想用一些塑料薄
膜把这些小树遮盖起来,经过一番长久的思考,他决定用3个L*L的正方形塑料薄膜将小树遮起来。我们不妨将山建
立一个平面直角坐标系,设第i棵小树的坐标为(Xi,Yi),3个L*L的正方形的边要求平行与坐标轴,一个点如果在
正方形的边界上,也算作被覆盖。当然,我们希望塑料薄膜面积越小越好,即求L最小值。

继续阅读