安师大附中口胡题解-解题报告

# 3.22 ### T1 发现统计方案数需要知道与一个点相邻的比它大的点的数量。发现新的边其实就是a可以通过$<\min(a,b)$的点到达b，我们从小到大加点，线段树合并维护每个联通块的邻居数量。 ### T2 建立前缀后缀的AC自动机，同时DP。复杂度$maxlen\times \sum len$ 这道题有一个问题：如果在中间出现怎么办？发现这个串一定有回文后缀，那么，反串AC自动机的路径上就不会跳fail导致中断了。也就是说我们直接倒着跑一遍，check一下就可以了。 ### T3 建立最短路树，在树上DP。中途需要求出不走父边到T的最短路e(v)，用左偏树写。  # 3.23 ### T1 考虑生成树的结构，对于第 i 列和第 i+1 列之间，要么连了一条边，要么连了两条边。将相邻的连了两条边的列视 作连通，则对于每个列的连通块，其中都存在恰好一列，上下两行有边。 于是我们可以把题目变成，将序列分段，每段的代价可以预处理，最小化代价即可。 ### T2 讨论绝对值的式子的各种情况，发现最终答案的式子比较简单，再从另一个角度看式子，可以得到dp的思路，扫描线维护区间的贡献。线段树优化即可。  # 3.24 ### T2 根据题意得到若干四元组，按顺序枚举一维，树状数组另一维 ### T3  分治+贪心的思想，建出“笛卡尔树”之后，就可以贪心了。对于第二问，因为决策是固定的，发现在状态里多记一维即可，合并是max卷积，预处理前缀和。 # 3.25 ### T1 想到对$\sqrt{n}$分类讨论，但是不会分析复杂度...  ~~感觉很奇怪，这明明也是暴力，要遍历所有边，为啥就对咧？~~ 还有另一种解释：设这个点度数为s，枚举所有度数比它大的点，这样总度数为$s^2$级别，所以不会超过$\sqrt{m}$ 我明白了，首先，大小为k询问涉及的边数为$\min(m,k^2)$，所以如果我们只遍历有用的边，复杂度是有保证的。但是这样很难做，我们就遍历小的即可。 乱搞 -> 正解 ### T2 每个数可以表示成$2^a3^bz$的形式，不同的z互不影响，我们可以把每个数看成$(a,b)$的点，这样问题就变成了给矩形染色，三个倒L形的格子不能同色，问方案数。如果直接在轮廓线存颜色，复杂度爆炸。 **但是有限制的计数可以容斥！** 我们枚举至少多少个三元环，这样我们轮廓线维护联通性即可。 ### T3 题解的做法是离线分治差分什么的，没看懂。但是我们有在线做法！ 我们树剖，每个点维护轻儿子的贡献和，这样，重链取反打标记即可，只有走一步轻链的时候会改变父亲的值，计算一下即可。感觉和动态Dp很像。 这道题的细节真的贼多...我调了好久... 代码：https://www.luogu.org/paste/v8fpww9t 大部分是一些细节问题，比如数组没赋初值，名称打错...但是重要的一步是： 我们要先遍历取反的链，在改变值之前，先把轻儿子的贡献去除！不然就无法正确计算贡献了。 # 3.26 ~~发现可能可以不用口胡了~~ ### T1 这道题有边权，这就很麻烦了，距离就不能存在状态里了，但是我们肯定是要预处理，对询问快速回答，怎么办？考虑产生距离的是$n^2$个点对，数量不大！我们可以在状态里记最远点。 ### T2 对序列分块，建出凸包，在凸包上均摊的走。 ### T3  然后就变成序列上数颜色了，扫描线即可。 # 3.27 ### T2 把每个点拆成log个点，都插进主席树里求前k大。为了卡空间，可以分成$[2^k,2^{k+1})$一个个做 # 3.28 今天的题十分套路 ### T1 啊啊啊曾经有一瞬间想到要枚举答案的dis是多少然后瞬间又把它pass了......我们枚举dis，发现每一维是独立的，背包合并即可。 ### T2 码农题，考场上必须写对拍。在纸上画一画，发现最关键的就是修改的那条链上的边，这是一个斜率优化的式子，我们要求出链上的凸包，于是可以离线树剖/线段树维护栈序凸包2个log做了。 ### T3 min-max容斥，然后为了不枚举子集，我们可以在状态里记选的点的奇偶性，可选的路径数，然后$O(n^6)$暴力DP即可。这道题用FFT优化转移甚至更慢。 这道题为了加速，可以把不是0的状态存起来转移。容斥的-1的系数可以直接放在dp指中，不用单独记选择的个数。 # 3.29 ~~凉了，还是得口胡~~ ### T1 这道博弈论一眼看上去很神仙，各种复杂的策略...但是看完题解发现并不难。首先，我们可以通过DP确定每棵子树的状态：先手胜、红胜，蓝胜。然后可行的点的集合可以通过类似的思路转移。 # 3.30 ### T1 枚举每个因数。10^18以内的因数个数是10^5级别的。 ### T2 好吧。曾经有一瞬间想求出每循环位移1对答案产生的贡献，但是犯懒没有写，又开始了无端思考。发现把x从开头移到结尾，贡献是n-2x+1，于是求前缀和最小值即可。 ### T3 想得差不多，但是细节肯定很多。我们把相同的一段缩起来，然后逐字符的确定，我们肯定是保留最多的当前字符，如果能都保留就过。不然就保留最长的k段，这时，最后一个保留的，后面的字典序会有影响，所以再求一下SA就好了。 # 3.31 ### T1 平面图的边数比较少，然后...？ ### T2  ### T3 枚举行的集合，然后列的集合，当选择了两列之后，每一列的单调性就确定了，为了保证复杂度，可以用桶转移。 # 4.1 ### T1 奇环直接出解，偶环要么无解要么无用，最后变成一棵树，对一个位置计算一下上下界即可。 ### T2 需要k-D Tree框出一个半平面，但是这样做的复杂度好象不对... 对于动态插入的半平面交，可以——二进制分组！ ### T3 打表...?