神犇的CTSC：怒A数据结构题，狂虐DP题，吓傻出题人。

蒟蒻的CTSC：捞点部分分，磕提交答案题，依赖出题人的良心。

我就是蒟蒻啊- -两天CTSC得分最多的题都是提交答案题……

先祝贺一下咱们学校的神犇 @kfdong 过关斩将进了IOI！神犇 @immortalCO A掉第1天第1题，直冲rank8！

——————————

Day 0。

5月1日，早早地赶上了到北京的飞机。（心想还有好多题不会，真是无比虚啊）

和 @immortalCO 交流了一些算法。

由于比较早，比较困，所以大多数时间都在休息【老师：今天的主要任务是休息

我依旧处于颓废状态于是晚上也没刷什么题不到22点就去睡觉了233333（另外宾馆不错）

——————————

Day 1。

设了6:30的闹铃但事实上不到6:30就醒了，然后开始紧张上午的比赛（Day 1就那么紧张干吗）

吃完早饭进考场脑子一片空白，盯着时间看，8:25，8:26，8:27，8:28，8:29，8:29:30，……

开始了。

（由于我比较逗比先看到的不是试卷上的题目而是文件夹）

travel，suffix，noip。

前两个看样子是传统题，第三题noip就比较有亮点了（我猜它一定叫“NOIP十合一”），看样子是一道有趣的提交答案题。

看题。

第一题好长，似乎是一道码农数据结构题，先写个暴力吧，等下……

第二题不长，但一看就完全没有思路，似乎是一道巨丧的DP题，先写个暴力吧，等下……

第三题果然名称叫“NOIP十合一”，似乎比前两题都可搞。先开始做这题吧！

打开第一个点，一个简单的图：1->2（边权为1），1->3（边权为0），2->3（边权为0）；3->4（边权为1），3->5（边权为0），4->5（边权为0）……

看样子有好多个子结构，每个有走1和走0两种，那么如果经过了$k$个子结构，要使路径长度为$w$，方案数就是$C_k^w$。

可是模数居然不是质数！质因数分解吧，存个指数（好在模数是$2^p3^q$的形式）。感觉细节很多要挂的样子。

搞出了第一个点，过了sampleout，有分心里就踏实许多了。

第二个点，有边权的都是自环，这不就是完全背包么= =询问都是从1开始，直接DP了一发很快就跑出来了。

第三个点，有边权的都是自环，但询问不是都从1开始，而且$n=10000$……

——利用提交答案题的特点，跑$10000$遍完全背包！

经过检查确保没有数组忘记清空以后一边跑一边写前面的暴力去了。

……发现第一题的暴力其实挺好写，代码30行左右很快就写完了（对拍器get，5分get）

……第二题的暴力就有点难写了，老是错，调完以后一直过不了样例2，不知道哪里写错了。

实在不知道哪里错，就不管了。

第三个点总算跑完了。

