CH Round #16

OI - Official

From lydrainbowcat


小时

尚未报名

Prefix 45/147 From
Channel 4/87 From
Parade 7/90 From

这轮比赛按照【真·NOIP模拟赛Day1】标准举办,难度和谐,利于涨信心涨Rating,题目非原创。

因为这次比赛比较简单,这里就简要说一下题解,还是不理解的就去看标程吧。

第一题:快排 或者 字典树。

这题明显是送分的。注意到仅有1000的数据范围,我们直接进行字符串快排,然后对于某一个串,取它的前【Max(它和它前面的串的LCP(最长公共前缀)长度,它和它后边的串的LCP长度)+1】个字符就行了。

第二题:排序+扫描+压位。

我们假设先进行了所有的插入,没有删除,然后考虑每个询问。这样就是把若干个关键点(波段区间的左右端点、询问的两个点各自)放到一个数组里,按坐标排序,然后扫描一遍,就可以知道对于询问的每个单点,有哪些波段集合可以覆盖它。这个可以用一个1024位的二进制数记录。

然后考虑插入和删除,我们就还需要知道在每个询问的时候哪些波段集合是存在的,这也可以用一个1024位的二进制数记录。于是对于每个询问就是看三个1024位的二进制数and起来是否为0。

这样复杂度是32768*15*1024,但是我们可以用bitset之类的东西(或者手写)压位,就变成了32768*15*1024/32了,然后就可以过了……

第三题:KMP变形

这题也算是老掉牙了。可以参见NOI2012冬令营,CEOI2011王宏讲课的课件。就是在KMP的每个比较[j+1]和[i]的地方,把两个数相等换成一个自己写的比较函数,比较在当前匹配的这段串里,当前位置前边比它大的数的个数和比它小的数的个数是不是都相等就行了。

这套题拿到200分应该是比较容易的(暴力分100+50+50),明天题目会稍微难一些。欢迎大家继续参加后天day2难度的比赛。