模拟赛总结

2023-3-19

赛时

T1花了半个小时看没有推出来式子直接跳T2。

一开T2先的部分分，看到一个没有环的情况。想了一下发现直接拓扑排序每次炸相同深度的点就可以了。后来考虑又环的方法，因为之前那一道xor的题目，想到了生成树，但是发现因为是有向图，生成树没有任何意义。

要是图是一棵树该多好，于是就想到了tarjan。一个强连通分块里面的点必须要一个一个轰，强连通分块自然就会变成一个DAG，这不就变成了没有环的情况了么？记录一下大小什么的就做完了。

T3以为想到了 \(n\le 10\) 的做法，但是发现加了，于是就打个所有人的概率都一样的方法。

T4打了个 \(m=1\)

又看T1，推出来这样的式子：\(C_{m-1}^{n-1}-n\sum_{i=k+1}^{m-n+1}C_{n-i-1}^{m-2}\) 找出现了一个什么样的不合法的数。其实是假的，因为可能出现多个不合法的数。于是写了40pts暴力。

赛后

50+100+20+10 \(\to\) rk1

T1其实很简单，考虑有 \(i\) 个数不合法，我们强制挑出来 \(i\) 个 \(k+1\) ，然后其他的随便分割，把这几个 \(k+1\) 分给某些位置。之后容斥一下就可。

T3是dp，还没太看懂

T4也不难，考虑 $m\le \sqrt n $ 的情况，这样可以直接每个循环出现的样子，然后用简单的动态规划就统计完了

如果 \(m> \sqrt n\) 的情况，暴力枚举那些位置反转，然后对于每个\(\mod m=i\) 的位置，统计出现的0和1的数量，取少的那一个，相加即可。

这样的好处就是不管那种情况，复杂度都是 \(O(2^{\sqrt n} \times n)\) 相当好而且巧妙。

总结

计数非常不行，GDKOI D1T2就是例子，还需要加强。还有分块技巧不熟悉。