Codeforces Round#439 Div.2 Solution

Problem A

直接输出Karen即可,因为异或必须遇到同一个数两次才可能还原。

Problem B

显然如果末尾遇到了25答案必定是0。不然的话暴力算即可。

Problem C

考虑距离为1是什么情况?同色相连

考虑距离为2是什么情况?同色通过某个异色相连

这样我们发现,只需要考虑两种颜色即可。那么问题就是二分图匹配个数,也就是

\sum_{i=0}^{min(A,B)}\binom{A}{i}\binom{B}{i}(i!)

Problem D

定义每次新添加的边的两个端点为关键点,且这个端点到根的路径上的点均为关键点。

那么显然这样只会有2m\log n个点。我们于是乎要算一下每个关键点是否与非关键点相连,是的话把所能累加的东西累加给他,只有左子树or右子树有的话就把他的儿子看成关键点即可。

那么每个点的贡献就是他的普通贡献乘上经过他,非关键点的个数。

暴力算就行了。

Problem E

考虑对子矩形的添加看做一次hash,那么问题等价于询问两个点的hash值是否一样。直接二维Fenwick树即可。

反思

这场比赛我最大的失误,依然是一直以来改不掉的毛病,容易卡题

因为手贱,导致了A题的FST,这种错误在正式比赛中是严格,绝对不容许存在的。

其次,对于C题一开始的想法事实上是错误的,在发现了错误之后,没有及时的扔掉算法,反而放弃自己,这是一个很严肃的错误,无论何时都不能放弃。

由于C题的原因,导致了卡题现象的发生,影响了心态,对于后面的题的思维的扩展产生了隐形的约束,面对E题这种吉福特题没有做出来是非常不应该的。

因为心理原因,贬低了自己,认为D题没有人过,那我就不应该去做,自动放弃。这是非常愚昧的。

所以对个人来说,这场比赛犯的错误是不容原谅的。应当及时汲取教训,不能再犯。

发表评论