CH Round #22 - 除夕欢乐赛

Codeforces - Official

From lydrainbowcatITX351


小时

尚未报名

PH List 24/179 500 分 From
Build More Roads 16/38 1,000 分 From
Bomb Disposal 15/44 1,500 分 From
WLAN Update 34/108 2,000 分 From
Strange Comic 5/38 3,000 分 From

已经重新进行Final Test,最终能力排名已发布。祝大家春节快乐!

题解:A:出题人用餐时在饭桌的塑胶板下面看到了一份从报纸上剪下来的PH表,于是产生了这道Trick水题。一个是7.8 7.? 7.? 7.? 7.8,中间三个都是7.8;还有2.9 2.? 3.? 3.0,这种9、0的数字要特别注意,根据递增的条件有一些情况下也是可以知道的。

B:构造一个边数最多的不含r团的n个点的图。方法参见标程,只有两重循环。。。

C:掌握好括号序列,这题就可以做了,主要是实现问题,没有思维难度。

D:可以证明最优解一定在MST上。所以MST+背包DP即可。注意图不联通输出Impossible。

E:每种颜色维护一棵Splay,然后考察平衡树的合并。

本场比赛的题目分值为:500-1000-1500-2000-3000。

CH能力排名的标准计划于近日从 0-1000-1250-1500-1700-1900-2100-2350-2600-3000 降低为 0-1000-1250-1500-1700-1900-2100-2300-2500-3000,实行时间另行公告。

从CH Round #19起,将接受用户捐赠用于发放公开赛奖励,具体公告 http://www.contesthunter.org/notice#notice-8

由于元旦期间CH经历了一些调整,所以新年欢乐赛没有办成,于是就改成除夕欢乐赛好了。为了大多数人的时间考虑我们安排在除夕的前一天晚上进行。

比赛为标准的Codeforces赛制,2小时5道题,难度介于Div.1和Div.2之间,由于是除夕【欢乐赛】,大部分题目以Div.2难度(NOIP)为主,为了增强挑战性最后一道题目会稍难一些。

Pretest不会很弱,会涵盖较大的随机数据,暴力和明显错误的算法应该是通不过Pretest的。不过边界情况和特殊构造数据可能不会出现在Pretest中,方便大家去Hunt~

最后由于评测系统为Linux,请大家使用longlong、%lld输入输出64位整数