NOIP2024 记录

· · 个人记录

edit

贪心 in 1h，感觉挺对。

一个极大的连续 1 段中的所有位置可以任意交换，0 的位置只能固定。依据题面可以直接将 s_1,s_2 划分成若干段，每段内可以随意排列，记录每段的 l,r,c_0,c_1 分别表示左右端点、0/1 的数目。

直接贪，如果前面位置能够匹配就一定直接匹配完，这样不会有本能匹配的最后匹配不了。维护两个指针 i,j 代表匹配到 s_1 的第 i 段和 s_2 的第 j 段。记 x=\min(c_0(i)+c_0(j)),y=\min(c_1(i),c_1(j))，这两段之间的匹配对答案的贡献是 x+y：

时间复杂度 O(Tn)。

assign

签到题，小于 T1，1h。

特判掉 c_i=c_j,d_i\neq d_j,ans=0 和 v=1,ans=1。

乘法原理，讨论每个位置 i 的贡献系数，全部乘起来就是答案：

可以将连续的全被钦定/全未钦定的合成一段，快速幂算出整段的贡献。唯一的问题是对于 10\cdots01 的区间 [i,j]，如果 a_i=x_i 并且一路钦定下来，b_{j-1} 必须等于 x_j 而不能任选。所以这个区间的方案数是 (v^2)^{j-i}-v^{j-i}+v^{j-i-1}。O(Tm\log n)。

traverse

还不会。

query

一个扫描线 + 线段树能做的东西以为要树套树，没有冲出链的性质，遗憾离场。

无关正解的暴力：只有长度等于 k 的区间有用。一个结论是一个点集所有点的 LCA 是其中 dfn 最小的和 dfn 最大的两个点的 LCA。枚举 len-k+1 个区间和答案取 \max，可以 dfs 序/欧拉序 O(1) LCA 做到 O(n\log n+nq)。

考虑正解。上面的瓶颈在于枚举区间，没有前途。考虑一个点 u 能否作为 LCA 贡献 dep_u 到询问区间。考虑预处理出所有 LCA 为 u 的极长区间。进行一个 dsu on tree，把所有儿子的区间集合合并到 u，启发式合并 set，如果有两段区间相邻就合成一个，合成区间时顺便把这些有贡献的区间记录下来（没有和其它区间合并的区间 LCA 肯定在某个儿子的子树里，不需要重复记）。这样有贡献的区间就只有 n 个单点和 n-1 个其它的区间。这部分 O(n\log^2 n)。

接下来就是有一些贡献区间 (l,r,w) 和询问区间 (L,R,k)。(l,r,w) 对 [L,R,k] 有贡献当且仅当 |[L,R]\cap[l,r]|\ge k。分类讨论：

前两个直接二维数点，树状数组维护前/后缀 max；最后一个将贡献区间和询问区间按照 r_i-l_i+1 或 k 从大到小排序，贡献区间的 w_i 挂在 l_i，询问区间 max 容易线段树解决。这部分 O((n+m)\log n)。

总时间复杂度 O(n\log^2 n)，可以通过。其实 dsu on tree 部分合并区间还能通过并查集维护做到单 log，O(n\log n)。