【杂文】CSP2019蒟蒻AFO(假)记

# **【杂文】CSP2019蒟蒻AFO(假)记** [$\mathcal{My Blog}$](https://www.cnblogs.com/Xing-Ling/p/11755700.html) ## **【初赛前 N 天】** ### **时间：2019-10-15** 今晚 $2012$ 的初赛题做到心态爆炸，选择考计算机基础知识一脸懵逼，填空和后面一道大模拟直接跳过，最后居然还得了 $60$ 多分。 ## **【初赛】** ### **时间：2019-10-18（day0 前一天）** 昨天做了 $NOIP2016$ $day1$，原本应该是 $2s$ 时限的 $T2$ 老师没注意只开了 $1s$，然后就被卡掉了 $5$ 分，今天做 $day2$ 时又被老掉牙的 $Cena$ 给坑掉了$95$，心态爆炸。 （晚上） 一边听 $y$ 总讲组合数学，一边临时恶补初赛知识点，感觉今晚学到的东西（初赛）比这一个月来总结的还要多很多。果然啊，人在面对险境时总能爆发出不可思议的力量。 ### **时间：2019-10-19（day0）** 艹晕车，到考试地点后脑子里面一片混沌，早上刚背的知识点全忘光了。 不得不说单选还是挺水的，结果后面阅读和完形直接原地爆炸螺旋升天，送上来的坑点一个都没踩漏，还有最后一道状压推了接近一个小时没看懂。 对脸懵逼。 下午用网上流传的问卷星测了一下，居然有 $83.5$，感觉应该是稳了吧。。 ## **【复赛前 N 天】** ### **时间：2019-10-28** 九校联考凉心模拟 $\text{day2}$。 $\text{T1}$ 就是个简单期望 $\text{dp}$，结果死活推不出来，白嫖了 $50$ 分的蒟蒻递推。 $\text{T2}$ 神奇的数论推结论然后上 $\text{CRT}$，也不会，码了个暴力。 $\text{T3}$ 一眼 $\text{LCT}$ 板子，但不会写，于是上了个暴力+离线树上倍增。 期望得分：$50+50+30=130$ 。 实际得分：$50+20+30=100$，$\text{T2}$ 卡常没卡过。 （好像只有我一个人上了 $100$ 哎） $\text{Trie}$ 树巨佬 $\text{lsy}$ 又一次用神奇解法吊打了 $\text{std}$，可惜的是考场上没调出来。 > 我真的觉得我的写法非常简单，瞬间就想出来了，而且代码也很好写，不就是个启发式合并加树上懒标记维护动态倍增 $\text{lca}$ 嘛。—— $\text{lsy}$ *我好菜啊。* 离比赛已经不足 $20$ 天了，回想起去年的毒瘤题，感觉现在自己去做的话，会做的依然会做，不会做的还是不会。 而据说今年的题会更毒瘤。  唉，等联赛后就直接 $\text{AFO}$ 了。 ### **时间：2019-10-29** > 大部分题都可以用 $Trie$ 树搞。—— $\text{lsy}$ $\text{stOrz}$ ### **时间：2019-11-1 至 2019-11-3** （电脑E盘被打穿祭） 受机房同桌 $\text{hyj}$ 诱惑，和他一起从不明渠道下了个破解版的绘图软件 $\text{AxGlyph}$，打开看了看感觉还不错。。。 第二天早上，打开浏览器提示[僵尸网络](https://baike.baidu.com/item/%E5%83%B5%E5%B0%B8%E7%BD%91%E7%BB%9C/5391691?fr=aladdin)，虽然感到很奇怪，但因为老师已经发下了考试题目，所以就专心做题去了。 （离考试结束还有两个小时） 题目比较水，闲得无聊又打开了这个软件，惊叹其功能之强大堪比几何画板。 （下午） 僵尸网络又来了，突然意识到事情可能不太对，询问老师又无果，只好换了机子。 （第三天） 周末收假回来捣鼓了一下午，最后让 $360$ ~~危险~~卫士出面搞死了数以千计的 $\text{virus.vbs.writebin.a}$ 病毒。 开始计算损失：装满了各种软件的 $E$ 盘被全部打穿；$D$ 盘里面的学习资料较为安稳，只有少数几个 $htm$ 遭了殃；至于 $C$ 盘嘛，教练设置的重启自动数据还原都救不了，才刚开机一小会儿就直接全军覆没。 漫长的查毒杀毒过程中，无所不知无所不能的 $zth$ 巨佬带着一脸 $\text{yin dang}$ 笑容走了过来。 > 等等，放下那只病毒！用记事本打开它，来，让我康康。$\text{emmm...[aoturun]...}$ 原来如此。那个 $\dots$ 你那什么病毒，给我留一份哈，我放到虚拟机里跑一下看看 只见他熟练地打开 $cmd$，用文本模式打开了一个受到毒害的 $htm$ 文件，在一长段字符中找到了问题所在，并秀了一波凡人看不懂的操作。 # **zth 太巨啦！** （晚上） 打包的部分病毒样本（疑似）和一只可怜的受害者（上面说到的 $htm$）被保存了下来（~~预测以后将会成为高级jc的作案工具~~）。 > 哎，你说这只病毒可不可以娘化呢？——把我给坑惨了的 $\text{hyj}$ ### **时间：2019-11-12 至 2019-11-14** 把所有学过的板子都挨着敲了一遍。 ## **【复赛】** ### **时间：2019-11-15** 今天居然没有晕车，顿时心情大好。下午在宾馆闲着没事干看了几篇论文，不知道会不会派上用途。 ### **时间：2019-11-16（CSP-S day1）** 第三次来到这座学校，去年的自闭记浮现在了眼前，唉，希望今年不要再翻车了。 （进入考室） 也许是太紧张了，找不到开机键？？？只得求助工作人员，旁边的小哥一脸诧异地望了我一眼（唔，好尬啊） 开机后迅速码好头文件和快读，看看时间刚好 $8:30$，于是抬头看大屏幕寻找 $ftp$ 地址 $emm....$ 地址呢？都已经到点了，为什么还没有公布啊，难道咕咕咕了？ 果不其然，当工作人员拿着 $U$ 盘依次插入隔壁小哥的主机时我便明白了一切。 应该要等会儿才公布发密码，闲着无聊花几分钟敲了个 $LCA$，熟悉了下键盘，感觉手感还不错，比学校机房里那个已经老化了的键盘好多了。 $md$ 谁设计的密码啊，丑死了，输了无数遍才发现后面居然有个问号，解压出来后又只有数据没有题面，喵了眼隔壁小哥，他似乎只有题面没有数据，搞得我差点笑出声来。 最后在 $rar$ 的准备界面里把 $pdf$ 强行拖了出来，开始看题。 $T1$ 题面这么长？难道是大模拟？心里顿时一凉，喵了眼 $T2,T3$，两个树论？但 $T3$ 的数据范围有点不正常。 回过来看 $T1$，反复琢磨了几遍题意，除了要开 $ull$ 外，貌似没啥坑点，就是个蒟蒻小模拟，随手敲了个递归（突然发现三次大考 $\text{day1 t1}$ 都写了递归 $\text{QAQ}$），为防位运算爆 $ll$，还专门预处理了一个 $mi$ 数组。但不知道为什么写挂了，调了一会儿发现了个 $\text{SB}$ 错误，一发过大样例，测了下 $64, 2^{64}\!-\!1$ 的极限数据，貌似没啥问题（考完才意识到没有数 $0$ 的位数，希望不要挂），看了看时间 $9:20$，和预估的时间一模一样，准备开 $T2$。 $emm...$ 链的部分给了非常诱人的 $50pt$，果断开链。问题被放到序列上，首先想是否可以继承，发现还真可以，直接 $dp[i]=dp[i-1]+f[i]$（$f[i]$ 表示以 $i$ 结尾有多少个合法子串），想到这里突然意识到：可以直接在树上 $dfs$ 的时候顺手就把答案维护了出来。虽然平时写树 $dp$ 都是边写边思考，但为了保险，还是往深处仔细想了想，似乎没什么问题，开始码码码。。。。 问题是如何得到 $f$ 数组，一开始写了个栈，但不太好处理，于是换了种写法：用 $w[x]$ 表示从 $x$ 到根的路径上第一个可用的左括号位置，设 $W=w[fa[x]]$ 则有 $f[x]=(W\!!\!=\!0)+f[fa[W]],w[x]=w[fa[W]]$，一发过样例、中样例，大样例崩溃，由于忘了如何手动开栈，果断上 $Linux$，顺便把 $T1$ 的数据也拷了进去，测了一遍发现全 $A$，看看时间 $10:19$，比预估早了一分钟。 $T3$ 链和菊花加起来有 $60$，先想链吧，貌似可以贪心，保险起见先打爆捜。$10min$ 后，开始了漫长的 $debug$ 之旅（$md$ 写个暴力都能挂），大概半小时后发现输入和我想的不太一样，改来改去始终过不了，仔细琢磨了下题面，涌起一股想要把出题人锤一顿的冲动. > 此时这条边所连接的两个结点上的**数字**将会交换 鬼知道你这里说的 “**数字**” 是指点权还是节点编号啊！！！害我调辣么久。 过样例后发现还有 $45min$，想了想菊花没啥思路，老老实实开链。 喵喵喵？ 码了七八十行发现思路有问题，唉，开考之前就在不断提醒自己要三思而后行，结果还是太冲动了。 看看时间还剩 $15min$，这时候应该也翻不出什么风浪来了，于是又把 $T1,T2$ 捞出来看了看，放到 $\text{Linux}$ 下再测了两遍。 $12:00$，收拾好笔和身份证准备走人，喵喵喵？为什么还不结束啊？难道是要延时？工作人员都不说一下的吗？早知道就应该把 $T3$ 再好好想想了。。。 找了找开始界面发现居然没有扫雷，差评。 出考场后听学校里一个拿了金牌的高三学长说他 $T3$ 只打出了 $25pt$ 的链，加起来 $35pt$，看来这次的 $T3$ 有点毒啊。 期望得分：$100+100+10$ 。 $day1$ 好像人均 $205-210$，没有区分度，希望明天能拿个不错的分数。 还有半个下午 $+$ 一整晚的时间可以颓，看番去咯！ （晚上） 听教练说今天的题过于zz，明天应该会柔和一点，考些简单算法、数据结构之类的东西，对我们来说最容易发挥实力。 ### **时间：2019-11-17（CSP-S day2）** > 晨起路途漫霜雾，迷惘不知何处。 > 归来寒风等闲度，不如心中愁苦。 也许是因为太冷了，今天进考室的时间似乎比昨天早一些。 还是那熟悉的桌面，不过 $\text{Dev}$ 被昨天下午的小朋友给弄成了一堆乱码，一时间不知所措，便去询问工作人员，隔壁小哥又一次向我投来了奇异的目光。 好在昨天存的快读$+\text{LCA}$ 板子还在缺省源里面，看看时间 $8:10$，飞速敲了个珂朵莉树和半颗线段树放在一边，准备打莫队时解压密码公布了出来，于是放下键盘去做准备工作。解压出来依旧是没有题面 $pdf$，需要强行拖拽。 今天出题人良心发现给了很多大样例。 $T1$ 题目描述比较恶心。看起来和一道二分图的题比较像，但这道求的是方案数，应该是计数 $dp$ 。$m=2,3$ 的情况有 $64pt$，研究了一会儿码了个暴力 $dp$：$f[i][p][j_1][j_2][j_3]$ 表示考虑到第 $i$ 种烹饪方法、共做了 $p$ 道菜、材料 $1,2,3$ 分别用了 $j_1,j_2,j_3$ 次的方案数，大力转移即可，$m=2$ 的同理，由于 $j_1,j_2,j_3 \leqslant n/2$，所以不需要优化也能轻松过掉 $n \leqslant 40$ 的数据。 $T2$ 首先想到的是斜率优化，但限制条件貌似不太好处理，决定先码个 $64pt$ 的暴力放这儿，等拿到 $T3$ 的部分分后再回来写正解。朴素思想是用 $dp[i][j]$ 表示处理了 $[1,i]$ 且最后一段为 $[j,i]$ 的最优答案，时间复杂度 $O(n^3)$ 。后来意识到可以用一个辅助数组 $g[i]$ 记录点 $i$ 的最优决策点（即最后一段的左端点），直接 $n^2$ 搞定：$dp[i]=min\{ dp[j]+(S[i]-S[j])^2 \} (S[j]-S[g[j]] \leqslant S[i]-S[j])$，一发过大样例，丢一边准备开 $T3$ 。 $T3$ 照着题意随便模拟一下就有 $40pt$，愉快地敲完 $n^2$ 模拟，加上 $15pt$ 的链，$day2$ $183$ 到手，加上 $day1$ $393$，此时离考试结束还有一个半小时，冲刺一下应该有上 $400$ 的可能。 目前还有两个任务需要完成，但由于时间的限制，需要舍弃一部分： $(1).$ 用一种特别麻烦的蠢方法写 $T3$ 的二叉树情况（$20pt$） $(2).$ 尝试 $T1,T2$ 可能成功的难点突破 $(36pt+36pt)$。 犹豫了一下，最后决定放弃二叉树，毕竟想出正解的回报更丰厚。 可惜的是，对 $T1$ 容斥 $+$ 计数 $dp$、$T2$ 斜率优化的尝试最后都以失败告终，直到考试结束依旧还是这个分数。唉 $...$ 亏大了。 退出考室后顿时心凉了半截，今天肯定人均 $203+$，而我因为贪图正解分数的肥美，连 $203$ 的基础分都没拿全。 期望得分：$64+64+40=168$ 。 （后来发现 $T3$ 数据描述中看漏了 “存在一种 $1$ ~ $n$ 的排列 $p$ 使得XXX” 导致那 $15pt$ 的链也丢掉了，所以只剩下了 $40pt$ ） ### **总结** $day1:$ 模拟 $+$ 树形 $dp$ $+$ 爆捜 $day2:$ 暴力 $dp$ $+$ 暴力 $dp$ $+$ 暴力树形 $dp$ 期望总分：$210+168=378$ 。 今年考了 $3$ 棵树。 作为一个暴力数据结构选手来说，这本不是坏事，奈何出题人过于 $dului$，根本不留活路。。。 ~~md 这一年的算法都白学了，到头来啥都没用上，去年高一好歹还码了个最短路，今年居然全写了 dp。~~ 考联赛烂成这个样子，只有退役了。 最后的机房时光在局域网联机 $mc$ 中愉快度过。 文化课我来啦！ ### **时间：2019-12-2** 咕咕 $\text{F}$ 终于放出成绩了，和预计的一样：$378$ 。 虽然分不高，但排名似乎还不错？ 那就 $...$ 文化课拜拜啦！ $\text{SCOI}$ 我来啦！