2014ACM广州站

报名

抱着有机会参加现场赛的幻想,我们报名了网上赛。

参赛

第一题是全场最难的吧,从第二题开始水直到第四题,后面我们便无从下手了。

做回

Relief grain
首先先弄懂在链上的处理方法,那么转移到树上用树链剖分就变成等价问题,只不过操作从m个变成mlogn个,所以在链上的方法是:我们把所有的操作标记,例如[l,r]要加一个z,那么我们在l上添加一个(z,+1),在r+1上添加一个(z,-1)的标记。到最后我们只需要建一个堆,保存每个类型的值以及最大值。从左往右扫,每次按该点的标记修改每个类型的值,再求最大值即可。时间复杂度是,再加个树链剖分就是
Rabbit's String
先是后缀数组,然后我们二分答案串,接下来的任务就是判断是否可行,也就是要用k-1次分割将比此串大的子串切割,那么这个切割的过程就是最小点覆盖线段问题,我的做法是所以加上二分整个算法的复杂度是

comments powered by Disqus