文章分类:题解

    文章分类:题解

    • 「2025 杭电多校 2」1004. 子串的故事(2)

      HDU 7994

      对于一个包含字符串 s1,s2,…,sks_1, s_2, \dots, s_k 的字符串可重集 TT,定义 TT 的价值为

      ∑1≤i<j≤kLCP(si,sj)\sum\limits_{1 \leq i < j \leq k} \mathrm{LCP}(s_i, s_j)

      给出一个长度为 nn 的字符串 SS,下标从 11 到 nn。有一个初始为空的字符串集合 TT。

      有 mm 次操作,每次操作给出两个正整数 l,rl, r (1≤l≤r≤n1 \leq l \leq r \leq n),你需要将字符串 S[l:r]S[l : r] 的所有前缀都加入集合 TT。形式化地,对于所有 l≤i≤rl \leq i \leq r,你需要将 S[l:i]S[l : i] 加入集合 TT。

      每次操作过后,你都需要求出此刻集合 TT 的价值。答案对 109+710^9 + 7 取模。

      数据范围:1≤n,m≤1051 \leq n, m \leq 10^5。

      时空限制:88s / 512512MiB。

    • 「Ynoi2006」rldcot

      Luogu P7880

      给出一棵包含 nn 个节点的树,以 11 为根,边带权。

      定义 depx\mathrm{dep}_x 表示节点 xx 到根的简单路径上的边权和。

      有 QQ 次查询,每次查询给出两个参数 l,rl, r,对于所有满足 l≤i,j≤rl \leq i, j \leq r 的二元组 (i,j)(i, j),你需要求出有多少种不同的 depLCA(i,j)\mathrm{dep}_{\mathrm{LCA}(i, j)}。

      数据范围:1≤n≤1051 \leq n \leq 10^5,1≤Q≤5×1051 \leq Q \leq 5 \times 10^5,−109≤w≤109-10^9 \leq w \leq 10^9,1≤l≤r≤n1 \leq l \leq r \leq n。

      时空限制:500500ms / 512512MiB。

    • 「2025 ICPC 武汉邀请赛」J. Dictionary

      QOJ 10745

      给出一个长度为 nn 的字符串 SS。定义字典为 SS 的所有本质不同的子串构成的集合,定义单词为字典中的字符串。

      有 QQ 次操作,每次操作会给出两个参数 l,rl, r,你将会在字典中,学习以 S[l:r]S[l : r] 为前缀的所有单词。每次操作结束后,你需要求出有多少个单词被你学习过。

      数据范围:1≤n,Q≤2×1051 \leq n, Q \leq 2 \times 10^5,1≤l≤r≤n1 \leq l \leq r \leq n。

      时空限制:44s / 10241024MiB。

    • 「NOIP2024」树上查询

      Luogu P11364

      给出一棵包含 nn 个节点的树,以 11 为根。

      定义 depu\mathrm{dep}_u 表示节点 uu 的深度,定义 LCA∗(l,r)\mathrm{LCA}^{*}(l, r) 表示区间 [l,r][l, r] 中所有节点的最近公共祖先。

      有 QQ 次查询,每次查询给出三个整数 l,r,kl, r, k,你需要求出

      max⁡l≤l′≤r′≤r∧r′−l′+1≥kdepLCA∗(l′,r′)\max\limits_{l \leq l' \leq r' \leq r \land r' - l' + 1 \geq k} \mathrm{dep}_{\mathrm{LCA}^{*}(l', r')}

      数据范围:1≤n,Q≤5×1051 \leq n, Q \leq 5 \times 10^5,1≤l≤r≤n1 \leq l \leq r \leq n,1≤k≤r−l+11 \leq k \leq r - l + 1。

      时空限制:22s / 10241024MiB。

    • 「gym103483」C. How Many Strings Are Less

      gym103483 C

      给出一个包含 nn 个字符串的集合 DD 以及一个字符串 ss,你需要找出集合 DD 中字典序小于 ss 的字符串数量。

      字符串 ss 会经过 QQ 次修改,每次修改会给出一个整数 kk 以及一个字符 cc,表示将字符串 ss 从第 kk 个字符开始到字符串末尾的所有字符替换成 cc。每次修改完字符串 ss 之后,你都需要求出集合 DD 中字典序小于 ss 的字符串数量。

      数据范围:1≤n,Q≤1061 \leq n, Q \leq 10^6,1≤∣s∣≤1061 \leq |s| \leq 10^6,字符串集合 DD 的总长不超过 10610^6。

      时空限制:22s / 512512MiB。

    • 「CF917D」Stranger Trees

      CF917D

      给出一棵大小为 nn 的树。

      对于每个 kk (0≤k≤n−10 \leq k \leq n - 1),你需要求出有多少个大小为 nn 的带标号树与原树有恰好 kk 条重合的边。答案对 109+710^9 + 7 取模。

      数据范围:1≤n≤1001 \leq n \leq 100。

      时空限制:11s / 250250MiB。

    • 「CF1830D」Mex Tree

      CF1830D

      给出一棵包含 nn 个节点的树。你需要给每个节点染上数字 00 或 11。

      路径 (u,v)(u, v) 的权值,等于从 uu 到 vv 的最短路径上所有节点数字的 MEX。一种染色方案的权值等于所有 1≤u≤v≤n1 \leq u \leq v \leq n 的路径 (u,v)(u, v) 的权值之和。

      请求出所有的染色方案中,可能的最大权值。

      数据范围:1≤n≤2×1051 \leq n \leq 2 \times 10^5。

      时空限制:33s / 256256MiB。

    • 「CF1444C」Team-Building

      CF1444C

      给出一张包含 nn 个点 mm 条边的无向图,每个点有一个颜色 cic_i (1≤ci≤k1 \leq c_i \leq k),求有多少组颜色对 a,ba, b (a<ba < b) 满足保留颜色为 aa 或 bb 的节点的导出子图是二分图。

      数据范围:1≤n≤5×1051 \leq n \leq 5 \times 10^5,0≤m≤5×1050 \leq m \leq 5 \times 10^5,2≤k≤5×1052 \leq k \leq 5 \times 10^5。

      时空限制:33s / 500500MiB。

    • 「CF2077D」Maximum Polygon

      CF2077D

      给出一个长度为 nn 的数组 aa,你需要找出字典序最大的子序列 ss,使得 ss 可以作为多边形的边长。

      当且仅当 ∣s∣≥3|s| \geq 3 且满足以下条件时,ss 可以作为多边形的边长

      2⋅max⁡(s1,…,s∣s∣)<s1+⋯+s∣s∣2 \cdot \max(s_1, \dots, s_{|s|}) < s_1 + \dots + s_{|s|}

      数据范围:3≤n≤2×1053 \leq n \leq 2 \times 10^5,1≤ai≤1091 \leq a_i \leq 10^9。

      时空限制:33s / 250250MiB。

    • 「CF1637F」Towers

      CF1637F

      给出一棵包含 nn 个点的树,编号 1∼n1 \sim n。第 ii 个点的高度为 hih_i。

      你可以在任意点放置任意数量的塔,对于每个塔,你可以选择放在哪个点,并且可以选择它的效率。设置一个效率为 ee 的塔需要花费 ee 金币,其中 e>0e > 0。

      如果存在一对分别位于 u,vu, v (u≠vu \neq v) 的信号塔,它们的效率分别为 eu,eve_u, e_v,且满足 min⁡(eu,ev)≥hx\min(e_u, e_v) \geq h_x,且点 xx 位于从 uu 到 vv 的路径上,则我们认为 xx 能够收到信号。

      请你求出使得所有顶点都接收到信号,所需的最小金币数。

      数据范围:2≤n≤2×1052 \leq n \leq 2 \times 10^5,1≤hi≤1091 \leq h_i \leq 10^9。

      时空限制:22s / 256256MiB。