CSP NOIP 模拟赛记录

9.18（lanos212）

T1 签到，10 mins 内过了。

T2 乍一看有点困难，题目太形式化，不太直观，先跳过去思考 T3 了，T3 没有什么 DP 的思路，但是这种题显然需要 DP。

看了一眼 T4，被一堆式子糊脸恶心了，没有怎么思考。

接下来一个小时在思考 T2 和 T3，突然发现 T2 只需要每次求最短路就可以了，那么就是简单的，但是乍一看自己写的好像是 \(O(n^4)\) 的，但是每个点只会被更新 \(O(n)\) 次，那么均摊就是 \(O(n^3)\) 的了，感觉这个题浪费这么多时间真的不太应该。

然后冷静下来看 T4，发现需要 DP，看到区间最小值考虑按照笛卡尔树来 DP，想了一下会了 \(O(n^2)\) ，直接写就过了，最后还剩下一个小时左右去攻克 T3。

但是自己根本没有往组合意义那方面想，也就是把所有方案的权值和双射到计算另一种方案上。

题目中的 \(\prod c_i\) 可以看作每个小狗选一个最喜欢的，那么就可以设出一个 DP，\(f_{i,j}\) 表示前 \(i\) 天，已经有 \(j\) 只狗得到了喜欢的香肠的方案。

\[f_{i,j} \to f_{i+1,j+k}\binom{n - j}{k}\binom{n - j - k}{a_{i+1} - k} \]

最终得分：\(100+100+44+100=344\)，rank 8。

9.25（by Mine_King）

T1 签到，但是磨蹭了一下，到 20 分钟才确定过了。

T2 读题花了很久，先会了一个暴力 DP，发现在根大于儿子的时候下面都是确定的，于是可以建立重构树，据 @喵仔牛奶 说这种东西叫“树上笛卡尔树”，反正改完之后直接 DP 就可以了，这个题做了 2h，问题可能在于没有快速发现上面那个加粗的性质吧。

T3 没有任何的观察，不会任何多项式做法，实际上后两题都是我薄弱的字符串 Border 理论相关。

T3 给出的这个每个字符出现至多 \(2\) 次，可以得到这个串只有一个长度小于等于一半的 Border，证明直接反证。

对于 Border 相同的字符串 \(P = ABA\)，计算 \(f(S,P)\) 的时候只考虑 \(S\) 中若干个 \(ABABA...ABA\) 的极长子串，设有 \(x\) 个 \(A\)，那么答案是 \(\left \lfloor \dfrac{x}{2} \right \rfloor\)，感受到计算这个只和 border 长度有关，不关心填了什么，那么直接枚举这个长度，然后问题变成计算 \(f(S,P)\) 和计算 border 为 \(len\) 的 \(P\) 的个数。

计算 \(f(S,P)\)

在 \(len = 0\) 的时候答案就是 \((n-m+1)V^{n-m}\)。

那么直接容斥，计算 \(\sum \limits_{i=1} (-1)^{i-1} S(A(BA)^i)\)，\(S()\) 表示直接计算的答案。

计算 border 为 \(len\) 的 \(P\)

直接枚举中间部分出现两次的字符个数。

因为 \(V \le 10^9\)，所以需要化一下式子，变成只和 \(V\) 的不超过 \(m\) 次下降幂有关。

T4 其实关键在于 Significant Suffixs 只有 \(\mathcal{O}(\log n)\) 个，然后是好做的，只需要一个 \(\mathcal{O}(\sqrt n) - \mathcal{O}(1)\) 的分块即可。

最终得分：\(100+100+5+10=215\)，rank 9。

9.28（by cyfff）

T1 直接过了。

T3 想了一下发现可以区间 DP，那么也过了，这个时候 9：00，还有两个多小时。

T2 先做了一些错误的尝试，然后发现只能记录留下来的两张牌，写了一个暴力 DP，发现只转移存在值的点似乎很快？但是实际上复杂度是错误的，在这里花费了一点时间做无意义的尝试。

冷静下来发现 DP 的转移量远小于状态量，想到之前做过的类似题，那么直接转移可能的转移就是对的？

写了一下发现过了大样例，但是已经快 11 点了，T4 看了一下发现是个容斥状物，但是先打算写 T2 拍子，写完发现没过拍！

冷静，发现是全局加 \(1\) 的时候标记打错了，调了 30mins。

最后 20 mins 极限冲了一下 T4 的两个暴力分。

但是，T3 fst 了！！！1

原因是常数太大，小机房机子太慢，导致的 TLE，虽然做法是常数非常小的，但是因为寻址的不连续，导致很慢。

最终得分：\(100+100+54+34=288\)，rank 9。

不 f 就是 \(334\) + rank 4 了/kk。

感觉目标是省选的话这个分和排名还是不够啊，需要加训点比赛了。