第四个点，点数才5，询问$w$也不大，直接DP就行了。设$f(u,v,w)$为从$u$到$v$长度为$w$的路径数，则$f(u,v,w)=\sum_{(u',v)\in E} f(u,u',w-w(u',v))$，其实$u$这一位只是表示DP要做5遍罢了- -复杂度是$O(nmw)$，还得等一会儿。

一边跑一边看第五个点，发现数据很有规律地在边中出现了11,12,13,...的点，看样子是强行拆点拆出来的，把这些边并回去就和第四个点差不多了，只不过点数变成了10。把第四个点的程序稍微改了下。然后感觉好像有细节。

此时已经2个多小时了，预计得分5+0+50=55。似乎是滚粗的节奏。

再看第六个点，点数200，边权都是1，但$w$非常坑爹地变得巨大了。

题目中给的提示是个看不懂的神奇东西，唯一知道的是“矩阵”。邻接矩阵？矩阵乘法？矩阵快速幂？

矩阵乘法的定义是$c_{i,j}=\sum_{k=1}^n a_{i,k}b_{k,j}$，就相当于从$i$出发经过$j$到$k$的路径。如果$A$是$G$的邻接矩阵（定义有点不一样，$A$的$(i,j)$表示有多少条从$i$到$j$的边），那么$A$的$(i,j)$表示$i$到$j$长度为1的路径数，而$A^2$的$(i,j)$表示$i$到$j$长度为2的路径数，类似地，$A^w$的$(i,j)$表示$i$到$j$长度为$w$的路径数。

第四个点跑出来了，第五个点接着跑也跑出来了。当然我做了一件作死的事情把第五个点输出到了第四个点导致第四个点要重新跑一遍

写了个矩阵快速幂验证一下，果然是对的。可惜$O(n^3\log w)$复杂度过高跑太慢。

然后接到通知第2题的样例2是错误的。看来我的暴力程序没问题。

第七个点，点数100，多数边权是1，少数边权是2。既然之前做的第五个点是合并边，这个点就是拆边咯，拆完正好200个点。套上一个程序，当然依然很慢。

后面的点规模更大，而且似乎没太大的性质【我傻逼到看不出第九个点怎么做

然后一边跑一边去研究第1题的部分分了。

发现一个挺水的部分分是$x$都相同，这相当于集合插入一个数，删除一个数，询问最小值，线段树维护。【由于我数据结构学傻了写了可持久化线段树

并不是特别好写（其实是我代码能力太弱了），写的时间起码是写暴力的2~4倍。

拓展了一下，由于求最小的$(x-x_0)^2+c$其实就是$x^2-2x_0x+x_0^2+c$，所以最小化$b=-2x_0x+x^2+c$，把所有星球看成点$(-2x,x^2+c)$，于是转化为用截距$b$最小的直线$y=x_0x+b$截这些点，维护凸包。

然而平衡树维护凸包好难写（说白了还是我代码能力太弱），直到考试结束还是没调出来。

提交答案题也没继续玩下去，就6、7两个点各跑了3分。

此时预计得分：25+5+56=86，连100都没上，感觉并不是特别好。

结束了。

出考场第一个问的就是 @immortalCO，他说第一题不知道是不是对的，第二题只会5分，第三题只会四十多。【我立刻明白了他第一题写了正解

顿时感觉被虐翻在地（要是大家都150+我就惨了）

然后开始担心暴力有没写挂，担心提交答案题有没写挂。

其实更担心的是提交答案题你看标题就知道了我这次主要靠的就是提答= =一阵紧张

14:50。

14:55。

15:00。怎么还不能看成绩？

15:10。怎么还不能看成绩？

15:30。怎么还不能看成绩？

……

终于可以看了。紧张时刻……输入密码……打开成绩单……直接翻到最底下……

依次看到：

xx xx xx 0 84

xx xx 54 0 84

25 5 54 0 84

前两题都在预期之内，第三题第1、5两个点都出了点细节问题，导致只WA了一点点……

还好出题人良心按正确比例给分不然我这两个点就爆0了【蒟蒻只能依赖出题人的良心就是这样

@immortalCO 果然A了第一题，得了153分。太强了！超过150和不到100，这就是差距。

咱们集训队大爷AKF（@kfdong）也A了第一题，分数160+（166？）

然而我第一题40都没有！只有25分！感觉要废了。

还好，我84分在学校也不是最差的（有66分、27分、25分的）虽然有点虚要是分数线高就呵呵了

——————————

Day 1.5。

论文答辩。

AKF第一个出场。PPT加了动画效果以后立马变得高大上了。

$\mathrm{TL}=8\min$导致许多选手只抽取一部分来讲，然而论文并不好懂所以只能看热闹了- -

前半部分都是对某算法的研究，后半部分都是命题报告。

某神犇的题叫strakf。

（1）

——黑科技！自strcat，strcmp，strcpy之后，又一个处理字符串的新神器问世了——strakf！

（2）

immortalCO：那个题目叫strakf的人是你队友吗？

AKF：是。

（3）

Q：为什么题目名称叫这个？

A：str是字符串的意思，akf是一个人名。

总之上午的论文答辩愉快地过去了。下午的报告会没那么有趣，不过仍然比较可看。看完就回去了。

回宾馆时发现第3题6、7、8三个点都可以预处理出邻接矩阵$A$的$A,A^2,A^4,A^8...$就可以$O(n^2\log n)$单次处理了。于是把这三个点都跑出来了。

我的24分！靠！

然后第1题平衡树维护凸包有15分，再加点代码量离线处理一下树的情况又有15分了。

我真是一到考场就SB啊！

好紧张。Day1没上100，要是Day2再这个成绩我就铁定挂了。

向来Day2比Day1难，于是我就有了挂Day2的传统（NOIP Day1 AK，Day2 240，省选 Day1 AK，Day2 190），说白了就是实力不足呗

——————————

Day2。

考前各种担心，要是题目巨丧就没分数拿了，要是没有提交答案题就又只剩几十分了，然后紧张得整个人都不好了。

开考赶紧看题。噫……还好有提交答案题expedition可以玩。

不过不是特别好搞？

先理解题意，就是个带限制的路径覆盖问题，然而并没有想到特别好的思路（DP？网络流？）

想了一会儿发现只会暴力，就写了个随机化搜索。

第一个点规模很小，没什么性质。

搜第一个点，过checker了，分数很低。

再搜，还是很低。

再搜，还是很低。

……

A了！

就这么开心地拿到了第一个点。（正如zgg所说，数据规模很小随便怎么搜都可以）

用这个程序去跑其它点，结果都只有两三分，有的还没分。

于是打开了第二个点。$p=1$，所有路径都可以走。那不只要所有边都走过就行了？

跑了个BFS发现是强连通的，这就好，于是改进了个“启发式随机化贪心搜索”【这- -

（说白了就是每次随机选一条没走过的边跑过去）

开始跑，结果等了好久都没跑出来。乘机去做其它题。

第一题daydayup是个神构造题，给一个偶数$N$，要求构造一个点数为$N$的最长上升路径（路径上的边权构成递增序列）最短且边权互不相同的完全图。题目非常良心，给了一个引理和一个证明，构造较优解也有3分，还附了一个tab文件。

构造渣表示完全不会……弃疗……

第二题treelabel是个和字符串字典序有关的题，有种Day1T2 suffix的既视感【后缀数组不就是后缀按字典序排序的结果吗】，字典序这个东西巨难处理，反正我只会暴力，先敲个10分暴力吧。

第三题第2个点跑出来了，结果用checker检查：Outputs too long。

靠这是什么鬼？难道路径太长了？把寻找路径改成BFS求最短路再跑，跑的时候去写第二题暴力，结果跑出来checker还是显示too long。

考试已经两个半小时了，然而此时分数只有0+0+20~30。要挂了好方啊。

各种纠结，到底要去搞哪一题？似乎都不可搞……越来越紧张……

纠结了半天决定继续提答。开始查程序有什么问题。

折腾来折腾去，折腾了三四次才发现我是多么SB啊：

调试语句没删！！

删了调试语句就过了。

后面的题，有树、DAG等特殊图，感觉搞个DAG的比较划算。

于是敲了个只对$p=1$正确的DAG上记忆化dfs的程序（$p>1$怎么办？拿部分分呗！每次贪心取一条最长路；不是DAG怎么办？拿部分分呗！DFS的时候去掉会形成环的一些边强行变成DAG）过了5、6两个点，其它点分数都只有不到6分。

再加点随机化，某些点的分数有少量变化，就这么把3、4、7、8都搞到了6分。

9和10分别只得到了3分和4分。而且调随机化参数也没用。【一定是姿势不对- -然而我并不知道哪里姿势不对- -

第二题暴力写完以后样例3输出adv而不是-1，我坚信是样例文件错了。

事实证明我是对的。

快4个小时了，此时预计得分：0+10+71=81。完蛋了连Day1的分数都不到要狗带了= =

（第一题怎么能0分？出题人那么良心给了那么多东西让你多得分，总要拿一些分啊！）

（于是硬着头皮搞第一题去了）

出题人的福利要全部用上啊……【像我这种蒟蒻只能依赖出题人的福利

【1】

首先看引理和证明，然后猜想答案是$\frac{2m}{n}=n-1$。

根据证明过程的思想，从小到大考虑每条边，看样子构造也是从小到大在空图中加边。

然后脑补怎么加边中……如果按$(1,2)$，$(2,3)$，$(3,4)$这样顺序加边容易挂，因为加着加着就一条很长的递增序列出来了，好像要优先往度数小的点加？

【2】

良心福利：答案为最优解的$2$倍以内时，有3分。

于是贪心乱搞一发：设$G$一开始为空图，第$i$次操作时在$G$中取$\deg(u)$最小的点$u$，再取与$u$不相邻的$\deg(v)$最小的$v$，连边$(u,v)$，边权为$w(u,v)=i$，重复$\frac{n(n-1)}{2}$次。

怎么检查是不是最优解？DP，记$f(i,j)$为从$i$出发只经过边权大于等于$j$的边可以走出的最长上升路径，于是$f(i,j)=\max\{1+f(k,w(i,k)+1)|w(i,k)\ge j\}$。记忆化搜索可以做到$O(n^3)$【当然有更好的状态定义方式可以使空间复杂度降到$O(n^2)$但是我懒得写了

测了下我的贪心乱搞，仅当$n$是2的正整数次幂时才能使答案为$n-1$，否则都在$[n,2n-2]$内。

30分get！

此时预计得分：30+10+71=111，加上Day1就195了看起来还行。

【3】

那么给个tab文件有什么用？

tab文件里有50个矩阵，第$i$个大小为$2i\times 2i$，并且上面的数都是$[0,2i-1]$之间的正整数。矩阵满足斜对称性，联想到邻接矩阵。每行每列都是$0$到$2i-1$的排列，猜想是加边顺序。

于是按照tab文件的顺序加边，先加矩阵中0对应的边，然后加1的边，再加2的边……写完测了一发，过了！答案都是$n-1$。

不过由于tab文件只到$n=100$，所以这个方法只能50分，剩下的用贪心乱搞可以65分。

此时预计得分：65+10+71=146，这样就能上230了。

不过感觉今天大家分数都会很高啊！然而我分数还没有 @immortalCO Day1分数高，似乎要完了？想再拿点分。

可惜离考试结束不到半小时了。

第二题显然想不出来，第三题没想到什么更好的近似算法（我为什么就没想到SPFA？），第一题盯着tab文件看了好久就是没想到构造这个矩阵的方法。

快结束了。各种担心，各种虚，各种测样例，测数据，调checker……

结束。

出考场时心想好多人都上200了。似乎又挂了。

问了下几个同学，第一题 @lightning 和我一样拿了65，第二题大家都写暴力，第三题 @immortalCO 拿了66分。第三题出题人zgg（@ufo，咱们学校的往届神犇）问了下咱们情况，我说71，zgg：强。【其实我根本不强这题有人80分

看来今天这个分数算挺正常了- -（但愿不写挂……不要写挂……

等成绩。

今天出成绩挺快的，15:00左右就可以看了。

输入密码，打开成绩单……依次看到：

xx xx xx 0 146

65 xx xx 0 146

65 10 71 0 146

和预期完全一样，就放心了。

总分：84+146=230。学校除了集训队大爷AKF以外我是rank2，rank1当然非 @immortalCO 大神莫属（D1T1比我高75分，高到不知道哪里去了）

然后和 @immortalCO 一起拿了Au

——————————

两天CTSC，我得分最高的题都是提交答案题。要是没有提交答案题我就滚粗了

写不出数据结构题，想不出DP和字符串题。在WC前觉得WC会考提交答案题就刷了好几道提交答案题练手结果变交互题了（交互题10分狗带）最后只有80分这次CTSC担心会不会没有提答了还好提答还在于是勉强混了个Au

幸好这次没写挂（虽然有的题没拿满）于是从WAer暂时变成了Auer

接着还有APIO所以依旧紧张中……