专栏文章

NOIP2025模拟赛9总结

lliujuhan
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miopn7d9
此快照首次捕获于
2025/12/02 23:05
3 个月前
此快照最后确认于
2025/12/02 23:05
3 个月前
查看原文

NOIP2025NOIP2025模拟赛9总结

前言

啥也不会。

T1T1

一眼二分图最大匹配，但是有k的限制。
猜测可以在匹配的过程中，优先匹配k位老师不上的课，贪心一下即可。
但是我只会 O(nm)O(nm) 的二分图算法最大匹配，会 T 。
而且不确定正确性，先打了再说。
发现居然能过大样例，看来是对的。
好像之前看到过一种 HKHK 算法，可以做到 O(mn12)O(mn^\frac{1}{2}) ，但是还不会。
就这样吧。

T2T2

计数问题。
首先发现答案可以转换为 max(⌈sum2⌉,max(ti))max(\lceil \frac{sum}{2}\rceil, max(t_i) ) 。
然后就想到了 O(n4)O(n^4) DPDP ，状态是三维的，感觉没有前途。
但是又想不到其他的方法，于是就打了，然后跳过了。

T3T3

图论。
感觉非常高级，没有什么思路，压根不知道从哪里入手。
不会，就跳了。

T4T4

树上问题。
感觉也不会，还是最后一题，觉得还不如把时间留给 T2T2 。
于是之后都在想 T2T2 ，却没有什么进展。

赛后

T1T1 11分，贪心假了，至于为啥能过大样例，因为大样例 k=nk=n ……。
正解就是 HKHK ，不过也可以用 dinicdinic 。
贪心是把k位老师和他们所对应的课的连边删掉，再跑二分图最大匹配。
HKHK 几乎没人会，于是 T1T1 在考网络流，逆天。
T2T2 3030分，意料之内。
答案转换对了，但是不用 DPDP ，直接组合数就好了。
另外我复杂度分析假了，实际上是 O(n3)O(n^3) 的，虽然也不能多过点。
列出组合数后，老师讲的是用组合意义，感觉非常困难。
不过我觉得可以直接化简，比较直接。
T3T3
正解是图上 DPDP ，由于不会超过 3030 轮，所以可以 DPDP 。
感觉自己做图论题还是少啊，没怎么见过图上 DPDP ，压根没往那上面去想。
T4T4
正解是神奇转换和树分治和树状数组。
其中转换极其高级。
题还没订，改天吧。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...