蒟蒻的Codeforces Round #316 (Div. 2)补题记

中午打了这场vp,有点惨啊。。。E有思路没写完,还是太弱了。

A. Elections(模拟)

A题看错题意,没处理好一人都没的票的情况。。。WA了四次,还有一次过了47个点。。。虽说9min就过了C,但是还是直接崩了。

B. Simple Game(博弈论)

简单题博弈,分奇偶情况讨论一下。

C. Replacement(乱搞,讨论)

我是乱搞,就是维护出来一开始有多少个相邻的’.’,然后每次改变分情况讨论。

D. Tree Requests(dfs序+二分)

这道题比赛的时候想了个记录每一层字母的思路,没想清楚。后来看看题解,发现方法主要有离线和在线的做法。在线的做法和我的很像,在这里就写一下在线做法,但是在线做法因为用了STL有可能被卡时间空间也是很悬。。。

维护dfs序出来,同时存下来每层深度下每个字符的属于的节点的dfs序。然后我们就可以二分找到某个节点子树的某一层的那些字符的个数。回文串必然要求为奇数的字符不大于等于2.所以就可以在线算出来了。

E. Pig and Palindromes(dp)

E差一点就写完了,就是最后的讨论没写清楚,没出样例于是GG。

首先我们可以从左上角(1,1)和右下角(n,m)同时分别向中间走。那么设dp[i][j][k],表示两个方向现在都走了i步,左上角走到了第i行,右下角走到了第j行。然后我们可以计算出这两个点的现在坐标,然后转移就可以了。

但是麻烦的地方在于最后中间那部分的讨论。如果走的是偶数的回文串(n+m%2==1),那么这两个点的最后坐标并不是在一起的,有两种情况:j>k和j=k的情况。走的是奇数的话,只有j=k的情况。

总结:这次换了打法,先做了C还比较顺利,但是A,B的崩盘我觉得还是自己的读题有问题吧。E题最后时刻没写出来,对于我来说也不是第一次,四省赛不就是这样吗,这种细节的题目,没有压力的时候还好脑子不乱,但是最后关头很难理清楚了。。。D题没想到dfs序,实在是太傻比了。以后争取每周打两场cf的vp。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注