【题解】GDOI2022 PJ 不保证完全正确的题解

· · 个人记录

GDOI2022 普及组题解

\text{D1T1 zouji}

题意

群臣吏民能面刺寡人之过者，受 A 赏；上书谏寡人者，受 B 赏；能谤讥于市朝，闻寡人之耳者，受 C 赏。

给出一些朝廷备案，求哪个人拿到最多的赏，相同的算较早拿到的。

题解

依照题意模拟即可。这东西怎么还有部分分啊

\text{D1T2 sequence}

题意

给出一个序列，每次可以合并两个相邻的数 a_i,\ a_{i+1}，变成 a_i\oplus a_{i+1}（\oplus 指按位异或）。求留下来最长的序列长度，使得不存在子区间的异或和为 0。

题解

做异或前缀和，得到数组 S_0,S_1,\dots,S_n。那么一次操作相当于删除一个 S_i\ (0<i<n)，子区间异或和为 0 相当于存在 i\neq j,\ S_i=S_j。简单判断即可。

\text{D1T3 line}

题意

给定一棵树，可以花费 w_u 的代价覆盖 u 子树内的叶子节点。假设选了 m 个节点覆盖，那么花费是 \max\{w_i\}\cdot m。求覆盖所有叶子最小花费。保证 w_u\le w_{fa_u}。

题解

考虑枚举最大值，权值相同的按深度从大到小，现在只用考虑最小化选的个数。由于特殊限制，没有已选点是当前点的祖先。所以每次新加一个节点选上并丢掉它子树内已选的点肯定最优。用 set 维护选择的点以及没被覆盖的叶子，总复杂度 O(n\log n)。

\text{D1T4 counting}

题意

现在有很多个数，数字 a_i 有 c_i 个，但是每个数字都是互不相同的。称一个可重数集是合法的当且仅当：

求有多少个大小在 [L,R] 间的合法的数集。

题解

先枚举公差 D。然后把是 D 倍数的 a_i 加进来并排序。然后把形成等差数列的极长段找出来。显然合法的数集是这些段的子区间。

然后对于每一段，就是要找长度在 [L,R] 间的子区间的 c_i 乘积之和。这个可以直接枚举右端点，动态维护。最后总复杂度 O(n\ln n)。

\text{D2T1 bing}

题意

给定 n，求 \displaystyle\sum_{i=3}^n\left[n\bmod i\neq 0\land n\bmod i\neq 1\land n\bmod i\neq -1\right]。

题解

拆开取模并移项，O(\sqrt n) 暴力枚举约数即可。

\text{D2T2 webpage}

题意

有 n 个网页呈树状关系。你一次操作可以：

求浏览所有网页并关闭标签页的最小操作次数。

题解

比较有意思。

回退这个操作是没用的。因为我们可以打开新标签页，所以子节点打开新标签页后就和当前节点无关了。所以一个节点的花费是打开自己的花费+浏览子节点的花费+关闭自己的花费。

又注意到若当前节点不是叶子，我们可以选择某个子节点直接替换自己，这样就不用花费一步来关闭这个标签页了，所以只有叶子需要“真正”加上关闭的花费。

所以有，\displaystyle f_u=[\operatorname{son}(u)=\varnothing]+\sum_{v\in\operatorname{son}(u)}f_v，也就有 ans=\text{节点数}+\text{叶子数}。

\text{D2T3 clock}

题意

有一个电子钟，用八段数码管显示了年月日时分秒。一段数码管在状态改编时会消耗一单位电。求两个时间点之间电子钟共消耗多少电。

题解

先打一些简单的表，然后枚举秒，可得 70pts。考虑优化。预处理一天内时分秒的花费，然后枚举天，足以通过本题。

\text{D2T4 robot}

题意

地图上有一个机器人，还有障碍。给一个上下左右的指令序列，每个指令机器人可能会无视，如果走的方向是障碍机器人不会走。求机器人有没有可能跨出地图。

题解

因为我们要求机器人是否能跨出地图，所以我们让机器人尽可能跨出地图是一个很正确的方法。设 f_{i,j} 为从起点走到 (i,j) 的方案中，匹配指令序列的某个子序列的最后一个下标的最小值。显然结尾下标越小，机器人越有可能走出去。

然后使用类似 SPFA 的方法，用子序列自动机处理转移。注意到一个节点最多被上下左右各更新一次，所以每个点至多入队 4 次。复杂度 O(|s|+nm)。