Codeforces Round #291 (Div.2)

VictorWonder posted @ 2015年2月21日 19:16 in Codeforces with tags 矩阵乘法 二分答案 解题报告 , 832 阅读
这套比赛是从冬令营后开始做的,做到现在大概有一个星期了,主要是由于春节期间各种颓+拖延整晚期。本来按照计划,这套比赛应该在前天完成,结果被我拖到了昨天,昨天又在搞翻墙的事情,就拖到今天了,今天下午,突然想起来这套试卷还没有做完,觉得不能再拖下去了,这才终于讲这套水题给刷完了。
题目都比较水,讲的不算很详细,还不懂的话可以找我或者看官方的英文题解。
 
Problem 2A
直接一位一位判断过去,假设有一位是x,如果9-x比x小的话,就用9-x替换该位,要注意的是不能有前导零,要特判(我在特判的时候出了错也是醉了)。
 
Problem 2B
这题坑了我很久,因为我莫名其妙地想歪了。题目大意是这样的,有很多不会动的怪物,位于平面直角坐标系上,你有一个两头同时可以发射激光的激光炮,也就是说,激光炮一次性可以将一条直线上的所有怪物都杀死,激光炮也不能动,现在询问杀死所有怪物需要几次。很明显,以激光炮的位置为原点,接着枚举每个点,看看其所在的直线有没有被枚举过就行了。
结果我想成了这个样子:激光炮是可以移动的(虽然我看到题目里面说激光炮是不会动的,但还是莫名其妙地想成了会动),那么就等于找到最少的直线,使得这些直线覆盖所有点,然后我就不会做的。。到后来才想起来,原来这题很水。
 
Problem 2C
这道题目是整套比赛中,我花的时间最长的一道题。给出n条字符串,接着是m次查询,每次查询给出一条字符串,询问给出的n条字符串中,是否存在一条长度相同且只有一个字符不一样的字符串。结果我开始的时候看成了“是否存在一条字符串,使其某子串和询问串恰有一个字符不同”,然后我就思密达了。
后来才发现题目没看完,然后想出了一种奇葩的做法,首先,把所有串都连起来,求出后缀数组和LCP,然后对于询问串,我们一位一位判断过去,对于第i位,判断一下有没有一个串和该询问串的LCP是i-1,且第i+1位开始都是一样的,实现起来似乎很麻烦的样子。然后我就无耻地看了题解,这才知道题目中竟然还有一个条件,保证只出现a、b、c三个字符,所以对于每一位都三种情况枚举过去,然后求hash就行了(实际上好像字符集是26的话也是能过的),题解中用的是排序后再二分判断,我偷懒用了map,最后再出现了各种莫名其妙的错误(我的DEVC++真高级呵,cstring都给自己加上了)
 
Problem 2D
这道题的题目看了我好久,因为懒得开翻译就直接看,看了好几遍才大致明白是怎么回事。就是有很多物品(就是题目中的droids,大概是士兵神马的,这些细节不用在意),每个物品都有m种属性(m很小,最大只有5),第i种属性有ai条,然后你有m种机器,第i种机器恰好可以将所有物品的第i条属性消去一条(如果没有第i条属性的话当然什么事情都不会发生),一个物品如果所有属性都没有了,那么该物品就会消失。然后,你一共可以动用m种机器一共最多k次,询问你能够消去的最长的区间长度是多少,要求输出第i种机器的使用次数。
题目看明白了,这道题目就好做了,首先,要想消去一个区间中所有物品的第i条属性,那么一共要动用第i种机器的次数等于这个区间所有物品中,第i条属性条数的最大值,即[tex]max_{k=l}^{r}ai_k[/tex],所以,问题就转化成求区间最大值了,因为最后要求,消去的区间长度最长,所以我们可以对每一个位置都向右二分出一个答案,然后再更新最终答案就行了。因为要多次查询区间最大值,所以最好打个ST表,线段树也可以,不过应该是可以卡的?当然,CF上不能卡,这题时限是2s,用线段树只要没有打萎,也是能过去的,但速度从理论上讲是要比ST表慢的。
 
Problem 2E
这道题是我这套比赛AC的第二道题我会说?这道题明显可以通过数据范围判断出做法,关键在于x,x是十亿,所以主体部分的做法要么是[tex]O(\sqrt x)[/tex],要么是O(log x)。O(1)一般来说非数学题或结论题是不可能做到的。
很快,可以发现这道题目可以用DP搞,最暴力的DP当然是O(nx)的了,十万*十亿,挺吓人的。其实还有一个关键,那就是di<=100。我们用fk表示等于k的di的树目,我们就能够成功将n从十万变成一百了,但是,很明显,这样还是跑不出来的,我们必须要把可恶的x给变小,要用矩乘优化DP。
单次矩乘是[tex]100^3[/tex]即一百万的,但是我们一共只需要矩乘log x次,所以最后还是能够跑出来的。
 
 
Code:

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter