NOIP2022 题解

#### A. [P8865 [NOIP2022] 种花](https://www.luogu.com.cn/problem/P8865) 固定 $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] 喵了个喵](https://www.luogu.com.cn/problem/P8866) 被构造支配了。 空栈是非常有用的，我们尽量利用这一点。 对于题目的两种操作，一种可从栈顶删去相同元素，一种借助空栈可从栈底删去相同元素。对于 $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] 建造军营](https://www.luogu.com.cn/problem/P8867) 删去一条边使得军营不连通，则删去的边一定是原图割边。 边双缩点，称 $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)}$ 之和。 $f_{i, 0, 1}$ 即 $i$ 的每个儿子 $u$ 的 $f_{u, 0, 1}$ 之积，$f_{i, 1, 1}$ 即至少一个儿子的 $\frac 1 2 f_{u, 1, 1}$ 和其它儿子的 $f_{u, 1, 0}$ 之积，$f_{i, 1, 0}$ 即 $f_{u, 1, 0}$ 之和加上至少两个儿子的 $\frac 1 2 f_{u, 1, 1}$（如果只有一个儿子，$u$ 子树外无点，与定义矛盾）和其它儿子的 $f_{u, 1, 0}$ 之积。 时间复杂度 $\mathcal{O}(n + m)$。 #### D. [P8868 [NOIP2022] 比赛](https://www.luogu.com.cn/problem/P8868) 扫描线，设 $T_{i, j}$ 表示以 $i$ 为右端点时每个 $j$ 作为左端点的答案。 加入 $a_i$ 时，考虑它对 $ra_j = \max\limits_{p = j} ^ i a_p$ 的影响，用单调栈维护，相当于若干次区间加法。加入 $b_i$ 时同理。因此，线段树容易维护 $T_{i - 1}\to T_i$。 而询问 $[l, r]$ 的答案相当于对所有 $T_i(l\leq i\leq r)$，查询 $T_{i, j}(l\leq j\leq i)$ 的区间和。改变求和顺序，相当于对所有 $j$，查询 $T_{i, j}(j\leq i\leq r)$ 之和。因为 $i < j$ 时 $T_{i, j} = 0$，所以又可以写成 $T_{i, j}(i\leq r)$ 之和。 维护 $T_i$ 前缀和 $U_i$，即对 $T$ 维护历史和，则询问 $[l, r]$ 相当于 $U_r$ 区间查询 $[l, r]$。 - 对于懒标记，维护 $(da, db, t, ha, hb, hab)$ 分别表示 $\Delta a$，$\Delta b$，求和轮数，每轮求和的 $da$ 之和即 $da$ 历史和，$db$ 历史和，以及 $da \cdot db$ 历史和。懒标记可合并。 - 对于信息，维护 $(num, sa, sb, sab, hab)$ 分别表示区间长度，区间 $\sum a$，区间 $\sum b$，区间 $\sum ab$ 和区间 $\sum ab$ 历史和。区间信息可合并，信息可与懒标记合并。 时间复杂度 $\mathcal{O}((n + q)\log n)$，空间复杂度线性。 代码直接在 https://codeforces.com/gym/104071/status 搜索我的 CF 号即可。