CF1141(div.3)滚粗记

才发现codeforce少打了s。

$19/03/20$晚

十点半左右打开洛谷,发现首页有个说今晚有$div.3$,于是急匆匆的登录发现刚好还有2分钟开始!

本来想说把网络流24题的练习终结的,但想想我急需一场比赛来挽救我糟糕的$rating$,于是随手拿了张纸就报名了。

第一题:

读完题发现是求2与3的因数和,而且最后还判整除,有些小细节耽搁一会,花了$4min$打完。。

第二题:

洛谷评分绿?这CF评分就没一个是靠谱的。大概就是有个01串周期,问整个最长连续1的长度;倍长直接一个个加就好,花了$3min$打完。。

感觉速度很正常的样子??说不定上分有望。

第三题:

给你个序列$q_i$,问能不能通过$q_i=p_{i+1}-p_i$确定一个全排列。

卡了$5min$,才发现求前缀和再统一加一个大数,最小那个一定在$p_i$中是1。于是就塞到一个桶里面暴力搞即可。

打完才$15min$,感觉状态不能再好了,我真是嗨到不行啦!

然后就遇到了第四题:

给你两个字符串,相同字母可匹配,'?'可与任意字符匹配,问最多能有多少匹配数?$(L<=150000)$

事实上原题不是这样的,但在我脑子里他已经被翻译成这样了。然后刷网络流一个星期的我,也自然而然的想到了二分图这个东西。。。。

然后当然要面临长度限制的问题,想了一会发现可以通过字符来建一个加权二分图(事实上这步可以转到正轨上的。。)

于是就敲啊敲啊敲啊敲。

答案搞对啦!!突然发现还有方案数。。

可以想到先将$a,b$两字符串的所有字符分别丢进$queue$里面,把最终每个字符的流量搞出来,然后对于每一对流量不为0的就暴力将队列的两字符匹配出栈,然后就没了。

于是就码啊码啊码啊码。

于是虽然思路十分顺畅,$40min$就过去了!!!

虽然现在情绪十分激动,但当时的我还在为自己能活用学过的知识而十分洋洋自得。

点开第五题:

打怪物每回合扣的学量有周期,问多少回合可打死(但可以伤害为负)。
看到伤害为负发现不能二分答案了,并没有单调性。

但是假设我们打了k个整周期外加几回合(不知道多少)打死怪物,可得到式子:

$$H-k*sum-minn<=0$$

其中$sum$为每周期的总伤害数,$minn$为最大伤害数。然后发现这个周期是可以二分的。。

于是快乐地码好,并快乐地$Wa~On~Test4$。。

??这会为啥我不懂啊,爆$longlong$了?于是调啊调啊调啊调,但一直崩啊崩啊崩。

于是就只剩$20min$,我始终不知道为啥会WA,于是就自爆了。。

困死了我睡了。

$19/03/21$晚

结果出来了,我排名$1700$左右,发现只对了3题?C被叉了?

发现几个毒瘤造极限数据,爆了我的$Int$,于是最终只有3题对的。。

回头又看了$E$,发现踏马又是题看错了,加上二分一些细节并不是很清楚,于是还是WA的很惨,最终在某位$ACMer$的指导下A了。。

现在想想,这次比赛还是要怪D浪费了太多时间。明明可以直接将相同字符先暴力匹配,再将问号单独处理做到$O(N)$,自己非要强行加大难度,结果就是为了达成同样的效果,我白白浪费了半小时宝贵的时间。。

但也不能说死,CF的比赛天天半夜进行,本来精力就会受一些影响,基本上就是想到哪里打到那里,也不知道可以怎么处理这个问题(喝咖啡强行续一波?并不清楚)

于是这次比赛也遗憾收尾,仍是在$1470$波动,真想啥时候能给我个机会上个紫啊。

但机会从来都是自己创造的,通过不断磨练,相信应该会有一天能实现的。吧。