「你说那是消磨 笑柄 罪过」

「你说那是消磨 笑柄 罪过」

「但那就是我的英雄主义」

CSP2020 J&S 游记

posted on 2020-10-30 21:20:34 | under 娱乐 |

某一天:

时律 : 优良传统:初赛过后再写游记,没过初赛干脆不写游记

几天后:

时律 : PJ 81.5,TG 78,坐标 ZJ,都过不了(

结果分数线一出……

J组入围线77.5分,共805名,S组入围线71.5分,共796名。

啊还好,初赛过了,那就写游记吧

Day ? ~ -8

这些日子教练在给我们做往年 NOIP 普及组的题 (2012 ~ 2016)

基本上 T4 都只会暴力 /kk

Day -7 (2020.10.30)

今天学校开展了一个什么奇怪的活动,绕着七都走一圈(15km)

预计 12:30 回到学校,结果 14:00 才到

路上一不小心就立了女装 flag:如果今年我S组有一等就女装()

然后引起了一帮人讨论穿什么

晚上准备开始搞提高组的题

打算先搞 17 年……?试试看吧

二黄一蓝三紫,我好害怕

21:46:07  AC 了 P3958 奶酪

看了一眼逛公园决定还是去睡觉吧

Day -4 (2020.11.2)

今天体测。引体向上 12 个,应该有全段第一吧 然而并没有

50m 7.56s,坐位体前屈和跳远由于有点差就不说了()

今天搞 18 年的普及

12:17:38  AC 了 P5015 标题统计
12:34:24  AC 了 P5016 龙虎斗
22:06:20  AC 了 P5018 对称二叉树

摆渡车老难了

Day -1 (2020.11.5)

教练中午把比赛相关事项讲了一遍

想法是:提高组(据说四题) A 掉 T1,尽量搞 T2,T3T4 暴力()

暴力出奇迹,骗分过样例!

Day 0 (2020.11.6)

打一遍模板。

线段树 √
树状数组 √
快速幂 √
欧拉筛 √
并查集 √
ST表 √
LCA √
Kruskal √
Dijkstra √
SPFA √
Floyd √
快读 √
快速排序 √
归并排序 √
单调队列 √

和 yjt 一起坐车(?)

去年在车上听着《Miku》《マインドブランド》,今年发现耳机没电了,草()

本来打算听《凋》的,只好在宾馆听了

Day 1 (2020.11.7)

在宾馆起床后对着镜子摆了个乔鲁诺立来检查自己的仪表(?)

早上J组。

7:40 在门口集合,一堆人 7:30 就到了,结果教练准时的在 7:40 到了。

接着找到机房进去,准备了一下。

密码是 Ta&Shan?Zhi@Shi%

8:20 开始看题,浏览了一下,T1 还是那么的水 (虽然是阅读理解),敲完的时候 8:45。

T2 一眼看上去是排序, $n<=100000$ 像是 $O(nlogn)$ 的做法。快排,归并,堆排?

分析了一下最有可能的是堆排,但是我不会手写堆。草为什么昨天晚上我不复习堆排

绝望之时看到每个学生的分数 $<=600$。桶排走你。

写完的时候是 9:05。看了一下 T3,一眼感觉很麻烦,便去看 T4。和去年一模一样呢

T4 言简意赅,数据是 $n,m<=1000$。思考一下就会发现搜索会 T 到飞起,果断想到了一种 $O(n^2m)$ 的思路可以搞到 70 分。

9:30 敲完,接着去看 T3。后缀表达式有点恶心,竟然在这个方面纠缠了半个小时才想出来怎么把这玩意转化成树。

考虑到每次修改都是临时性的,也就是说每次只会有一个数变化,而且每个数只会在表达式中出现一次,所以有相当大一部分的表达式是没有变化的。预处理这些表达式,可以让每次询问的复杂度变为 $O(logn)$。

算了一下复杂度应该能过,10:30 的时候再去搞 T4。

把 T4 玄学优化了一下,虽然还是 $O(n^2m)$ 但是这玩意在最好情况下能达到 $O(nm)$,平均复杂度大概接近 $O(n\sqrt{n}m)$,应该能过。

这个时候是 10:45。还有一个小时多。

我……AK 了?

出去上了个厕所,发现监考老师在看番

检查了 N 遍,每道题大样例都过了,然后无聊了好久最后出了考场。

出考场后:

yhxf:感觉今年的题目比去年都要简单啊

我直接膜拜好吧

下午S组。

密码是 (ke2YI0gong2YU0)。既然上午是他山之石,果然下午就是可以攻玉()

看题。T1 竟然是大模拟……?

于是就花了一个小时写了 300 多行,期间把水和巧克力全解决完了。两个小样例没有问题,大样例出现了奇怪的情况:有些答案对了有些没对?

再调了半个小时,没辙。去看第二题。

第二题读了好几遍才懂,打了一个及其暴力的暴力后去看第三题。

第三题还是暴力。

第四题仍是暴力。

此时剩下一个小时,回头去看第二题,找到了一些规律。

如果一种饲料已经被任何一只动物所需要,那么其他动物需要它也没关系。但是如果一种饲料不被任何一只动物所需要,题目所求的其他动物必须也不能要这种饲料。

于是便在读入的时候预处理每只动物的二进制第 i 位是不是 1 ,然后就可以求出有多少位的饲料是当前的动物没有需要的。

设这个数为 p,那么问题即化为

有 k 个数,每个数为 0 或 1,其中的 1~p 只能为 0。求此满足此情况的方案数。

所以便是 $2^{k-p}$。但是还要把这个数减掉 $n$。

所以答案为 $2^{k-p}-n$。

大样例过了,还剩半个小时。T3 仍无思路,看 T4。

T4想到了一种 $O(Tnlogn)$ 的思路,结果死调都调不出来,只好放弃。

然后出考场。听到大家都说 T2 简单,我觉得我 T2 应该稳了。

一段时间后到了动车站,因为之前买了学生票得改成人票花了好一会儿时间,差点没赶上车。

Day 2 (2020.11.8)

洛谷自测:

J:100+100+0+50=250 草,T3不知道为什么爆了

S:10+90+0+20=120 草

Day 3 (2020.11.9)

J组懂了,T3数组开小了(然而开大之后还是0分),T4后来点优化想法错误了,如果用之前的 $O(n^2m)$ 还能有 85 分。

我死了。

AFO。

草,等下,教练说今年 J 组分数线在 230~250

有希望!

教练又说洛谷T3数据有错,换个地方测T3还有20,耶

Day 11 (2020.11.17)

J:100+100+70+30=300

S:20+95+20+20=155

草,J组T3怎么有70,而且数组还开小了