(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）
T1 直角三棱锥
签到题。思路有三种：
• 打表，然后差分两次就发现，答案是 𝐾 三次方级别的多项式，插值或猜一猜 就出来了；
•求几次和就出来了；
•答案也可以视作是 𝑥 + 𝑦 + 𝑧 ≤ k, 𝑥 ≥ 0, 𝑦 ≥ 0, 𝑧 ≥ 0 整数解的个数，也即是
𝑥 + 𝑦 + 𝑧 + 𝑐 = k, 𝑐 ≥ 0 整数解的个数。
T2 前缀查询
在 Trie 上类似线段树一样地打标记，记录子节点需要变化多少声望值， 当前这个 节点作为名字属于多少人，作为名字声望值的和为多少，有多少人名字匹配前缀， 作为前缀的总声望值的和是多少， 这五个信息直接记录一下（或者通过之间的关 系也可以少记一点）。
每次操作先下传好标记，然后进行相应的操作就好。 顺带一提，线段树也可以看作是二进制数的 Trie，可以发现这两种数据结构也是有
一定关系的。
T3 可达性
先将强联通分量缩为点，将图转为 DAG，DAG 中每个入度为 0 的点的个数就是答 案的个数； DAG 每个入度为 0 的点，对应原图中的点集任选一个就能构成答案； 因为需要字典序最小的，各自取标号最小的点，升序排序后即为字典序最小的答案。
T4 codeJan和树
可以通过一遍 dfs 获取所有树的 beauty。如果直接枚举子树的话，可能不太好做。 不妨枚举被减掉的子树，在这个子树 上找到一个祖先树，使得祖先树减掉这个子 树可以获得不超过 m 的最大数值。显然祖先树的 beauty 按照距离从近到远 是单调 递增的，符合二分的性质，所以可以二分选择祖先树根节点到当前子树根节点的路 径上结点数，假设为 K。那么 知道了 K 如何确定祖先树根节点的编号呢？因为任 何一个正整数都可以表示成 2 的幂次相加，预处理一下 2 的幂次， dfs 的时候倍增 得到祖先，就可以在大概 log(n) 的复杂度内得到相应的祖先了。总的时间复杂度 大概为O(n log(n))。
可以通过一遍 dfs 获取所有树的 beauty。如果直接枚举子树的话，可能不太好做。 不妨枚举被减掉的子树，在这个子树 上找到一个祖先树，使得祖先树减掉这个子 树可以获得不超过 m 的最大数值。显然祖先树的 beauty 按照距离从近到远 是单调 递增的，符合二分的性质，所以可以二分选择祖先树根节点到当前子树根节点的路 径上结点数，假设为 K。那么 知道了 K 如何确定祖先树根节点的编号呢？因为任 何一个正整数都可以表示成 2 的幂次相加，预处理一下 2 的幂次， dfs 的时候倍增 得到祖先，就可以在大概 log(n) 的复杂度内得到相应的祖先了。总的时间复杂度 大概为O(n log(n))。
T5 无效位置
离线倒着做，相当于每次操作把一个位置 x 变成有效的，给每个点开一个线性基， 每次操作相当于合并 x-1（如果已经有效）所在区间，x，x+1（如果已经有效）所 在区间的线性基，并记录在 x-1 所在区间的最左端，用并查集维护即可。
T6 细胞
现在可以计算出所有的值，只需要再做一次 IDFT 就能求出 f(x)的各项系 数，注意到给定的模数是经典的 NTT 模数，因此在模意义下直接计算即可，时间复杂度 O(2 (m+logn))。
其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305
全部评论
(0) 回帖