考试总结 2024Oct-Nov

前言：太懒了，不想每次都单独写。

\(\def\EZ{\textcolor{#51af44}{\text{EZ}}}\EZ\) 表示简单，10分钟内就能想到。
\(\def\HD{\textcolor{#3173b3}{\text{HD}}}\HD\) 表示中等，能独立想出
\(\def\IN{\textcolor{#be2d23}{\text{IN}}}\IN\) 表示困难，独立思考能想到 \(50\%\) 以上
\(\def\AT{\textcolor{#383838}{\text{AT}}}\AT\) 表示非常困难，独立思考只能想出 \(50\%\) 以下

题目按作者的主观难度排名。

20241024

• T1 \(\EZ\) 小清新hash题

• T3 \(\EZ^{+}\) 直接折半搜索就好了，考场想到折半，但是没有细想，因为 T1 耗时过久，如果是正式赛加 30min 肯定能出来

• T2 \(\HD\) 已经转化为背包，一个十分重要的提示，如果某一个问题已经转化为背包，那么就不可能有多项式的优化，只可能是减小值域，因为这是一个 NP-Hard 问题 。本题就是需要注意一个答案的范围。

• T4 \(\HD^{+}\) 一个巧妙的答案转化，得到结论。但是我打表打出了错误结论，这是为什么呢，因为我没有把所有方案都输出，只输出了其中一个最优的结果就是最后一个，结果以为是逆序，如果都输出就会发现其实基本上全是一样的，而只有一种特殊情况会出错。

总结：还是比较成功，但是 T1 做太久而且缺 30min 导致每一题都很有思路（基本只差最后一步那种）结果每一题都没 A 出来。

20241105

• T1 \(\EZ^{+}\) 整除分块+卡常。值得注意的是猜了很长时间的整除分块公式（T=1h，猜出来了），对状态影响非常大，下次不应该再犯，应该推导，其实十分简单，被之前讲师讲的什么基本和组给蒙了

  \[\begin{aligned} &\left\lceil \frac{n}i\right\rceil=m\\ \iff& i(m-1)< n \le im\\ \iff& \left\lceil \frac{n}m\right\rceil\le i\le \left\lceil \frac{n}{m-1} \right\rceil-1 \end{aligned} \]

  注意右界本身就是取不到的

• T2 \(\HD\) 计数dp+卡常。写出正确的方程，但是卡常没完全卡完，还有一个可行性剪枝没有加，加完之后总和计算量正确。

  正解是倍增

• T3 \(\HD\) 如果会李超线段树，比 T2 还简单

• T4 没看

20241107

• T1 \(\HD^{-}\) 哪个 duliu 第一题放这个，性质注意到了，后面的贪心错了。

• 【MARK】T2 \(\IN\) 非常巧妙的概率 DP，不知道这种转换怎么做出的

• T3 \(\HD\) 大模拟，难写

• T4 -26min 的时候改题，根本没看。

20241108

• T1 \(\EZ\) 可给每一行打一个标记，维护这是原来的第几行/列

• T2 \(\HD^{-}\)

  请出我们今天的降秩时刻（play了2h被制裁了）：

  完全是错误的，注意到链长至多 3，但是误以为算出范围之后直接枚举就不会互相影响了，实际上是错误的，例如

显然 \(1\) 的可选集合是 \(\{2,3\}\) 而 \(3\) 的可选集合是 \(\{1,2\}\)

但是，\(3\) 的 \(2\) 只能在 \(1\) 取 \(3\) 的时候取到。

所以直接枚举值是错的。应该确定 \(a,b,c,d\) 的取值之后再检验。

那么检验就是给每一个点分配一个权值。这个图很简单，链长最长为 3，所以链头填 3，链尾填 1 肯定可以，\(O(n)\) 对 \(a,b,c,d\) 检验一下即可。

爆搜剪枝跑 \(80\%\)，难泵。

就这也能过大样例？？？

• T3

20241112

• T1 \(\HD\) 贪心

• T2 \(\IN\) std 用了广义串并联图，考虑 Grimgod 的一种新想法：

  注意树的情况是非常好做的，考虑点双缩点，这个时候：

  钦定一个点作为根，在缩点后的树上 DFS，对于每一个点双，暴力枚举其中度大于等于 \(3\) 的点的颜色并判定，其余度小于等于 \(2\) 的点显然有解。

  对于与这个点双儿子连接的内部点，如果它选了颜色 \(c\)，那么就禁止儿子与当前点双连接的内部点使用颜色 \(c\)。

  可以说明，如果只禁止一个点使用一种颜色 \(c\) ，那么不会对答案产生影响，因为如果存在一种方案使得这个点使用了颜色 \(c\)，那么只需要把颜色依次轮换一位 \(1\to2,2\to3,3\to1\) 就能够获得合法的方案。

  考虑一个点双内度大于 \(3\) 的点的个数，满的构造一定是在满二叉树上进行的，可转化为覆盖问题，如果一个中间的点要贡献，则它两个儿子里面都有一个被连接的点，考虑叶子最少也有 \(\mathcal O(n)\) 个两两连一个则需要 \(\frac{n}2=k\) 条边，即 \(\mathcal O(3^{2n})\)

  ---

  UPD 考场上被否决的想法差不多是正解，现在考虑差在哪里：

  因为主要是枚举之后怎么确定其他的点，这一点感觉还是不好做，因为题解是广义串并联图。

  还有本题搜索剪枝可过，其他乱搞也有较高正确性（就我的似了是吧）

• T3 \(\HD^{++}\) 差一点点，注意到树高和树的个数是不超过 \(\log\) 的，但是没有予以重视，在考虑更新 DP 值的时候以为只能 DDP，没有考虑暴力跳父亲，也考虑到了扫描线，但是没有考虑到删除左端点就是删除根，最后一步优化还是容易做出的。

• T4 \(\AT\) 由于笛卡尔树随机时高度期望 \(\log n\) ，证明考虑 Treap 的复杂度正确性。倒着做相当于每次删除根，可以用 FHQ-Treap 的方式合并，随机情况下复杂度是正确的。

  正解很麻烦。