NOIP2022 题解

Alex_Wei · 2022-11-27 23:26:05 · 个人记录

A. P8865 [NOIP2022] 种花

固定 y_0，对于 x_1，合法的 y_1 数量确定，为 r_{x_1, y_0}，其中 r_{i, j} 表示 (i, j) 右侧的连续空地数量。对于 x_2 同理。

因此，直接枚举 x_1, x_2, y_0，检查是否有 (x_1, y_0)\sim (x_2, y_0) 均为空地。若合法，则 \texttt C 的数量 r_{x_1, y_0}r_{x_2, y_0}，\texttt {F} 的数量加上 r_{x_1, y_0} r_{x_2, y_0} d_{x_2, y_0}，其中 d_{i, j} 表示 (i, j) 下方的连续空地数量。

考虑前缀和优化，对每个 (x_2, y_0)，求出其上方合法的 x_1 的 r_{x_1, y_0} 之和。时间复杂度 \mathcal{O}(n ^ 2)。

B. P8866 [NOIP2022] 喵了个喵

被构造支配了。

空栈是非常有用的，我们尽量利用这一点。

对于题目的两种操作，一种可从栈顶删去相同元素，一种借助空栈可从栈底删去相同元素。对于 k = 2n - 2，我们总可以时刻保持空栈。

问题转化为处理 k = 2n - 1，其它 n - 1 个栈都有两个元素，且当前牌堆顶的元素 x 不同于当前在栈中的所有元素的情况。

考虑牌堆顶接下来若干张牌，找到下一个 x 或栈底元素 b。

• 若找到 x，则将 x 加入空栈，到下一个 x 出现之前不会遇到栈底元素，所以过程中不需要空栈。
• 否则找到 b，设其对应栈顶元素 t。
  • 若 t 在 b 之前出现偶数次，则将 x 加入 b 所在栈，此时栈内元素分别为 b, t, x。处理到 b 时，因为 t 出现偶数次，所以栈内元素仍为 b, t, x。将 b 插入空栈即可消去 b。
  • 若 t 在 b 之前出现奇数次，则将 x 加入空栈。处理到 b 时 b 所在栈仅有 b 一个元素，所以将 b 插入即可得到新的空栈。

精细实现可做到 \mathcal{O}(n + m)。

C. P8867 [NOIP2022] 建造军营

删去一条边使得军营不连通，则删去的边一定是原图割边。

边双缩点，称 x 被点亮当且仅当 x 对应点双存在军营，方案数为 2 ^ {s_x} - 1，则答案为边双树上每个点集 S 被点亮的方案数乘以 2 ^ {m - V(S)} 之和，其中 V(S) 表示 S 的虚树大小。

考虑树形 DP，设 f_{i, 0 / 1, 0 / 1} 表示 i 子树内是否有点，i 子树外是否有点的 S 对应的点亮方案数乘以 2 ^ {-V(S)} 之和。