csp-2019 游记

本人坐标SH，初二蒟蒻一枚，2019csp有点炸。。。普及275，提高125（周围大佬pj都是300+来着），感觉是没什么希望了。。。明年加油吧 ------------------------------------正文分割线------------------------------------ # Day -365~-120 划水ing ------------ # Day -120~-90 八月，暑假过去一半，我们的信息集训也正式开始。记得当时那三周真的是我此生最难的几天。。。 第一周还行，讲的各种算法还勉勉强强能听懂，回去对应的习题也还能稍微自己思考思考，甚至有时我还能独立想出来正解（印象比较深的是 七夕祭 ） 到了第二周，难度就上来了。。。因为加上了高中，其实难度一下子就从pj+提高到了省选难度，当时挺崩溃的，几乎听不懂，算法思路都不是很理解，~~所以导致有几天我就在颓废~~，这里印象比较深的是KMP算法，那个next数组的求法真的是神奇~~（我至今未懂）~~ **所以给自己一个目标：年底前搞懂KMP在干嘛并且会写**。 第三周可能就完全没怎么听课了，因为觉得听也没什么用，所以就自己去刷刷题然后学一些力所能及的算法了。 ------------ # Day -40~-28 这段时间是csp的初赛及复习时间，这段时间其实过得不算太紧，由于之前也考过csp，对于初赛的题型也算比较了解的，就是对S的机试比较好奇。刷了大概10+的模拟卷吧，分数还能看，所以也没有压力很大，平常心对待吧。 ------------ # Day -27 这天是csp的考试，我记得我挺早就到了efz的，还向大佬请教了下之前一点没有搞懂的问题顺便和ctq1999，@诱宵美九 打了招呼后就进考场了。 进了机房，老师给了个网址，结果我开了inf个标签页，刷新了inf次，还是没有进去，唯一一次是登进去了在加载题目的时候炸了~~（垃圾CCF，卡的跟CF似的）~~，当时真的很想骂人qwq。不过在50分的时候jls进来给了个上海的专用网址就好了。选择一道道做下去还挺顺的，我最炸的计算机理论知识一道没考让我极其开心。在阅读程序的时候犯了一个小错，看错题目意思导致我手动模拟好久才发现自己看错了。在最后一大题时时间才过了40min，就告诉自己放平心态，慢慢考。于是发现了一道毒瘤状压dp。。。想都没想先看第二题，先写完看第一题。最后还是没有想到状压dp是在干嘛，蒙了几个就没什么事干了。检查了几番后，我就提早0.5h交卷了。交完我就后悔了，因为我说好和zzf一起走，既然等在efz门前还不如再看看。。。 在校门口和同学对了对答案，发现对的题没一道一样的？？！！！然后我就慌得一批，结果一问才知道貌似还分AB卷（全班都是A卷，就我一个B。。。）。后来还发现居然有考场能用devc++。。。顿时原地爆炸。 吃过午饭前往华师大（荒郊野岭啊。。。），一路比较通畅，到了校园发现考场还找不到了，走了大概15min才进了考场。一看到题目其实就比较踏实了，一路做下去直到最后一题的看程序。。。就是一个很sd的题目结果被我想的太复杂，推了1h，不过终究还是做出来了。有惊无险 ------------ # Day -26 自己看了看题目，估分J91，S73，感觉一般，不过教练说稳了，于是就放心开始准备复赛了。 ------------ # Day -4~0 这几天停课去efz集训去了（最后一天是在自己学校的机房，因为efz是考场），总算是享受了一次免考。。。（上次几乎所有人都免了就我一个人傻乎乎的过来考试还差点暴毙被踢出卓越qwq）这几天集训其实并没有学什么新东西，都是在打模拟赛，4天7场，强度较高，不过上午的Silver远没有今年csp毒瘤。。。（这当然是后话）不过其实下午主要就是考自己的代码实现能力，其实正解都不难想的，只是需要耐心推一推。（这里@ctq1999 其实真的没有什么难的，以你的实力AK也不难）。模拟赛后信心还是挺足的，毕竟还不知道CCF会出毒瘤题目。。。最后一天晚上复习了下LCA，树的直径，dp还有一些STL的实用工具就睡了（我爸居然催我颓废。。。惊了）。然后大概是10点睡觉的（今年最早系列）。 ------------ # Day 1 今天要csp了，早上6:40起的床（第一次睡的这么舒服），7：50到efz，其实并没有很慌，~~毕竟近几年的真题都刷过了，分数都在300左右浮动。。。（今年还是太毒瘤了）~~，丝毫没有意识到等会会遇到什么毒瘤。先是遇到了hry@xiaoh 然后碰到了几个巨佬，唠嗑几句就进考场了。 进了考场才发现gry居然坐我对面qwq，惊了，心里%了%gry就开始打LCA模板了。密码发下来后第二遍就过了，开始看题。 T1感觉比较简单的qwq，自己花10min手推了推，发现其实挺容易的一个递归，写完看了看数据范围，？？？为什么会有2^64，ll不是最大到2^63 -1嘛，这五分高精到时候有时间再拿吧（当时的我丝毫没想到还有个ull）于是转向T2。T2看了看题觉得一条链的时候是可做的，于是开始写一个大概是n^3的暴力。 1h过去后，自己调代码调疯了。。。就是看不出来到底哪里错了，于是乎去洗了把脸清醒清醒。回来15min仍然没有思路就先转T3了（当时心态有点炸，但是还没觉得很毒瘤）。T3一看题就感觉很难。。。注意到数据范围里有菊花图的情况，于是乎开始写一个贪心。40min过去，贪心总算调好了，自己一开始出的数据都过了后，自己开始hack自己。10min后，我发现贪心貌似是错的，心态就炸了，随便输出了个东西就回来调T2了。 当时我T2觉得没什么错就重构了代码，准备玄学一波，没想到自己还是没有写出来。。。结束前5min我已经疯了，刚好T2已经过了样例和自己出的两组就没想着再去管了，检查了一下T1和其他提交时要注意的，我就放空了。当时预计自己95+35+0的来着，没想到第二题还是写炸了。 去长泰广场吃了个饭，又回来再战普及。 回来时刚好jls在拍集体照，差点就没赶上，不过还是顺利的拍完进了考场。 准时开题。T1大水题没什么好说的。T2当时文字比较多就直接看了数据范围，震惊的发现n到了1e5，顿时觉得没这么简单，后来发现题目里有限制，于是就写了个45n的暴力，还考虑了下要不要开ll，不过最终没开。 ## 接下来就是我与350+失之交臂的沙雕时刻 看向T3时30min都没过，就没有很慌，然后开始看题。当时看到题第一想法就是对于每天都取最优的，下一天卖掉，然后再循环，看了看不就是一个T-1个完全背包嘛，当时抱着比较怀疑的态度试了试，发现居然过了样例。我开始了对人生和社会的大思考，去年摆渡车的毒瘤历历在目（我是蒟蒻）。然后冒出一个很sd的想法：可能今天买了后天再卖赚的更多啊，明天不能卖。。。抱着这个想法我就开始推dp，推了30min还没思路就写下一题了。 T4这题一上来看到感觉挺毒瘤的，所以就先打了个40的暴力，20min后开始思考正解。我先想到是不是和最短路有关系，因为每个人到1的最短路如果大于这个阶段就是不可行了，于是我又开始打了一个堆优化dij，nlogn的算法，发现刚好能卡过时间，感觉自己是对的，并且大样例对到前10个yes都没有问题，但是样例错了，于是我开始想：是不是这里对于最短路有什么要求啊，貌似两个阶段可以一来一去消耗掉诶。然后转念一想，不对啊，只要大于最短路长度，那么总归是会到达的（什么sd思路），于是又回去看T3了。。。 现在时间其实没过多久，才80min，我就先写了35分的骗分算法（T=1,2和N=1的时候），然后开始自己写当T=3,T=4时候如何算的方法（写了大概150行，调完自己测的也没什么错，就没再管，开始推dp），结果一直到结束前15min都没想出来就交了，预估自己是100+100+35+50的来着qwq。结果机房外遇到sng的zj巨佬，想都没想告诉我T3是完全背包，我傻了。。。然后告诉我T4要考虑奇数偶数的，我崩了。。。我貌似离350就两念只差。。。唉 回到家其实已经有点爆炸了，D1的S目标是100+40+30的来着，然后J还炸了，当时颓废了一会，10:30睡觉 ------------ # Day 2 还是早早来到了学校，坐在机房efz然后开始拿着手机颓废，~~结果被jls当场抓到2333~~进了考场莫名开始慌，密码还输入好几遍都没对。 看到第一题：what？f**k有毒吧，怎么连个暴力分都这么难拿。。。于是我就开始推第一题（下意识觉得自己推一推还是能出来的）。当时真的除了前两个点n=2的时候能暴力，其他的连个暴力都没思路。1h后，我仍然卡在这题，觉得是dp但试了好几个都写出来是错的，于是看向旁边的@xiaoh hry大佬，发现他也在看T1并且推DP而且也是写了一堆草稿的样子我就安心了，开始看T2。 T2一看题还是觉得很毒瘤啊，第一反应居然是贪心（我怕不是个励志），写完发现不对，就随缘了，写了个12的暴力就开始推dp。推了30min开始吐槽题目怎么这么毒瘤啊，真的没啥思路，于是写了个过了样例没过大样例的dp然后10内跑n！的暴力，5000内跑dp，5000外跑贪心。 T3一看到题第一感觉比T1T2都好拿分。。。当时想着先把一条链的情况拿出来，每次的重心就是两段的中间部分啊，On扫一遍就行了，写完测完没发现自己有什么问题又开始推T1。 此时已经过去3h，我也不抱很大的希望了，又推了15min后觉得真的没时间了于是写了个m*2^n的暴力，但是第三个样例没过，让我很不解，我输出512，样例是742，死活调不对，最后还是没有找到错误，希望CCF能让我再过一个。。。 考完后心态挺炸的，觉得自己这几天的努力都白费了。。。预计提高是140~150（因为当时不知道我D1T2写挂了），然后晚上自测的时候就真的崩了，d1t1的25+d2t3的15没了，当时觉得三等都悬了，然后就抱着自己已经崩了一地的心肝文化课去了（毕竟一周没上课，要补的还挺多的） ------------ # Day 3 对你没有看错，我由于作业落下的有点多，肝到了今天早上1.30qwq然后睡觉去了。 ------------ # Day 4~7 疯狂肝文化课，补一周的作业和课程，结果天天肝到1点~2点，本人已疯，有事烧纸，没事也烧纸。。。 ------------ # 总结 其实这次csp整体并没有发挥出我的实力，但是的确也让我认识到了自己的不足之处，对于提高组这个级别来说还是太勉强了，自己的独立思考还不太够。 1.该拿的暴力拿不到，自己测的数据总是hack不掉自己的代码。这个问题其实很严重了，因为OI赛制对于写正解真的是奢望（某些能随手AK的大佬不算），还是要注重自己写暴力的能力。尤其是D2T1，32分的暴力其实不难，但是因为自己的失误导致没有拿到，所以我觉得自己还是应该多写写暴力，多造造毒瘤的数组，这样才能让自己的代码拿更高的分。 2.dp部分薄弱。的确，dp作为现在信息的重要考点之一，在题目里占的分数也是很多的，类型也是层出不穷，对于每种dp，总归就只有想到了和想不到两个状态，一个天上一个地下，可能你能背背包的模板，但是dp是活的，不可能靠几个模板就能在OI届拿到比较好的成绩。对于我自己，我觉得应该多练习练习dp了，毕竟当时的摆渡车没想出来，这次的纪念品还有Emiya的这几道题都没有想到正解，哪怕是部分分的dp也没有丝毫的思路，作为一个下次想拿提高一等的人，我觉得是时候提高一下自己的dp水平了。 3.考试时发挥不出自己的真实水平。这个问题其实已经困扰了我好久了，几乎每次大考都发挥不了自己的真实水平，每次总归会突然做不出一些平常已经练习过好几遍的题目，OI考场上也是这样，学校亦是如此，但是我也没有什么好的方法去解决。所以这里想要问问读到这里的人，请问我这个蒟蒻该怎么解决这个问题 最后，祝广大Oler们都能达到自己预期的csp分数。 顺带吐槽一句：CCF什么时候感觉要想着全国树学奥林匹克竞赛发展了qwq ------------ # 期望与计划 期望是提高和普及双一等，提高250+，普及380+吧，加油！ #### 关于文化课 文化课的话其实就抓紧吧，因为自己的文科其实不是很好，补了好久也没有什么大的提升，所以还是按部就班吧，抓紧先把学校的课程搞好再去提升自己的信息（仅限于平时，特殊时期有其它的计划）。本人的语文和英语在年级中游。。。然后数学属于20左右的，理综的话大概是60+？平时的排名大概在70左右，下一学期尽量提升到50吧。 #### 关于信息 1.尽量在2020前刷完所有的普及+提高中力所能及的题目。 2.一周至少两道dp（不是裸的模板），这样到了明年csp就刷了100+的dp了。 3.自学完算法竞赛进阶指南中的大部分提高的内容，并把普及的内容全部复习并熟练掌握且能灵活运用（这条感觉有点困难，毕竟KMP至今都不会）。 4.做完的CF题每场div2补到E，div3全部补完（特别毒瘤就算了，比如CF601div2）。 5.尽量在平时能多刷刷题，但是不要耽误文化课。