NOIP2025模拟赛9总结
liujuhan
·
·
个人记录
NOIP2025模拟赛9总结
前言
啥也不会。
T1
一眼二分图最大匹配，但是有k的限制。
猜测可以在匹配的过程中，优先匹配k位老师不上的课，贪心一下即可。
但是我只会 O(nm) 的二分图算法最大匹配，会 T 。
而且不确定正确性，先打了再说。
发现居然能过大样例，看来是对的。
好像之前看到过一种 HK 算法，可以做到 O(mn^\frac{1}{2}) ，但是还不会。
就这样吧。
T2
计数问题。
首先发现答案可以转换为 max(\lceil \frac{sum}{2}\rceil, max(t_i) ) 。
然后就想到了 O(n^4) DP ，状态是三维的，感觉没有前途。
但是又想不到其他的方法，于是就打了，然后跳过了。
T3
图论。
感觉非常高级，没有什么思路，压根不知道从哪里入手。
不会，就跳了。
T4
树上问题。
感觉也不会，还是最后一题，觉得还不如把时间留给 T2 。
于是之后都在想 T2 ，却没有什么进展。
赛后
正解就是 $HK$ ，不过也可以用 $dinic$ 。
贪心是把k位老师和他们所对应的课的连边删掉，再跑二分图最大匹配。
$HK$ 几乎没人会，于是 $T1$ 在考网络流，逆天。
$T2$ $30$分，意料之内。
答案转换对了，但是不用 $DP$ ，直接组合数就好了。
另外我复杂度分析假了，实际上是 $O(n^3)$ 的，虽然也不能多过点。
列出组合数后，老师讲的是用组合意义，感觉非常困难。
不过我觉得可以直接化简，比较直接。
$T3
正解是图上 DP ，由于不会超过 30 轮，所以可以 DP 。
感觉自己做图论题还是少啊，没怎么见过图上 DP ，压根没往那上面去想。
T4
正解是神奇转换和树分治和树状数组。
其中转换极其高级。
题还没订，改天吧。