CSP2020 J&S 游记
时律
2020-10-30 21:20:34
某一天：
> 时律 : 优良传统：初赛过后再写游记，没过初赛干脆不写游记
几天后：
> 时律 : 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》](https://music.163.com/#/song?id=406716121)和[《マインドブランド》](https://music.163.com/#/song?id=407485173)，今年发现耳机没电了，草（）
本来打算听[《凋》](https://music.163.com/#/song?id=1484790317)的，只好在宾馆听了
## 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，而且数组还开小了