vp 记录

发布于 2021-08-23  127 次阅读


前面的话:

沉迷vp,开个博客记录一下自己丢人的战绩。

之前的 CF 以及 At 都是抱大腿居多,自己肝题少,水平提升不大。

所以果然还是要靠自己努力么。


Vp in Codeforces

  1. Codeforces Round #732 (Div. 2)

ID:Encounter_qty , rank 1537.

在A题被降智了,赶时间没看到操作次数 $\le 100$ 的限制,直接一发 WA on test2。然后写得磕磕绊绊,到 00:21 才过,裂开。然后去 rush 一下 B,发现一个性质:交换两个长度相同字符串相应的位置,它们的哈希值总和似乎是不变的。于是求哈希值相加,比较少了哪个字符串的哈希值即可。然后脑子一抽用不擅长的 std::string 进行操作,写到 00:50 才过。果然还是 char* 比较适合我。C 题,序列操作题,想了很久没思路,旁边 $\texttt{legendgod}$ 大佬一眼切掉,给了个思路,01:25 一发过。D 题没什么思路,赛时猜是 DP,直接弃了。F题大概是作差?后来没怎么看题了。

事后看了一下 Tutorial,居然是Chinese Round...

补了一下D题,在一波操作转化之后变成了组合题,插板法瞎算就完事了。之后遇到这类所谓“操作题”需要多观察操作的性质,尝试转化操作,不要见到是计数,觉得是 DP就直接跳。F题猜的差不多,思路类似吧。

  1. Codeforces Round #738 (Div. 2)

ID:Alkaid_Star,rank 1277 .

A 题猜了个结论,0:04 一遍过。然后经典被降智,B 题很简单的思路却重构了一遍代码才在 00:19 一遍过。C题是个结论题(大概?),开始的时候没有思路,后来漏了一种情况,甚至怀疑自己解法是错的,血亏一发罚时。补上一个特判就A了,时间 00:32。D1 挺简单,马上想到了并查集的思路,两边并查集然后暴力判断,00:49 一遍过。后面的 E 估计是 DP,被点到死穴了,完全不会。

这次的题主要还是有点冲动,写了一部分代码又不对,删掉重写的情况有点多。以后还是应该三思而后行

事后看了一下 Tutorial,居然又是Chinese Round...

补了一下D2,是道神仙思维题。评论区 $O(n \log n)$ 做法吊打标算 $O(n \log^2 n)$,Orz。

  1. Codeforce Round#736 (Div. 2)

ID:Alkaid_Star,rank 82.

这把状态不错。A 题是个简单构造题,原来想着特判后来发现 $p \ge 5$,用不上, 0:01 一遍过。B 题是显然的贪心,瞎写一通,0:06 一遍过。C 题,赛事还是想了一会儿的,想复杂了。原题显然可以转化为每个连通块里编号最大的点被保留。而题目保证了每条删去的边都已经存在,这样我们不需要与维护当前点相连的到底是哪些点,只需要维护有几个与当前点相连的点即可。不过赛事还是想了前者,开了个 std::set 维护,$O(q \log n)$ 00:20 同样是一遍过。第四题,首先根据余数相同可以进行一波差分把余数相同改成区间 $\gcd>1$。注意这里有个细节是差分数组需要用绝对值,负数会出问题。然后用线段树维护区间 $\gcd$,双指针扫一遍就好了。此时做完前四题,我的排名是 rank 23。看一波榜,发现此时还没有人过 E,甚至以为是榜错了(。后来发现有人过了,那没事了啊,E 看起来是个挺牛的题。仔细思考了一波,发现可以按照模 3 的余数分成三类,答案就是总和减去其余两类的和。总和可以用上指标求和做,剩余两类却是不会推了。F 题看起来挺神的,不是很会。

后来发现 E 的思路大概是对的,只不过没有想到 dp 递推这个套路,而是想一味去简化式子。然后发现好像也有生成函数的做法,好像会简单很多。


我们无法选择过去,但我们可以改变未来。