CSP2019 游记
又到了退役的日子了……
2019/11/14 之前
$91.5$ 分碾线过初赛，经历期中考的折磨，然后……马上就要出发了。
2019/11/14
日常颓在机房。
下午模拟赛。
前两题送分题，上来切了。
第三题是个神奇的最优化问题，我无从下手……然后随便打了个连大样例都过不去的贪心就跑了。得分 $20$。
然后学校里好像发生了一些事情（不方便透露），希望接下来这几天身体安好。
明天，出发了……
2019/11/15
9:00
昨晚 $11$ 点打的。CSP 的 rp 不会用光了吧？
今天早上本来有场“信心赛”？被我鸽子了。还是在家睡觉舒服QAQ
还没出发，先写一些自我提醒吧。
- 看清范围，合理估计空间，不要开小或开大数组。
- 合理分配考试时间，不在有十足把握的情况下使劲刚一道题。
NOIP2018 D2T2 的教训。 - 尽量写较优的时限。能写一个 $\log$ 的就写一个 $\log$，想不到更优的话，那常数尽可能实现得优一点。
- 不开 C++11 的话，注意一些关键字的冲突，以及头文件开全（用 freopen 一定要开 cstdio 不能只开 iostream）。防止莫名 CE。
- 尽量用那些确定能用的东西，无法确定的最好别用。
- 没得开 O2 的话，更要注重效率。
- 心态要好，多拿分，尽力就行，不要留下遗憾。
玩得开心。
那，暂时写这些。
下午，如果停车场（雾）出现一个抱着小鲨鱼的小家伙，那大概就是我吧……
11:40
吃完饭了。
早上不知道在干嘛，就这么水过去了……
整了点东西，再过会准备去学校集合了。
然后这个游记硬是被我写成了动态？
这样也不错嘛。
17:25
到宾馆了。
并没有去康考场啊……
不管了，反正在宾馆里待着就好了。
各位明天见吧。
准考证号：ZJ-00642
21:30
打了几把麻将被虐爆了……
写了道点双的题练习，看了点板子。
Day 1 RP++！
2019/11/16
6:55
昨晚睡得不错，早上起来精神还行。
各位都加油啊！
13:00
真是自闭啊……
T1 格雷码，告诉你怎么模拟了，随便搞搞就好了。
T2 简单的树上问题，没多久就搞定了。
接下来干 T3。
看完题目，看完部分分，我自信地以为这些部分分都挺好写，就花了一半的时间搞正解。
然后没搞出来……
开始写暴力，先写个 $10$ 分的阶乘大暴力，这个没啥问题。
然后写链和菊花的。开始写了才知道自己有多 naive……
花了一个多小时写了两个暴力都是假的……
然后根本没有想过去检查 T1 和 T2。就结束了……
出来后好像大家都和我同样的感受？
不挂分的话就 $210$ 了。我真是自信……
还有考试前见到 zhouwc 了，超级帅的小哥哥呢~
23:30
下午反正就一直颓……果然还是不要去想今天的分数了吧。
于是……
狠之间太可怕怕掉分
睡了睡了，做个好梦。
2019/11/17
6:40
今天也要继续加油。
15:15
考完直接回来了。
今天的题，某种意义上，可能比昨天要良心？
开始时觉得挺难，T1 盯了好久，以为是啥流题。不过流不能计算方案数啥的。
大概 $40$ 分钟的时候，想到了计算有一个超过一半的方案数然后减去，做个背包就好了。
$1$ 小时左右写完了 $O(n^2m)$ 的做法，过了大样例就溜了。
然后看 T2 和 T3，稍微想了下 T3，感觉是个可做的数据结构题，再看了 T2 感觉是不太可做的难题。就准备先打 T2 的暴力。
看完一眼秒出 $O(n^3)$ 做法，记 $f[i][j]$ 为前 $i$ 个数，最后一段长度为 $j$ 的最小值。发现 $j$ 增大的时候和也增大，就直接令 $f[i][j]$ 表示前 $i$ 个数，最后一段长度小于等于 $j$ 的最小值，然后用一个指针转移。就 $O(n^2)$ 了。
想 T3 的时候大概还剩不到 $2$ 小时。仔细思考一波，就是计算每个点作为重心的次数，然后用数据结构维护一些子树大小信息，直接查询。
换根的时候，原来的父亲的子树大小会变化，我直接用一个树状数组维护整体的子树大小信息，然后以 $1$ 为根的每棵子树的子树信息直接线段树合并上来。时空复杂度都是 $O(n\log n)$。
剩下的时间，我也没仔细想 T2，感觉可能是单调队列啥的但写不出。然后就拍了下 T3，给 T1 测了下速就跑了。
没挂的话，就是 $100+64+100=264$ 吧。挂了的话就……
走之前还见到了 memset0 神仙。
然后就回来辣……等出了分再更新吧……
2019/11/19
出程序了，赶紧到处去测。
洛谷数据：$100+100+10+100+64+100=474$
SOJ 数据：$100+100+10+100+64+100=474$
牛客数据：$100+100+10+100+64+90=464$
其他一些地方测，好像都是 $474$。姑且认为牛客那个编译器菜吧。寄希望于 CCF 少爷机。
终究没有挂分吧……那也只能说我是正常发挥罢了。
为什么，今年，会有那么多人离开？
机房里的欢声笑语，过了这 CSP，都没了。
平时还有哥哥陪我水水群，过了这 CSP，也没了。
似乎，考完当天的我，自我感觉很好呢……
终究，还是要感伤吧。
说我考得好吗？也不好。D1T3 的暴力分，D2T2 的暴力分，我终归没有拿到。
终究，不要再悲叹了吧。
真正运气不好的，并非是我。
路还长……
愿一切安好。
2019/11/21
打算补今年题的坑了（虽然也没多少）。
格雷码2019/11/16
括号树2019/11/16
树上的数
Emiya 家今天的饭2019/11/17
划分2019/11/21
树的重心2019/11/17
2019/12/1
15:30
出分了。
没有挂分啊，万幸。
D1T3 太毒瘤了先咕着吧。
来康康这个题吧。
如果可以的话，WC2020 见。