CodeForces 475B Strongly Connected City

强联通分量的题,建图搞定了就搞定了。关于scc的算法可以翻我的图论标签找一下我写的一篇tarjan算法总结。

CodeForces 1A Theatre Square

作为CF的Hello World题,居然会拿爆int这种事坑人。。。

CodeForces 342C Cupboard and Balloons

这货是几何题, 一图秒懂系列:

)0U7OLC(${F}O0C050VRHJI

CodeForces 3C Tic-tac-toe

模拟题,这个题我WA了一下的原因是忘记了X的数量始终比O多一个,即使是赢了,也要是在棋盘合法的前提下。

CodeForces 126B Password

整个比赛都在搞这个题,还不知道哪里不对。

其实这个题如果用kmp做主要卡在这么几个地方:
首先要读懂题,aaaaaa的对应答案是aaaa,四个a,也就是说prefix是在不包括最后一个字符的范围内检索,suffix是在不包括第一个字符的区域检索,中间那个则是在既不包括第一个字符也不包括最后一个字符的范围内检索。
然后Next数组要机智地用好,就是说当前模版串失配之后,机智的方法是利用当前模版串的next数组,直接构造出下一个可能的模版串,而不是一次只删掉末尾的一个字符,再重新扫描这种暴力方法。

其实这个题上面两点我都没想到,更要命的是我的next数组构造方式就存在问题。

在这里重申一下正确的next数组构造方式,首先next[0] = 0,next[1]  = 0(next[0]=-1也是可以的),这个没什么好说的,然后要注意,在进行到中间的时候,首先检查next[当前位]对应的字符是不是和现在的字符相等,相等就在当前next的基础上+1,赋值给下一位的next,如果没有匹配上这个时候不是简单的归零,而是要把当前的比较位置更新成当前比较位置对应的next值的对应位置,也就是一定要迭代回去。(我就是因为没有迭代,next数组整个就是错误的)

CodeForces 279B Books

lower_bound真的不是那么好掌握的。。。有时候很坑。

这个题就是前缀和还不够,在前缀和的基础上还要使用二分搜索进一步减小时间复杂度才能过掉大数据。

CodeForces 244B Undoubtedly Lucky Numbers

把那些lucky numbers预先生成出来打进一个表里(预处理),接收到输入的时候然后只要查表就可以了。

CodeForces 202A LLPS

枚举所有的可能性,如果可以的话计数器加一,这个枚举过程可以借助二进制枚举来优化,把每一位当成控制该位对应字符是否使用的开关,通过位运算来判定,就可以了。

CodeForces 96B Lucky Numbers (easy)

打个表就行,因为数据范围小。

CF 460C Present

二分答案求解,这种求最小值的最大值,或者可以转化成求最小值的最大值的问题都可以通过二分答案,回代验证的方法求解。

这个题要注意在ok那个函数中res会被加爆int,如果把判定推出的if写进for里就可以避免加爆还能剪枝加速,要么就用long long也是可以的。

注意在回代检验的过程中,使用了前缀和来快速提取当前节点已经在先前被浇了多少次水。

Scroll to top