QBXT 2023 7 月集训 做题记录

Day 5

0 + 80 + 60 + 0．

A. 网格行走

为啥值域只开 $128$，std 不会写的 $O(nmV)$ 吧．/qd

拆位 DP，计算每一位上异或和为 $1$ 的方案数即可．时间复杂度 $O(nm \log V)$．

B. 树

枚举根做 DP，$O(n^3)$ 是容易的．

考虑如何优化．对于一条路径，考虑将其贡献在端点的 LCA 处计算，类似树形背包合并即可．

C. 序列

设 $f_{i, j}$ 表示考虑了低 $i$ 位，需要进 $j$ 位，且序列中元素低 $i$ 位的和等于 $m$ 的低 $i$ 位的方案数，$g_{i, j}$ 表示考虑了低 $i$ 位，需要进 $j$ 位的方案数．转移枚举 $x$ 个元素第 $i + 1$ 位上是 $1$，且 $(j + x) \bmod 2$ 和 $m$ 的第 $i$ 位相同．$g_{i, j}$ 的转移有两种贡献，将低 $i$ 位和第 $i + 1$ 位对异或和的贡献分开考虑．那么我们有如下转移：

$$\begin{aligned} f_{i + 1, (j + x) / 2} &\leftarrow \binom{n}{x} f_{i, j} \\ g_{i + 1, (j + x) / 2} &\leftarrow \binom{n}{x} g_{i, j} + [j \bmod 2 = 1] \binom{n}{x} 2^i f_{i, j} \end{aligned}$$

D. 酒馆

E5-2682 v4．/qd

首先观察到，在最优的方案中存在一个酒馆，使得能到这个酒馆的所有人都到了这个酒馆．

那么我们可以设 $f_{l, r}$ 表示只考虑只能到达 $[l, r]$ 内的人，最大的收益是多少．设 $w_{k, t}$ 表示有 $t$ 个人到了第 $k$ 家店的最大收益．枚举最大值取到的位置 $k$，我们有转移

$$f_{l, r} \leftarrow f_{l, k - 1} + f_{k + 1, r} + w_{k, t}$$

其中 $t$ 可以通过一个类似二维前缀和的东西计算．

考虑如何求出 $w_{k, i}$，有转移 $w_{k, i} \leftarrow j \times i - c_{k, j}$，这是标准的斜率优化，直接做就行了．

感谢 QBXT 的 shaber 评测机，带 $\log$ 过不了．

Day 6

100 + 100 + 70 + 85．

A. 危机

暴力．

B. 质树

暴力．

C. 整除

A069930．

然后筛 $\sigma(n)$ 即可．

为啥开个 long long 都能被卡的？

D. 序列计数

考虑如何对每个 $n$ 快速计算答案．

考虑 $n$ 的唯一分解：$n = \prod_i {p_i}^{a_i}$．为了让我们的序列中的元素的 $\operatorname{lcm}$ 正好是 $n$，显然元素不能含除 $p_i$ 以外的质因子，且存在一些元素唯一分解中 $p_i$ 上的指数等于 $a_i$．那么逐个考虑每个数 $p_i$ 上的指数怎么填，枚举有几个填了 $a_i$，显然答案为

$$\prod_i \sum_{i = 1}^k \binom{k}{i} {a_i}^{k - i}$$

这不是我们二项式定理吗！然后就做完了．记得预处理指数，不然会超时．

Day 7

100 + 70 + 50 + 0．

A. 咒语

将询问离线之后倒序还原位置．

B. 博得

发现将字符重排和 这道题 的操作是一样的，那么考虑同样的转化，而 Broder 有一个重要结论就是对于一个串的所有前缀，其变化量总和是 $O(n)$ 的．

那么暴力就行．

C. 能量水晶

起手写了个分治，我脑子怕是有点问题．/qd

一个数能被开 $k$ 次方根的充要条件是它的唯一分解中，质数上的指数都是 $k$ 的倍数．

那么对每个数将指数序列看成向量，维护向量的前缀和 $\pmod k$，然后就是对每个位置查找在他前面有多少个向量前缀和和它的前缀和相同．这个可以通过 hash + map 解决．

D. 字符串谷

贺 ppt．/qd

考虑题目所求为两者权值之差，考虑令串 $s_i$ 的权值为 $v_i + \frac{1}{2}\sum_{j} \operatorname{LCP}(s_i, s_j)$．

