海亮 2024 2 月集训 做题记录

发表于 分类于

Round 1

Day 1

没打．

! A. 染色数组

! B. 博弈

! C. 消消乐

Day 2

40 + 0 + 0．

* A. 土豆田

直接算不好算，考虑计算反面，即包含 00 个或 11 个 11 的子矩形个数．

考虑枚举上下边，维护有多少个列区间能够当前上下边围成合法的子矩形．我们将所有列分成三类：没有 11 的，有 11 个 11 的，有 ≥2\ge 2 个 11 的．连续 11 类列可以随便选，最多选一个 22 类列，33 类列不能选．

发现每次插入的贡献只和左右两边第一个非 11 类列有关，故使用 set 维护．然而这样显然跑不过去，又发现这玩意好删不好插，故将 set 换成链表．

! B. 像素原神

! C. 区间操作

只补了 50 分．50 分是 典．

Round 2

Day 1

70 + 0 + 10．挂完了．

A. 房间

考虑图建模．将房间看作点，门看作边，特别的，将两端的门看作 11 和 nn 连向 n+1n + 1 的边．直接建 Kruskal 重构树，若一个点满足他子树中的点权和大于其父亲的限制，那么可以跳到父亲，求能否跳到 n+1n + 1 的祖先链上．一遍 dfs 即可求出．

* B. 序列

若最终序列中有 kk 个上升，那么一定有 n−k−1n - k - 1 个不升．我们难以直接计算恰好 ii 个不升的方案数 fif_i，故考虑容斥，设钦定 ii 个不升的方案数为 gig_i，二项式反演可得

gi=∑i≤j(ji)fj  ⟺  fi=∑i≤j(ji)(−1)j−igjg_i = \sum_{i \le j} \binom{j}{i} f_j \iff f_i = \sum_{i \le j} \binom{j}{i} (-1)^{j - i} g_j

又注意到 ii 个不升构成了 n−in - i 个不升段，设钦定 ii 个不升段的方案数为 hih_i，有 gi=hn−ig_i = h_{n - i}．

考虑如何计算 hih_i，若一个不升段中填写的数确定，那么排列方式也确定，我们实际上要计算的是将所有数划分成 ii 个互相区分的集合的方案数，注意到我们需要计算本质不同的划分方式，即每种数内部互不区分，只能使用插板法，而这会导致空段的出现，故再容斥一次．设 ζi\zeta_i 为将所有数划分成 ii 个可空的互相区分的方案数．二项式反演可得

ζi=∑j≤i(ij)hj  ⟺  hi=∑j≤i(ij)(−1)i−jζj\zeta_i = \sum_{j \le i } \binom{i}{j} h_j \iff h_i = \sum_{j \le i} \binom{i}{j} (-1)^{i - j} \zeta_{j}

考虑计算 ζi\zeta_i，对每种数插板即可，记数 cc 出现的次数为 ctc\mathrm{ct}_c，有

ζi=∏c(ctc+ii−1)\zeta_i = \prod_c \binom{\mathrm{ct}_c + i}{i - 1}

将 ct\mathrm{ct} 相同的贡献放到一起乘，复杂度 O(nnlog⁡n)O(n \sqrt{n} \log n)．貌似可以通过分析把 log⁡\log 去掉，但是我不会．

前面的就是两次卷积，NTT 直接做即可．

* C. 图图

先考虑怎么在可接受的边数和点数内将这个图建出来．考虑对 [1,n][1, n] 扫描线，我们需要支持：区间反转，点向区间内的 11 连边，区间内为 00 的位置向点连边．直接线段树优化建图，维护区间内 00 / 11，连入 / 连出的边，pushup 的时候新建节点，直接做就行．

现在来考虑如何计算答案．显然先 SCC 缩点，强联通分量内的点互相可达，然后在缩点后的 DAG 上考虑计数．显然我们的 SCC 只有两种类型：只包含一部点的和两部点都包含的．按照拓扑序考虑，每处理完一部分后将其删去．若当前 SCC 内包含两部点，那么显然其中的点能到达当前图中的所有点；若只包含一部点，拓扑序紧接其后，只包含一部点且所在部和当前相同的 SCC 都不能到，但是能到剩下的部分．

Day 2

40 + 13 + 0．唐完了．

* A. 决斗

发现一个人若能赢，那么他需要打赢序列中的最大值，故将序列按最大值划分成两部分，两部分内部的判定独立．利用笛卡尔树即可 O(n)O(n) 计算某个序列的 f(a)f(a)．

现在考虑计数．设 fl,r,x,yf_{l, r, x, y} 表示区间 [l,r][l, r] 内填的最大值为 xx，某个数要能赢，填的值要 ≥y\ge y．枚举区间最大值的位置 ii 已经填的数 jj，有转移

fl,r,x,y←+fl,i−1,j−1,max⁡{y,j−(i−l)+1}×fi+1,l,j,max⁡{y,j−(r−i)+1}f_{l, r, x, y} \xleftarrow{+} f_{l, i - 1, j - 1, \max\{y, j - (i - l) + 1\}} \times f_{i + 1, l, j, \max\{y, j - (r - i) + 1\}}