Appleblue17 的博客

Appleblue17 的博客

大头蜜蜂欢迎你!

CSP-J/S 2020 复赛游记

posted on 2020-11-08 00:09:15 | under 未分类 |

CSP-J/S 复赛游记

CSP-J/S 2020 RP++

Day -4 / -3 / -2

这周每天中午都在机房打题,就没回过宿舍

不睡午觉有点疲倦,不过也没办法

主要是改之前的一大堆的模拟题

还有几个大佬中午也一起在机房

Day -1

呀,时间变紧了

赶紧打板子

线段树,树状数组,ST表……

BFSDijkstra , 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 生涯与努力

希望能卡线

(希望渺茫)


希望能捞个双一!