[数据结构与算法]2021/10/29模拟赛

考试

看了 $5min$ 的第一题，以为是个 $Trie$ 树，正着建一棵倒着建一棵，到 $8:40$ 的时候能过样例。记录下每个节点对多少字符串有贡献。

$8:55$ 开始$T3$ 的 $30$ 分暴力，枚举删哪两条边，然后 $bfs$ ，看是否还联通，一直到 $9:20$ 结束。

$T4$ 的第一组样例错了，我还以为是我没看懂题或者忽略了什么附加条件啥的，找是不是有啥特殊任务会输出不一样格式的输出。
到 $10$ 点才用模拟写了个最简单的一档分，设置了偏移量防止数组越界。
感觉可以暴力模拟出进行一轮的结果，然后翻转得到后边的结果，有点像分形之城

然后回过来搞 $T2$ 想用 set 搞，但是在此之前我就只用 set 写出来过一次题，还不是在考场上而是订题的时候，所以不敢写，用 $O(N^2)$ 每次sort 一边然后选择比较优秀的方案。$10:50$ 打完过不了样例，推导了几遍发现是题目理解错误了，
我以为这一段一段的是原本不必要相连的，随便挑出来几个组成一段就可以。

然后就按照题意写了个 类似区间DP的东西 ，先用 bj[i] 处理出来以 $i$ 为左端点向右的一段，最远情况下右端点的位置，然后用f[i][j] 存从 $i$ 到 $j$ 的花费。再写个g[i]表示从 $1$ 到 $i$ 点的最小花费。状态转移方程是$$g[i]=min(g[i],g[j]+f[j+1][i])$$
最后考虑下初值，判断下每次的状态转移是否合法，自以为 $40$ 分。
写到 $11:25$ 写完

然后开始写 $T1$ 的对拍，但是我跑出来的稍微大点的数据都是输出 $0$ 的，没看出来有啥问题，太自信了，没有拍小数据的。

复盘

$T1$ 太盲目自信，最后的成绩还不如直接模拟的分好看，对拍没拍出来错误，不光得看大数据还得看小数据的正确性。没有想到题解中说的 矩阵求和

$T2$ 不认真审题，但凡看完题就推下样例看看也不至于读错题浪费时间。而且对 STL 的熟练度还是不够。这个数据好构，但是没写对拍，爆 $0$。按照上面的状态转移方程的话，看是否合法时应该判断的是if(bj[j + 1] >= i) ，考试时候写成了if(bj[j] >= i) 。痛失 $40$ 分

$T3$ 一开始把删边后的验证当成在树上做了，后来检查的时候才注意到删完边还是个图。算阶原题没做出来，也没想到树上差分。

$T4$ 连用 map 维护都没想到。