NOI2022 模拟赛合集【kel.ac.cn】

Round XLIX

开场看B想了3h假回去想A1h切。

A. 守序划分问题

容易想到一个必要条件，对于任意集合 \(S\)，需要满足 \(\max_{i\in S}A_i>\min_{i\notin S}A_i\)。然后用你的大脑构造一下发现这东西也充分。

于是思考如何计数，即不能将数列割裂成两个部分。于是考虑动态规划。设 \(f[i,j]\) 代表将 i 个数划分成 j 段的方案数。考虑容斥，有 \(f[i,j]=s[i,j]-\sum_{k=1}^{i-1}\sum_{l=1}^{j-1}f[k,l]s[i-k][j-l]\)。其中 \(s\) 是第二类斯特林数。这玩意像个卷积但是是二维的所以我们不妨固定一维，然后另一维ntt。可这样复杂度是 \(O(n^3\log n)\) 的，过不去。我们发现直接按找点值做最后再插值回去也可以，所以复杂度优化到了 \(O(n^3)\)。

B. 心理阴影

考虑如何合并两个子树的拓扑序的期望。如果记为 \(f[u,v]\)，那么答案即为 \(\sum_{u,v are bro}f[u,v]\) 加上祖先之间的贡献。如何对这个dp？考虑有 \(\frac{sz_u}{sz_u+sz_v}\) 的概率走到 \(u\)，于是直接从子树转移即可。

C. 点整的上圆

神秘题，记一个原题的结论：

所有模 4 余 1 的质因子的指数乘2加1的积。

Round L

B看错题瞎想了1h。最后暴力也没打完。

实际得分 100+0+20 期望得分 100+100+40 预估考场得分 100+25+40

A. 哈希计数

这题的数据范围很吓人。仔细想一想发现要求的那个值是 \(O(n^3)\) 的，所以看起来很可以多项式复杂度解决问题。于是考虑dp，记 \(f[i,j]\) 代表 \(i\) 个点的树和能否是 \(j\)。可是这样设的话不太好转移，需要记录每个点的根的距离和。我们换一种角度思考，对于每条边，他的贡献是 \(sz[x]*(n-sz[x])\)。于是考虑加入每条边的时候把贡献提前计算。于是就可以转移了。直接做的复杂度是 \(O(n^8)\)，可以bitset优化，36的数据只用跑 0.2s。

B. 运输计划

大分类讨论题，考虑枚举建在哪里，然后分类讨论。

C. 时代的眼泪

很套路的分块题（考场上自动认为这题不可做就每仔细想，其实想一想说不定可以想出来）。