那么如果两个串都被一个人选中，LCP 恰好被加了两遍．

如果分别被两个人选中，一相减恰好消除．

所以直接对这个权值排序，从大到小以此选择即可。

Day 8

100 + 95 + 30 + 80．

A. 链条

把节点权值变成 $a_u \oplus a_f$，然后就用一个 DP 弄一下权值最大和次大的链就行．

B. 奇迹之地

$n \le 5 \times 10^4$，一眼 bitset．

设 $f_{u, v}$ 表示 $u$ 到 $v$ 的路径条数 $\bmod\ 2$，容易使用 bitset 优化转移．

C. 星树

这下要 learn how to use binary search 了．/qd

考虑二分答案，转化为判定是否存在合法方案使得根节点答案 $\ge$ 一个值．

这样那个排列的限制就没用了，设当前判定的值为 $x$，我们直接将权值 $\ge x$ 的点看作 $1$，剩下的点看作 $0$．

设 $f_{u}$ 表示在 $u$ 的子树中分配至少多少个 $1$ 才能使得 $u$ 为 $1$．设 $u$ 的儿子个数为 $v$，由于题面中的策略是取中位数，转移直接枚举 $f_v$ 前 $\lceil 1 / 2 \rceil$ 大的 $v$，求和即可．

D. 千叶树．

$f_i = 1$ 的部分分是容易的，由于根节点必须单独被分到一个集合，其他的节点可以任意分，答案就是 ${n - 1 \brack m - 1}$．

$n, m \le 100$ 的部分分也是容易的，设 $f_{u, i}$ 表示将 $u$ 的子树内划分成 $i$ 个互不区分的集合的方案数，转移考虑合并一个子树，枚举两部分分别有划分出了多少个集合，然后再将多出来的集合合并．比正解难写．/qd

考虑按照 bfs 序分配集合，这样在考虑一个点时，其祖先都被考虑过了，有转移 $f_{i + 1, j} \leftarrow f_{i, j - 1} + (j - \mathrm{dep}_{i + 1}) f_{i, j}$．

Day 9

100 + 30 + 91 + 100．

A. 代数

暴力．

B. KAKURASU

小游戏网站．/qd

倒着搜索，然后剪掉全选也凑不齐和超出限制的状态．

C. 卡特兰

先讲讲赛时做法．

考虑构造一个 DAG 状的自动机，接受的字符串数就变成了 DAG 上的路径计数．然后就可以通过构造一定量的重边来减少状态数．

具体而言就是先挂一个有 $6$ 个节点的链，然后对于距 $1$ 号点距离为 $i$ 的节点，由它向终止节点连 $a_{i + 1}$ 条边．注意到字符集大小是 $20$，而 $a_5 = 42$，出边数量不够用，那么由 $4$ 往 $5$ 连 $3$ 条重边，这样 $5$ 就只用往终止节点连 $14$ 条边了．然后类似的构造把 $a_6$ 挂上就行．

最终大约最劣需要 $9$ 个状态，由于最优状态是 $4$ 个，那么可以每个测试点就能拿到 $9$ 分．

赛场大佬们的乱搞是钦定停在 $1$ 上，然后直接搜邻接矩阵．注意到我们知道所有测试点中 $a_6$ 的值，那么打个表就能过去．

题解的剪枝不知所谓．感觉不如搜邻接矩阵！

D. 完全回文数

A002779，然后 LINKS 里面有个 表．拜谢 Hans Havermann, T. D. Noe．

然后我们的 ckain 给不知所谓的题解添加了绝佳的注解！

考虑去搜索一个长度为 $\rm{len}$ 的数字．设当前前 $i$ 位形成的数字为 $S$，后 $i$ 位形成的数字为 $T$．那么当前可能被搜出来的数字形如 $S \dots T$．

从 $S$ 的方面考虑，平方出来的数字在区间 $[S^2 \times 10^{2(\rm{len} - i)}, (S + 1)^2 \times 10^{2(\rm{len} - i)})$．从 $T$ 的方面考虑，平方出来的数字后 $i$ 位一定是 $T^2$ 的后 $i$ 位．

由于这个平方串理应是回文的．我们判断从 $S$ 考虑正着看和从 $T$ 考虑反着看的两个区间是否存在交即可．

Day 10

60 + 0 + 70 + 0．

A. 最短路径

一眼分层图最短路，然后我把图建出来了．/qd

