20231027

23/10/27 NOIP模拟赛总结

时间安排：

7:40-8:30

看T1，没啥思路，一开始以为是组合数，写了个递推求组合数发现是最简单的DP，测样例，手搓了几组小样例都过了。

8:30-8:50

T2只会模拟，写的get函数有点麻烦，耽误了一些时间。

9:00-9:30

看T3 T4都没想到，去写T5暴力。

9:30-10:20

T5暴力取模的地方调了半天，最后测样例没看仔细，把小于等于改成小于就过了，\(m=10^{18}\) 的情况写了个并查集，赛后发现假了。

10:20-11:00

想T4，连暴力也不会，但是思考树的情况时想到了正解，开写。

11:00-11:20

想了想T2和T3，决定去思考T2更高档暴力。

11:20-11:40

试着写了写T3，但是没时间了，最后输出 \(S\) 串，拿了5分。

11:40-11:50

写freopen，编译了一下，准备交题。

反思总结：

1.对题目的取舍不合适：在T2和T3当中选择T2，放弃了更好写的T3暴力。

2.T1花费时间过长，但多写代码还是对思考题目有帮助的。

简要题解：

T1:

设 \(f_{i,j}\) 表示从 \((1,1)\) 走到 \((i,j)\) 的方案数，考虑刷表，开一个数组记录 \((i,j)\) 能否转移到 \((i+1,j)\) 和 \((i,j+1)\) ，转移不再多说。

T2:

将答案分成两部分统计，能填满的和无法填满的。

无法填满的部分直接暴力统计，复杂度：\(O(n)\)。

能填满的部分分成竖列和横行，竖列直接等差数列求，两个横行之和是定值，也可以直接算，该过程用差分维护，复杂度：\(O(n)\)。

T3:

设 \(match_i\) 表示以 \(i\) 结尾的 \(S\) 的子串，和 \(T\) 最多能匹配到哪里。

因此，我们在删除一个 \(T\) 后，可以从 \(match_i\) 继续遍历，该过程可用栈实现。

T4:

当 \(m\%2==0\) 时，\(ans=0\) 。

当 \(m\%2!=0\) 时，我们考虑删除度为奇数的点或两个连在一起且度都为偶数的点，答案取最小值。

T5:

求出 \(nxt_i\) 表示 \(i\) 经过 \(k\) 次交换到达的点，发现 \(i\) 和 \(nxt_i\) 连边形成了多个环。

对于每个点，我们先进行 \(\left\lfloor\frac{m}{k}\right\rfloor\) 个轮次，然后再进行 \(m\%k\) 次交换求出答案。