NOIP 2023题解

· · 个人记录

\text{T1 词典 (dict)}

把所有单词的最大字典序形态和最小字典序形态放到一个新数组里排序，然后对于每个单词，如果它的最小字典序形态比其他所有单词的最大字典序形态都小，那就可行。

时间复杂度 O(n^2)。

\text{Code}

\text{T2 三值逻辑 (tribool)}

先按题意模拟，设初始变量分别为 x_1,x_2,...,x_n，最终变量为 y_1,y_2,...,y_n，则显然：

以此建立 $j \to i$ 的边权为 $1$ 或 $-1$ （表示 $y_i=x_j$ 或 $y_i=\lnot x_j$）的有向图，由于每个点的入度最大为 $1$，因此这是个基环森林，每个点最多只会在一个简单环上。 然后思考哪些点必须赋 $\text{U}$。观察样例可以很轻松地发现： - 如果 $y_i=\text{U}$，则 $x_i$ 只能赋为 $\text{U}$。 - 如果一个环上的负边条数为奇数，则该环上的所有点都只能赋为 $\text{U}$。 - 如果 $x_i=\text{U}$，则以它为起点所有可以到达的点都只能赋为 $\text{U}$。 - 不满足上述三条性质中任意一条的点，都可以不赋为 $\text{U}$。 因此先按题意模拟求出 $y_i$，然后建图 $\text{dfs}$ 即可。 时间复杂度 $O(n)$。 [$\text{Code}$](https://www.luogu.com.cn/paste/8lah2smc) ------------ ### $\text{T3 双序列拓展 (expand)}

我不会。

\text{T4 天天爱打卡 (run)}

显然是个 \text{DP}。

设每个任务 task_j=\{l_j,r_j,v_j\}。

先将所有 l_i 和 r_i 离散化，然后以离散化出来的特殊时间点为第一重循环。

设离散化数组 b_i，表示第 i 个时间点实际上是第 b_i 天，map_{b_i}=i。

假设目前是第 R 个时间点，考虑第一步把所有满足 r_j=b_R 的任务加进去。

设 f_i 表示算到第 i 个时间点的最大净收益（即答案），s_i 表示从第 i 个时间点一直跑步，跑到第 R 个时间点的吃饭收益（即不算跑步损耗）。

考虑哪些 s_i 能吃到新加任务的收益。

我们先不考虑不能连续跑超过 k 天的限制，则显然，在第 l_j 天前开始跑的都能吃到这个收益，即 s_1 \sim s_{map_{l_j}} 都要加上 v_j，所以可以用线段树维护 s 数组。

在维护好 s 数组后就可以考虑 f 数组的转移（即答案的转移）。

由于 k 天的限制，最早只能从第 b_R-k+1 天开始跑步，由于这一天并不一定是离散化中的特殊天数，所以需要二分求出最小的 L，使 b_L>=b_R-k+1，表示最早能从第 L 个时间点一直跑到第 R 个时间点。

设 i \in [L,R]，则转移方程式为：

其中第一项为 $f_{i-1}$ 还是 $f_{i-2}$ 取决于 $b_i-b_{i-1}$ 是否为 $1$（因为在第 $b_i-1$ 天不能跑步）。 注意也可以选择不跑，即 $f_R$ 初始可设为 $f_{R-1}$。 做到这里，时间复杂度还是平方级别的。但是观察方程组可以发现，$s_i$ 与 $f_{i-1}$ 或 $f_{i-2}$ 以及 $b_i$ 是绑定的，而 $b_R$ 是常数项，因此可将第一项与第三项一起放到 $s$ 中（即线段树中）维护，每次转移求出 $[L,R]$ 中的最大值即可。 时间复杂度 $O(n \log n)$。 [$\text{Code}$](https://www.luogu.com.cn/paste/xs7d8em9)