CSP-J/S 2020 复赛游记

[更好的阅读体验](https://www.cnblogs.com/Appleblue17/p/14159746.html) ## CSP-J/S 复赛游记 ### CSP-J/S 2020 RP++ ## Day -4 / -3 / -2 这周每天中午都在机房打题，就没回过宿舍 不睡午觉有点疲倦，不过也没办法 主要是改之前的**一大堆**的模拟题 还有几个大佬中午也一起在机房 ## Day -1 呀，时间变紧了 赶紧打板子 线段树，树状数组，`ST`表…… `BFS`，`Dijkstra` , `Tarjan` ，树上差分…… ~~结果一个都没考到~~ ## Day 0 毕竟是第一次参加提高组~~第二次普及了~~，还是很紧张的，毕竟初中参加不了`noip` 然而还是要上数学课 然而学校还是考场 所以机房用不了了？！ 啊这 于是一大群人到处找电脑，跑到老师办公室去，跑到艺术楼的机房（为什么会有这个）去，甚至跑到化学老师那里去借 最后居然在宿舍向宿管借到了。。。 服了 晚上也没啥心情写作业，随便聊聊睡了 *** ## Day 1 ### CSP-J 2020 `6:30` 起床，发现起太早了，别人都没起来 ~~继续睡~~起来等到 `7:00` 吃饭，又等到 `8:00` 才去考场 到考场一看，依旧没有隔板 ~~毕竟机房确实没有~~ 我左右两位这次看起来专业一点了，起码没有玩 `Scratch` （ 终于看到一次有意思的密码了 ### 他山之石 *** ### T1 哇，这么水，跟去年差不多 时间复杂度：`O(logn)` 用时：`10 mins` 期望得分：`100 pts` 民间数据自测得分：`100 pts` 实际得分：`100 pts` ### T2 第一眼：插入元素，查第 k 大，平衡树请 第二眼：平衡树不是可以拿值域线段树代替的嘛 （开始打） （突然停下，看了眼题面） 第三眼：啥呀值域才 [0,600] ，桶装不就完事了吗？！ ~~（不过洛谷评测机好像有点歧视我的代码，卡了30多次才过）~~ 时间复杂度：`O(600n)` 用时：`15 mins` 期望得分：`100 pts` 民间数据自测得分：`100 pts` 实际得分：`100 pts` ### T3 好家伙阅读题终于来了 ~~还一堆废话~~ 啊这，后缀怎么处理啊 ~~平时模拟赛都是思维题都不会这些数据结构了（~~ 好吧首先要建棵树 树上先把原来的值算出来 然后在自上而下 dp 一下，没啦？ 不过讲真真不好打，就先去看 T4 了 …… 看了一眼打了个暴力又回来了 挺长的，`2k` 代码 这时候快没时间了，我随便出了一个 `5w` 大数据 #### RE了？？？ 害怕 可能是爆栈吧？我如此安慰自己 后来一想，之前写树哪一次爆过栈啊。。。 不理了，恐怕会挂成 `20 pts` 晚上一测，发现满了 （两天后） 我听说 `gets()` 不能用啊啊啊啊啊 （一周后） ### `gets()` 居然还是有分 ### 不过这东西太容易出锅了能不用就不要用吧 时间复杂度：$O(n)$ 用时：`90 mins` 期望得分：`20-70 pts` 民间数据自测得分：`100 pts` 实际得分：`100 pts` ### T4 第一眼：`BFS` （ T4 还能考 `BFS` ？） 第二眼：网络流 （看了眼数据范围，8行） 第三眼：$O(n^3)$ dp （看了眼数据范围，`70 pts`？？？） 然后我就先打了个暴力，又回去 `T3` 了 后来再想了想，把前和后更新的分开，然后拿后缀最大值搞成了 $O(n^2)$ 然后最富戏剧性的事情来了 #### 我直接把暴力交了上去 …… 时间复杂度：$O(n^3)$ （$O(n^2)$） 用时：`80 mins` 期望得分：`100 pts` 民间数据自测得分：`70 pts` 实际得分：`70 pts` *** 期望得分：`320-370 pts` 民间数据自测得分：`370 pts` 实际得分：`100+100+100+70=370 pts` 还是挺稳的 所以大家千万注意**不要交错文件**啊啊啊啊啊啊 后记：晚上测了测隔壁桌的，前桌 `170 pts` ，后桌 `230 pts` 针不戳 ### CSP-S 2020 中午回去睡觉，不在话下 这次大家还是蛮重视的 下午一进考场，不说别的，平均高度就相差很多（关注这个干嘛 ### 可以攻玉 （话说开考时这密码还挺难辨认的折腾了几分钟） *** #### T1 哇，一页题面 哇，阅读理解 哇，烦人模拟 开 $ \ $ 门 $ \ $ 红 ~~全机房都在做阅读题的感觉你体验过吗~~ 不说别的，这题面我硬是读了十分钟 大概从`1582`年开始分类 然后一年一年枚举，不然太烦了 然后打着打着我才发现 公元前`1,5,9,...` 年是闰年 这题太繁琐了我也不讲这么多了 大概 `40 mins` 才调出来 然后发现`T`飞啦 好像是年跳得太多了，模个`400`就行了 （但是好像被老爷机卡了……） ### 然后没开 long long ### 100->90 时间复杂度：$O(T(n/400+k))$ 用时：`45 mins` 期望得分：`100 pts` 民间数据自测得分：`90 pts` 实际得分：`90 pts` ### T2 第一眼：又是阅读……不会很难吧 第二眼：这……模拟？ 第三眼：不会真的是模拟吧。。。 ~~好像有点水~~（后记：烂了） 拿个`map`记录买的饲料，再枚举哪些位可以买即可 ### 但是你知道吗，map 存 1e6 会炸 ### 90->60 时间复杂度：$O(nlogn)$ 用时：`20 mins` 期望得分：`100 pts` 民间数据自测得分：`60 pts` 实际得分：`60 pts` ### T4 感觉进入正片了 哇哦，蛇会思考了（ 一只蛇要是不想玩了，立马就结束了 所以一定是最强的蛇不停地吃，只到有一只不想吃了 不想吃了，肯定是因为它能预测未来，再吃就会被别人吃掉 然而有可能它本来能被别人吃掉的，但在那之前游戏已经结束了 所以我们可以把整个过程弄出来，记录每一次的最大最小值 如果有一只蛇这一轮被吃掉了，而它之前有一次吃了别人，它就会反悔 好的那么这样就没问题了 但是当时我太傻了又没想清楚，结果做法假了 但奇怪的是洛谷数据只挂了一个点（听天由命） 时间复杂度：$O(n^2)$ 用时：`60 mins` 期望得分：`55 pts` 民间数据自测得分：`50 pts` 实际得分：`40 pts` ~~（数据也太水了）~~ ### T3 数据结构题？ 乱想了想，好像可以拿拓扑排序+线段树合并做（当然正解不是这个） 但线段树合并……不太好打 于是先随便打了一个 `20 pts` 的暴力 这个区间乘也太耗时间了，线段树？ 整体区间乘耶，就不麻烦线段树了 弄一个 `laz` ，到时候所有数都乘上 `laz` 不就行了吗？ 那加 `k` 的话就变成加 `k/laz` 了 ### 然而我忘记特判0了 ### 75->50 （这数据真的不是随机出来的吗） 距离结束还有一个小时，开始搞线段树合并 然后……自然也没调出来 代码都 `3k` 了 时间复杂度：$O(?)$ 用时：`30 mins` 期望得分：`30 pts` 民间数据自测得分：`25 pts`（乘0的逆元） 实际得分：`50 pts` ~~（这真的太水了吧）~~ *** 挂得好多啊…… 太菜了 期望得分：`305 pts` 民间数据自测得分：`205-225 pts` （差得有点多啊） > 洛谷 90+60+25+50=225 > Outiku 90+60+75+50=275 > 牛客 90+60+80+25=255 实际得分：`90+60+50+40=240 pts` 其实还行？ 真心希望能拿个一等奖，也不枉两年的 `OI` 生涯与努力 希望能~~卡线~~过 ~~（希望渺茫）~~ *** ## 希望能捞个双一！