B. 跳棋盘

容易设计一个 $O(n^4)$ 的 DP，考虑如何优化．

首先只考虑决策点在自己左上方的情况，转移方程形如 $f_{i, x, y} \leftarrow f_{i - 1, x^\prime, y^\prime} + x - x^\prime + y - y^\prime$．用一个二维 BIT 维护决策点，然后分讨 $4$ 种绝对值的拆法就行．

赛时看到暴力 70 分就跑了，没想到暴力挂了．/qd

C. 树

发现这个问题好像不弱于小 Z 的袜子啊！那么直接考虑根号做法．

先考虑链怎么做．直接上序列莫队，插入的时候容斥一下贡献．维护质因子集合的出现情况可以 hash．这里我赛时以为需要开个质数个数平方的桶，于是就直接上 bitset 了．事实上本质不同的集合是序列长度级别的，直接 hash 很对！为啥想不到呢．

正解就是直接上树上莫队．嘴巴会了，没写代码．

D. 树树树

神仙题，晚些时候问过 yht 再写．

Day 11

90 + 100 + 72 + 29．

A. 子序列

拆贡献，然后做完了．

B. 排列

设 $f_{i, j}$ 表示长为 $i$，峰数为 $j$ 的排列数目．

考虑插入 $i$．插在峰两边或序列两头不会改变峰数，插在其他地方都会增加一个峰．那么有转移：

$$f_{i, j} = (2j + 2) \times f_{i - 1, j} + (i - 2j) \times f_{i - 1,j - 1}$$

C. 闪电

卡空间．/tuu

首先容易设计一个 2D / 1D 的 DP，然后利用前缀和优化到 $O(n^2)$．然后我们发现出题人卡了空间．/qd

那么我们考虑将点按 $x$ 排序，然后设 $f_{i, 0 / 1}$ 表示考虑从 $i$ 出发，第一个向 左 / 右 偏转的闪电个数．转移考虑插入点 $i$ 作为闪电中的第一个点或第二个点造成的贡献．

D. 三

定义一个三元组 $(i, j, k)$ 的价值为 $a_i + a_j + a_k$．

假设在一次询问中，我们作为答案的三元组为 $(i, j, k)$．尝试观察能够作为答案的三元组的性质．

• 如果 $a_i < a_j$，且存在 $i < p < j$ 使得 $a_p > a_i$，显然 $(p, j, k)$ 合法且更优．
• 如果 $a_i > a_j$，且存在 $i < p < j$ 使得 $a_p > a_j$，显然 $(i, p, k)$ 合法且更优．

那么每个数可以与左 / 右边第一个比它大的数作为答案中的前两个，有用的前两个形成的对只有 $O(n)$ 个．

考虑 从右到左 进行扫描线，对每个位置维护值 $c_i$ 表示三元组 $(x, y, i)$ 取到最大价值时，$a_x + a_y$ 的值，答案就是区间内 $a_i + c_i$ 的最大值．$l \to l - 1$ 的过程中，考虑插入 $a_l$ 造成的影响，将 $l$ 作为第一个元组的有用的对加入时，对 $c_i$ 的影响形如后缀取 $\max$．具体而言，设当前加入的对是 $(l, i)$，那么相当于将 $[i + (i - l), n]$ 这段后缀对 $a_l + a_i$ 取 $\max$．

以下是一些民科内容，不保证正确性，建议不看．

注意此处从左到右扫描线不可做．因为若想从左到右进行扫描线，我们必定要在三元组的第一个数处计算贡献，不然区间查询就废掉了．这样的话我们就需要找到关于三元组中后两个元素的性质，然而注意到我们的不等号方向是 $j - i \le k - j$，考虑前两个数形成的对时，我们对答案做的调整是在放松这个不等式．但当我们尝试调整后两个数形成的对时，我们是在往紧的方向调整，然后性质就不好了．

Day 12

A. 购票

差分计算每条路会被走多少次，然后贪心一下．

B. 复制

我超，原．

C. 正方形

卡常．/oh

预处理每个点向 上 / 下 / 左 / 右 能走多少步，然后枚举正方形对角线所在直线，计算有多少点对可以作为对角．

玩一下限制发现是经典二维数点，扫描线一下．

D. 逆序对

我超，原．

深搜剪枝有 95 分，拜谢 ckain．

正解还不是很会啊，晚些时候补．