我知道了王子 的博客

我知道了王子 的博客

CSP-S游记

posted on 2020-11-06 11:00:12 | under 未分类 |

看大家都在写,我也来一个吧。

Day -?-1

初赛模拟试卷,84分全班倒一,我爪巴了。

Day -? 下午

初赛,自闭。
虽然知道自己考炸了,但没想到这么差。
和一份民间答案对了一下,只有70分。
时间复杂度4题全错是我没有想到的。
原本以为机房里面同学说过不去初赛退役了只是玩笑话
没想到这就发生在了我身上。

Day-? 晚上

和标准答案对了一下,发现 $70 \to 80$
这民间答案这么烂的吗?
我以为时间复杂度全错,结果只错了一题?
但还是考的很烂,应该过得去初赛吧。

Day-?+1

肝文化课作业一个下午,竟然错过了大新闻
那我是不是没有导师了,淦。

Day-0

和shenmadongdong合作拿下P6660最优解

打了一些板子,但是感觉其实用不上,最关键的是考试状态得好,能做出有思维题,或者打出四维部分分。

Day-1

为什么你们在发试题前都在敲代码啊。
那我也敲。。。
缺省源都没敲完就被命令停止了

拿到试题:

T1 好像是大模拟啊,这个我擅长
T2 好像是思博题。
T3 数据结构?爬了。
T4 好像是博弈论,待会去搞搞看。

比赛开始

先开T1。
打了1h5min啊啊啊啊啊,我真的太菜了。
过了大样例,但还是感觉很悬。

然后开T2,打了20min,运行,出了什么诡异的东西。
然后发现没有初始赋值,那没事了。
一发过了大样例。

然后开T3,发现不会,skip先。

开了T4。
好像不是博弈论。
诶这个 $n=3$的情况不是送分吗?先打了
然后在考虑通过递归判断要不要吃。
发现每次取出最大和最小的不能直接用堆(可能是我太菜了),要用平衡树,但是我在考场上估计打不出平衡树。
思考了一下,果断使用set
发现这样也有70分,那就打啊
打了一会儿发现思路有点问题。肚子有点痛,先去了一趟厕所。
在厕所里理清了思路,回来搞一下。
CE了。然后发现我忘记set的删除操作是什么了(打成了delete)。
去stl内部找了一通,发现是erase
过了样例3
然后在测样例4的时候爆栈了,那不管了。

然后回到T3
不会。。。
不会。。。
不会。。。
不会。。。
不会。。。
那就打暴力吧。
首先打个线段树…… 打什么线段树啊,反正也过不去,不如打分块吧。
然后就打好了暴力。
突发奇想测了一下大样例。不出我所料,跑不出来。。。 诶他怎么只用4秒就跑出来了啊,这不科学。
不管,这意味着我能多水一些分。
然后fc了一下,发现没有差别(fc的时间比我运行的时间还要久。。。)

然后去检查了一下T1,造了几组边界数据,发现没有问题。

这个时候只剩30min了。
先检查了一下文件操作,发现我T3没改,好险啊。
然后又发现我T4没有删调试信息(因为样例3比较小就直接肉眼比对了)
最后又检查了一通,发现没什么问题,开始吃面包。
吃完了面包发现还有20min,准备把T4的非递归形式写出来。
花了15min没写出来,又去检查格式了。

草听说T2还有k=64,n=0的情况,爬爬爬

最终预计得分:100+95+30+70=295
最高得分:100+100+?+?=300+?

Day-2

先去oitiku上测了一发
100+95+70+70=335 感觉良好
又去洛谷上测了一发
40+95+30+70=235
??????????
爬了爬了
经检查,我从10月3日跳到了10月14日
只有这1天出了问题。
100->40 ,爪巴了。

又发现T3暴力递归可以达到指数级,最低得分刷新下限。

最低得分:40+95+20+70=225
(艹怎么又T2T4比T1T3高啊)
期望得分:70+95+30+70=265
最高得分:90+95+30+70=285

官方数据:100+95+65+70=330
感动
hoho!可以苟到NOIp结束再退役了!

T3 指数级分块65,指数级线段树70,指数级直接加逆元75
CCFsb

XJOI评测:T1还是只有40,换成洛谷民间数据AC的代码,依然只有40pts,疑似ub,但是T3涨到70pts了

发现访问到了负下标,如果返回值为0的话就能过。

用Linux就能过,然后CCF评测机用的是Linux

开心.jpg

最终预计得分330pts/335pts

最后成绩:100+95+50+70=315

CCF评测机还是太慢了,不过也知足了

赛后反思

这场CSP-s靠着运气考得比很多实力比我强很多的大佬都要好,但不能总是考运气,提高实力才是最关键的!

感觉自己基础算法实在是不扎实,高端算法学得也很少,以致于我甚至一颗线段树都怕自己打挂浪费时间,因而去打了分块。
如果打了线段树就能多 $5$分,但这仅仅是因为数据水的原因,并不是反思的重点。
如果数据不水的话,我最低会被卡到40+95+20+70=225

这个分析基于我最差成绩分析,而不是CCF的思博数据
这场CSP考试策略完全没有问题,考得不好还是自己的原因。
可以发现我T1和T3分数很低。
事实上,我代码能力比较差。(这估计也是大部分人有的问题吧)
考场上,我T1打了1h,中间打挂多次,最后还是打挂了。可能这个速度在部分人眼里不算慢了,但我想问自己:

你猪国杀是白刷的吗

当时觉得自己代码能力太弱,决定刷猪国杀的时候,周老师表示支持。但为什么刷过了之后,模拟题能力依然那么差呢?

当时模拟赛打战旗,也是调了2h才发现自己有一个地方x打成了y。而这一次,并没有那么多时间给我检查,所以,有一个1打成了0,直接挂成40pts。

代码能力实在太弱,估计也跟我比较懒,刷题比较少有关吧。

至于T3,真的是自己能力不行了。

考场上只认为这可能是个数据结构,然后就skip了。
这对当时的我来说确实是一个正确的选择,因为图论我也不擅长。
打完T4回来看T3,发现依然不会做,然后选择打暴力,这固然是最好的选择。

但是你为什么想不出正解呢

事实上T3正解的算法都是我学过的内容,我考场上也想到了这是一个DAG,拓扑后可能可以进行一些操作。
但我不敢。
图论是我的短板,我不敢把暴力放着冒这个险去敲图论。
所以我的短板还是很明显的:图论、数据结构。
这一次刚好只考了1题,下一次如果考3题呢?
还是得补啊。

这次T4得分比较高,其实是策略原因。
我看到T4就觉得这是我可能会做的题目,说明我对自己的短板和长处还是有一定了解的,这是我的优势。
然而T4的正解和蚯蚓这道题有很大的关系,我却没有刷过。

懒惰,成了我的瓶颈。

不想学新算法,不想刷题,终究只能止步于NOIp。
无论是ZJOI还是PKU/THU WC,要学的知识点都不止提高组知识点。
或许我能依靠自己的小聪明在NOIp中再次获得好成绩,但也肯定止步于此了。

JYZ,从现在开始,你需要勤奋努力了!!!