0824考试总结
某场考试总结
考完了一个月之后再来写总结也是没谁了。。。
T1
简单题，随手构造出来就行。
可以加强，比如弄成质数个，或者干脆 \(10^{18}\) 个。
然而有个结论，考虑往一个字符串后添加 \(k\) 个 \(0/1\)，那么本质不同子序列个数一定可以写成 \(k(x-b)+x\) 的形式，其中 \(x\) 为该字符串的本质不同子序列个数，\(b\) 为上一个 \(0/1\) 前一个位置的答案。根据这个玩意来构造，不会太好做。
T2
发现本质不同子序列个数随 \(n\) 的增长近乎呈指数增长，猜想满足条件的不会太多，所以暴力处理即可。
实际上设 \(DP\) 状态，\(dp[i]\) 表示考虑到前 \(i\) 个字符，本质不同子串个数，有转移 \(dp[i]=2\times dp[i-1]-dp[lst[i]-1]\)，\(lst\) 表示 \(i\) 处字符上一次出现的位置。
于是设 \(dp[i][j][k]\) 为考虑前 \(i\) 个字符，上一个 \(0\) 处本质不同子序列数量 \(j\)，上一个 \(1\) 处本质不同子序列数量为 \(k\)，枚举 \(0,1\)，直接转移。
T3
我想的是折半之后爆搜，然后剪一下枝，比 \(std\) 快 \(5\) 倍。
确实也是折半，但是其实可以考虑偏序关系，两个 \((x,y,z)\) 三元组合并，不妨要求 \(x_1+x_2\le y_1+y_2\le z_1+z_2\)，然后值为 \(z_1+z_2-(x_1+x_2)\)，本质上是个二维偏序。
还可以剪个枝，强制要求 \(x_1\le y_1\le z_1\)。同样能对应上去。
实际上还可以发现强制要求 \(z_2\le y_2\le x_2\) 也没有问题，证明比较繁琐，故省略。
T4
很妙的一道题，我想的是，需要将相同城市联系起来，考虑它们在虚树上的关系，每个点需要和它倾向的所有点连边，然后实际上只会连 \(O(n)\) 条边，连好之后 \(tarjan\) 求下 \(SCC\) 就行。
有一种非常神奇的做法，考虑点分治，暴力求分治中心的答案，然后考虑其它点，发现之后的所有点的答案都不会跨过分治中心，可以暴力计算。