成绩还没有出来,105分有点慌,只希望能够过线。
DAY 1
不敢相信,这次CSP-S在本校(本人在九中光华集训)!!!下午考试,上午就直接在寝室里面睡大觉,睡到了早上10点左右,感觉精力很充沛。上午在寝室里面复习,重新写了一遍强连通分量,还写了一遍spfa和dijkstra,然后就准备中午吃饭了,吃完饭本来是准备再睡会觉的,然而突然发现我还没有复习逆序对,于是中午没有睡觉,把逆序对的归并排序的板子背了,就准备去考场了。
(发现还是中午睡个觉会比较好)到了考场,心里面想了一下策略:首先,先把题读一遍,看一下题的难度,然后再开始写,最后留下30分钟调虚拟机。
考试开始了以后,我先看了一下题,第四题感觉很难,而且不好骗分,想着如果没时间就不用看了,第一题,完全没有思路,想了一下动态规划(本人动态规划不是很会写),但发现好像不能用动态规划,因为一条链可以跳出去又跳回来,这时候我反而还有点开心(因为肯定不是动态规划了)。然而过了10分钟我还是没有一点思路(这时候考试都开始20分钟了,我还没有开始写代码),于是我决定先看看能不能拿部分分,一看,特别开心,竟然有45分的情况下\(k=0\)。这种情况下就是从起点开始长度为\(5\)的链里面权值最大的,直接写了一个\(DFS\),然后跳到第二题。
第二题经过5分钟的思考,发现需要多次询问区间最值,第一反应就是线段树,又发现这道题还不用修改,直接就写了线段树,但是我在想,当数列里面有负数的情况增怎么办,我想到了写\(6\)个线段树,每三个分别维护两个序列中的最大值,最小值和最接近\(0\)的值,但是写到一半发现这没有正确性。大无语,怎么办,我想正解肯定没有这么简单,于是我就去想怎么拿到部分分,然后我就写了一个暴力,较小的数据范围用暴力来跑,较大的数据范围用线段树来跑,线段树就只处理所有数为正数的情况。
写完第二题,算了一下分数,如果不出意外应该是已经有了100分了。开始写第三题。第三题的题目好长啊!!!读了\(10\)分钟的题目,然后在草稿纸上画了一下,发现每个地点只有一个出度,并且图里面要有一个环,然后直接建图,但是我脑子不好使,不知道为什么建了一个反图,然后开了一个数组统计每个点的出度,然后首先判断是否所有点的出度都是1,然后再跑一个\(DFS\)判断每一次能不能找到一环,如果找不到环就输出\(NO\)如果找到了环就继续找下一个环,知道所有点找完,每次找到一个都打上标记,这样就不会重复找(稍微降低一下复杂度)。写完以后发现时间只剩下了\(20\)分钟,然而我还没有调虚拟机,我第三题样例都只测了第一个,就急忙去开虚拟机了,把虚拟机调好然后把\(Warning\)基本上改完,最后再检查了一下头文件。
终于交上去了,考完力!!!
DAY 2
然而,考试第二天,噩梦。在\(luogu\)自测上面一测,直接吓死,第一题暴力写挂了!!!只有20分!!!在\(infoj\)上甚至只有10分!!!完了,寄……再测一下第二题,55分!!!寄!!!完蛋,暴力的范围判断小了!!!我试着把判断用暴力解得范围调大一点,直接\(55pts->75pts\)!!!寄了啊。后来又听同学说第二题其实可以开\(8\)个线段树分别维护两个序列的正数最大值,正数最小值,负数最大值,负数最小值。啊啊啊,我差一点就想到正解了啊!!要是当时再稍微多想一点,不就多了\(45\)分了吗?总结就是有思路了可以多想一下,要不然后悔莫及。哎,都不敢测第三题了,算了反正都挂成这样了,测测也没关系了。于是就交到\(infoj\)上测了一下,竟然有\(40\)分!!!我当时都只测了一个样例。完全没有把握的题竟然拿了\(40\)分!最后算了一下\(10+55+40=105\)有亿点点惨。希望\(CCF\)大发慈悲,不要\(AFO\)就好了。