chxH
脑筋急转弯题. 首先注意到 $t_{n-1}$ 和 $t_n$ 的前 $n-2$ 个字符完全相同,所以
$$\operatorname{lcp}(t_{n-1},t_n)\ge n-2.$$另一方面,每个 $t_i$ 的长度都是 $n-1$,因此答案只可能是 $n-2$ 或 $n-1$. 我们只需要判定是否存在两个不同的位置 $i,j$,使得 $t_i=t_j$.
不妨设 $i<j$. 比较删去第 $i$ 个字符和删去第 $j$ 个字符后的两个字符串,在区间 $[i,j-1]$ 上必须满足
$$s_k=s_{k+1}\qquad(i\le k<j).$$也就是
$$s_i=s_{i+1}=\cdots=s_j.$$因此,存在 $t_i=t_j$ 当且仅当原串中存在一对相邻且相同的字符. 必要性由上面的式子直接得到. 充分性则只需要选择这两个相邻位置,分别删掉其中一个字符,得到的两个字符串必然完全相同.
最终答案为
$$\begin{cases} n-1,&\exists i,\ s_i=s_{i+1},\\ n-2,&{\rm otherwise}. \end{cases}$$直接扫描一遍字符串即可,复杂度为 $O(n)$.
J
贪心题. 首先将三个人按照离开时间重新编号,使得
$$l_1\le l_2\le l_3.$$先判断是否存在做完所有题的方案. 我们可以按照第 $1,2,3$ 个人的顺序,先做完第 $1$ 个人的所有题,再做第 $2$ 个人的所有题,最后做第 $3$ 个人的所有题. 记三类题目的总耗时分别为 $S_1,S_2,S_3$,则可行性条件为
$$S_1\le l_1, \qquad S_1+S_2\le l_2, \qquad S_1+S_2+S_3\le l_3.$$这不仅是充分条件,也是必要条件. 必要性显然,因为在 $l_i$ 之前必须完成所有截止时间不超过 $l_i$ 的题. 对于充分性,若一个方案中截止时间较晚的题排在截止时间较早的题前面,那么交换二者不会使任何题超时. 不断交换就能得到上面的顺序.
接下来考虑在所有题都能做完的前提下最小化总罚时. 对于任意一个人,把属于他的题目从整个做题顺序中抽出,得到的子序列一定按照耗时从小到大排列. 若同一个人的两道题中长题在短题前面,交换它们不会破坏可行性,却会严格减小总完成时.
先从初始的 $1\to2\to3$ 顺序理解这个贪心. 假设第 $2$ 个人的第一道剩余题耗时为 $b$,第 $1$ 个人当前的最后一道题耗时为 $a$,且 $b<a$. 若把 $b$ 交换到 $a$ 前面不会导致第 $1$ 个人的题超时,那么这次交换会使罚时减少 $a-b$. 一旦第一次交换可行,继续让 $b$ 向前跨过更长的题也不会继续推迟第 $1$ 个人最后一题的完成时间. 因此 $b$ 应当一直向前移动,直到它前面的题耗时不大于 $b$.
这启发我们不需要真的一项项交换,而可以从前往后直接构造最优顺序. 为每个人维护一个按耗时升序排列的队列,并维护他还没做的题目总耗时 $S_i$. 设当前已经用时为 $now$,尝试选择第 $k$ 个队列队头的题,其耗时为 $c$. 首先要求这道题自身能够按时完成,即
$$now+c\le l_k.$$之后临时令
$$now'=now+c, \qquad S_k'=S_k-c,$$再用 $1\to2\to3$ 的顺序检查剩余题目. 对于每个仍然有题未完成的人 $i$,必须满足
$$now'+\sum_{j=1}^{i}S_j'\le l_i.$$一个人若已经没有剩余题目,那么他的截止时间不再参与之后的可行性判定. 不过在取走他的最后一道题时,仍然需要用 $now+c\le l_i$ 检查这道题本身.
每一轮分别尝试三个非空队列的队头,再从所有不会使剩余题目变得无解的队头中,选择耗时最小的一道题接到序列末尾. 选择后更新 $now,S_i$,并将当前的 $now$ 加入总罚时. 这个过程与从一个初始可行序列出发,不断进行不破坏可行性的短题前移交换完全等价,所以最终得到的就是最小总罚时.
对三个队列分别排序的复杂度为 $O(n\log n)$. 之后一共进行 $n$ 轮,每轮只尝试至多 $3$ 个队头,复杂度为 $O(n)$. 因此总复杂度为 $O(n\log n)$,空间复杂度为 $O(n)$. 总罚时需要使用 64 位整数,最后判断其是否严格小于 $t$ 即可.
I
很有意思的 DP 计数题. 首先考虑只给出一条 DFS 序列时,应该如何描述一棵能够生成它的树.
记这条 DFS 序列为 $d$,节点 $x$ 在序列中的位置为 $p_x$,并为每个节点钦定一个子树大小 $siz[x]$. 于是节点 $x$ 对应序列中的区间
$$[p_x,p_x+siz[x]-1].$$我们还要求 $siz[x]\ge1$,所有区间均不越过序列末尾. 特别地,根节点 $1$ 对应整个区间 $[1,n]$. 若任意两个这样的区间要么互不相交,要么一个包含另一个,那么这些区间便构成一个层叠结构. 将 $x$ 的父亲定义为严格包含 $x$ 对应区间的最小区间所对应的节点,即可唯一还原出一棵树. 反过来,任意一棵以 $d$ 为 DFS 序的树,每棵子树在 $d$ 中都恰好占据一个连续区间. 因此,一条 DFS 序列上的合法 $siz$ 赋值与能够生成这条序列的树一一对应.
接下来需要判定第一条 DFS 序列所确定的树能否生成其余 DFS 序列. 这里用到下面这个很常用的结论.
对于一个 DFS 序列 $d$,令 $p_x$ 表示节点 $x$ 在 $d$ 中出现的位置,即 $d_{p_x}=x$. 那么 $d$ 是有根树 $T$ 的一个合法 DFS 序列,当且仅当对于每个节点 $x\in T$,都有
$$\begin{aligned} \{d_y\mid p_x\le y<p_x+siz[x]\} &=\{y\mid y\text{ 在以 }x\text{ 为根的子树中}\}. \end{aligned}$$其中 $siz[x]$ 表示以 $x$ 为根的子树大小.
必要性显然. DFS 第一次访问节点 $x$ 后,会连续遍历完以 $x$ 为根的整棵子树,之后才会离开它. 因此,从位置 $p_x$ 开始的 $siz[x]$ 个节点恰好就是 $x$ 的子树节点.
下面对树的结构归纳证明充分性. 叶子节点的结论显然. 对于一个非叶节点 $x$,它的各棵儿子子树两两不交,并且根据条件,每棵儿子子树都在 $d$ 中形成一个连续区间. 这些区间恰好拼成 $x$ 后面的整个子树区间. 按照这些区间在 $d$ 中出现的顺序访问 $x$ 的各个儿子,再根据归纳假设生成每棵儿子子树内部的序列,即可生成以 $x$ 为根的完整区间. 最终对根节点应用该结论即可生成整个 $d$.
于是我们可以只在第一条 DFS 序列上决定树的结构,再用这个 lemma 验证它能否生成其余所有序列. 预处理布尔数组 $yes[x][s]$,表示能否令 $siz[x]=s$,同时满足对于每个 $1\le j\le m$ 都有
$$\{DFS_{j,y}\mid pos_{j,x}\le y<pos_{j,x}+s\}=\{DFS_{1,y}\mid pos_{1,x}\le y<pos_{1,x}+s\}.$$集合相等也不需要真的维护集合. 对于固定的第 $j$ 条序列,定义
$$q_j[k]=pos_{j,DFS_{1,k}},$$也就是第一条序列中第 $k$ 个节点在第 $j$ 条序列中的位置. 固定节点 $x$,从 $pos_{1,x}$ 开始向右扩展候选区间,并维护这段区间中 $q_j[k]$ 的最小值 $mn$ 和最大值 $mx$. 对于长度 $s$,由于其中恰好包含 $s$ 个互不相同的位置,两个节点集合相等当且仅当
$$mn=pos_{j,x}, \qquad mx=pos_{j,x}+s-1.$$对每条 DFS 序列和每个区间起点都向右扫描一次,即可在 $O(mn^2)$ 的时间内求出全部 $yes$. 由于本题中 $n,m\le500$,这个预处理处在 $O(n^3)$ 的规模内.
之后在第一条 DFS 序列上进行区间 DP. 令 $f[l][r]$ 表示有多少种合法且满足 lemma 条件的 $siz$ 赋值,使得第一条序列中的区间 $[l,r]$ 恰好形成一棵以 $DFS_{1,l}$ 为根的子树. 因而必须有
$$siz[DFS_{1,l}]=r-l+1.$$再令 $g[l][r]$ 表示将 $[l,r]$ 划分成若干个连续子树区间的方案数. 如果一组分界点为
$$l\le i_1<i_2<\cdots<i_k=r,$$那么它对 $g[l][r]$ 的贡献就是
$$f[l][i_1]f[i_1+1][i_2]\cdots f[i_{k-1}+1][i_k].$$因此,$g$ 相当于记录由一排兄弟子树构成的有序森林. 对于一棵以 $DFS_{1,l}$ 为根的子树,删掉根以后,$[l+1,r]$ 必须恰好构成这样一片森林,所以
$$f[l][r]=g[l+1][r]\cdot yes[DFS_{1,l}][r-l+1].$$而 $g[l][r]$ 可以按照第一棵子树的右端点 $mid$ 分类:
$$g[l][r]=f[l][r]+\sum_{mid=l}^{r-1}f[l][mid]g[mid+1][r].$$边界为
$$g[l][l-1]=1,$$表示空区间只有一种空森林方案. 每种合法赋值中第一棵子树的右端点唯一,因此这个转移不会重复计数. 最终答案就是 $f[1][n]$.
$f$ 的每个状态可以 $O(1)$ 转移,$g$ 的每个状态需要枚举 $mid$,所以 DP 的时间复杂度为 $O(n^3)$,空间复杂度为 $O(n^2)$. 加上前面的预处理,总时间复杂度为 $O(mn^2+n^3)$. 所有计数和转移均对 $10^9+7$ 取模.
B
很有意思的树上 DP. 首先注意到树上的每条边都是桥. 为了访问一条边另一侧的节点并最终回到城市 $1$,每条边都至少需要经过两次,而题目又限制每条边至多经过两次,因此每条边实际上恰好经过两次. 整趟旅行固定包含 $2n-2$ 次移动,不使用优惠券时的总费用恒为
$$C=2\sum_{e\in E}c_e.$$于是对于给定的 $k$,问题等价于在某种合法的树上往返顺序中选出一段长度恰好为 $k$ 的连续边序列,最大化其中的边权和. 记这个最大值为 $best[k]$,最终答案就是
$$ans[k]=C-best[k].$$真正需要考虑的只有什么时候开始使用优惠券,使用以后还能够免费走多少步,以及优惠券生效时应该按照什么顺序遍历当前节点的儿子. 优惠券之外的遍历顺序不会改变答案.
先将树以 $1$ 为根. 记
$$len[u]=2(siz[u]-1)$$为从 $u$ 出发完整遍历它的子树并回到 $u$ 所需的移动次数,再记
$$sum[u]=2\sum_{e\in E(T_u)}c_e$$为这个过程经过的边权和. 最朴素的想法是设计两个相互转移的三维状态:
$$f[u][i][j]$$表示在 $u$ 的子树内部某处开始使用长度为 $i$ 的优惠券,当遍历完这棵子树并返回 $u$ 时已经免费走了 $j$ 步,最多能够免除多少费用.
$$g[u][i][j]$$表示进入 $u$ 时长度为 $i$ 的优惠券已经使用了 $j$ 步,接下来遍历 $u$ 的子树并回到 $u$,能够在这棵子树中额外免除的最大费用. 如果
$$i-j\ge len[u],$$那么整棵子树都可以被优惠券覆盖,此时显然有 $g[u][i][j]=sum[u]$.
不过这里的 $i,j$ 并不是两个独立的信息. 对于 $f$,我们只关心从优惠券开始生效到返回 $u$ 为止实际经过了多少条边. 对于 $g$,我们只关心进入 $u$ 时优惠券还能覆盖多少条边,也就是 $i-j$. 因此可以将状态压缩为
$$f[u][t],\qquad g[u][t].$$考虑任意一种从 $u$ 出发,完整遍历 $T_u$ 后回到 $u$ 的合法序列. $f[u][t]$ 表示这种序列长度为 $t$ 的后缀能够取得的最大边权和,$g[u][t]$ 则表示长度为 $t$ 的前缀能够取得的最大边权和. 两个状态本质上分别描述优惠区间穿出和穿入一棵子树的情形,下标范围均为 $0\le t\le len[u]$.
接下来就是一个类树上背包状物. 对于 $u$ 的儿子 $v$,从 $u$ 出发完整遍历 $v$ 的子树再返回 $u$,需要经过
$$L_v=2siz[v]$$条边,若这整段都被优惠券覆盖,能够免除
$$V_v=sum[v]+2c(u,v)$$的费用.
计算 $f[u]$ 时,每个儿子有三种安排方式:
- 在优惠券开始之前遍历,对状态没有贡献.
- 在优惠券开始以后被完整遍历,向背包中加入长度 $L_v$ 和收益 $V_v$.
- 优惠券在这棵儿子子树内部开始. 若在 $v$ 的子树中免费走了 $x$ 步,那么取 $f[v][x]$,再免费经过一次 $v\to u$,总共贡献 $x+1$ 步以及 $f[v][x]+c(u,v)$ 的收益.
第三类儿子至多只有一个. 所有第一类儿子放在它之前,所有第二类儿子放在它之后即可. $g$ 的转移完全对称: 先完整覆盖若干棵儿子子树,再在至多一棵儿子子树内部用完优惠券,剩余儿子放到优惠券结束以后.
实现时需要注意,程序中合并儿子的顺序并不代表它们在实际遍历中的顺序. 可以维护一个标志,记录是否已经选定那棵被部分覆盖的儿子. 一棵完整覆盖的儿子在两种标志状态下都可以加入背包,最后再把未覆盖的儿子,部分覆盖的儿子和完整覆盖的儿子按照对应角色重新排列. 这样就不会因为固定的合并顺序漏掉方案.
最后考虑一段完整的优惠区间. 取它的起点和终点所在位置的 LCA $u$,那么整段优惠区间可以拆成:
- 从某棵儿子子树内部返回 $u$ 的后缀,由 $f$ 描述.
- 若干棵被完整覆盖的儿子子树.
- 从 $u$ 进入另一棵儿子子树的前缀,由 $g$ 描述.
若某个端点恰好位于 $u$,就把对应部分的长度看作 $0$. 如果两个端点都在同一棵儿子子树中,则递归到那棵子树内处理.
为了统计完整的优惠区间,再令 $h[u][t]$ 表示完全位于 $T_u$ 的遍历中,长度为 $t$ 的连续段能够取得的最大边权和. 合并儿子时可以维护一个两位的状态,分别记录是否已经选择了左端点所在的后缀儿子以及右端点所在的前缀儿子. 对于每个儿子,可以把它放在优惠区间外,完整放入优惠区间,作为左端点使用 $f$,或者作为右端点使用 $g$. 同一个儿子不能同时充当左右两端. 完成选择后,把左端点儿子放在最前面,完整覆盖的儿子放在中间,右端点儿子放在最后面,就一定能构造出对应的实际访问顺序.
两端落在同一棵儿子子树中的情况由 $h[v]$ 继承,两端的 LCA 恰好为 $u$ 的情况由上述背包产生. 因此最终有
$$best[k]=h[1][k].$$每个节点只需要维护 $O(siz[u])$ 个状态. 合并边 $(u,v)$ 时使用标准树上背包,复杂度为当前已经合并的子树大小与 $siz[v]$ 的乘积. 将每一对节点按照它们的 LCA 归入对应的一次合并后,可以看出整棵树上的复杂度之和为 $O(n^2)$. 空间复杂度为 $O(n^2)$,所有费用均使用 64 位整数. 最后输出所有 $C-h[1][k]$ 即可.
F
受沈阳区域赛那道图论构造题的启发,我们可以把指定环作为整张图中唯一保留下来的环.
首先按照题目给出的顺序将环定向为
$$p_1\to p_2\to\cdots\to p_k\to p_1.$$接下来把所有环上点的距离设为 $0$,从这些点开始进行多源 BFS,求出每个点到环的最短距离 $dis_u$. 对于至少有一个端点不在环上的边:
- 如果两个端点的距离不同,就从距离较大的点指向距离较小的点.
- 如果距离相同,就从原编号较大的点指向原编号较小的点.
对于环上点之间的非环边,按照 $p_1,p_2,\ldots,p_k$ 的顺序编号,从编号较小的点指向编号较大的点.
这样一来,所有涉及环外点的有向边都会使二元组 $(dis_u,id_u)$ 严格减小,所以环外不可能产生有向环. 同时环上点不存在指向环外点的边. 因此对整张图进行 Kahn 拓扑删除后,所有环外点都会被删除,而每个环上点始终保留一条来自环上前驱的入边,不会进入队列. 最终没有被删除的点恰好就是指定环上的点.
现在只考虑这些点的导出子图. 其中保留了完整的指定环,其余边则全部从环序较小的位置指向环序较大的位置. 接下来维护每个点在当前图中的入度,把所有入度恰好为 $1$ 的点加入队列.
假设取出的点为 $v$,它当前唯一的入边为 $u\to v$. 由于所有环边始终没有被删除,$v$ 至少保留着来自环上前驱的入边. 现在它只有这一条入边,所以 $u$ 一定就是 $v$ 在指定环上的前驱. 于是记录
$$nxt_u=v,$$并删除 $u$ 指向其他点的所有边. 这些边一定都是非环边,删除它们不会破坏真正的环,同时可能使更多点的入度降为 $1$.
这个过程一定能够处理完所有环上点. 初始时 $p_1$ 的入边只有 $p_k\to p_1$,而 $p_2$ 的入边只有 $p_1\to p_2$. 处理 $p_2$ 后会删除 $p_1$ 指向后方的所有非环边,从而使 $p_3$ 只剩下 $p_2\to p_3$ 这一条入边. 如此归纳下去,$p_3,p_4,\ldots,p_k$ 都会依次变得可处理. 队列中即使提前出现其他入度为 $1$ 的点也没有影响,因为此时识别出的唯一入边同样必然是环边.
最后从任意一个环上点开始不断沿着 $nxt$ 行走,就能得到指定环的同向循环序列. 起点可能不同,但这只会产生循环移位,符合题目要求.
多源 BFS,两次删边过程以及最后恢复环序都只会将每条边处理常数次,因此总时间复杂度为 $O(n+m)$.