当前位置：首页 > news >正文

UNR#10

news 2026/7/22 1:11:17

不能打 NOI /fn/fn/fn。因为好久没打模拟赛做一下 UNR#10，主要可能是为复现 NOI 做准备。

Day1

vp 100+100+10=210。T3 倍增分块有点太精妙了。

【T2】感觉题目不错，就是有点难写。

首先先考虑判定。考虑固定出现次数 $x$，则发现第 $i$ 段可行的结尾对于 $x$ 始终是一段区间 $[l_i,r_i]$，且 $r_i$ 是尽量后选择 $i$ 段的端点，而 $l_i$ 是尽量前选择 $i$ 段的端点，则 $k$ 合法的条件 $n \in [l_i,r_i]$。考虑 $x+1$ 时的 $[l_i',r_i']$，根据定义不难发现始终有 $r_i <l_i'$，所以每个 $k$ 对应的 $x$ 是唯一的！所以可以对每个 $x$ 单独处理，然后套路的拆开 $l,r$ 将 $\sum n \in [l_k,r_k]=\sum [l_k \le n]-[r_k <n]$，所以分别对 $l,r$ 进行 dp：
- 对于 $l$，这部分比较容易。令 $g_{i,j}$ 表示区间 $[i,j]$ 恰好出现 $x$ 个数的方案书，则令 $f_{u,i}$ 表示 $l_u=i$ 进行转移即可；
- 对于 $r$，发现区间 $[i,j]$ 的转移与 $a_{j+1}$ 有关，不难想到需要 $a_{j+1}$ 的值，即令 $g_{i,j,v}$ 表示 $[i,j]$ 出现 $x$ 个数，且都不是 $v$ 的方案数个数，同样令 $f_{u,i,v}$ 表示 $r_u=i$ 且 $a_{i+1}=v$ 的方案数个数。因为求 $[i+1,j]$ 的方案时已确定 $a_{i+1}$，所以可能需要一点细节。
$v$ 可能很大，但显然值域可压缩 $O(n)$。第二部分的复杂度看上去是 $O(kn^4)$，但事实上 $x \le n/k$，所以复杂度 $O(n^4)$。
【T3】感觉倍增分块很精妙！

考虑一组 $[l,r]$ 如何判定，发现一个巧妙的事实：对于 $k \in [\frac{l+r}2,r-l+1]$，判定 $s_{l,l+k-1}<rev(s_{r-k+1,r})$ 均是可行的！于是联想到使用倍增分块。即取 $k=2^p$ 然后将查询区间分为 $\log $ 组比大小，直接使用 $sa$ 即可做到 $O(n \log^2n+q\log^2n)$！这里有一个小优化，就是事实上每个询问 $[l,r]$ 只有最后一个 $k=2^p$ 会增加查询节点，所以本质上节点只有 $O(n\log n+q)$ 于是复杂度优化到 $O(n\log^2n+q\log n)$。

然后可以有一些 16 叉树的常数优化，还有一个比较 sa 的做法，还没读懂。

trick：感觉比较 Ad-hoc，区分度也比较小。主要是对于 $k$ 的观察感觉非常巧妙！！！

Day2

vp 100+100+20=220，感觉风格和 Day1 差不多，就是 T2 好写一点。

【T2】仙人掌的部分分给得不错 /qiang

看到求 $T$ 的个数而不是 $(T,s)$ 的个数，于是思考合法 $s$ 满足什么条件。发现如果用 $T$ 刻画 $s$ 非常复杂，于是先考虑仙人掌。
对于一个环 $p_1,p_2,\cdots,p_k$，假定断掉 $(p_1,p_2)$，则发现 $p_1$ 可以为 $s$ 当且仅当 $p_2$ 可以为 $s$，如此套环得到合法的 $s$ 在圆方树上是一条链，于是点 - 边容斥 $O(n^22^n)$。发现这里的 "链" 是有种非树边的感觉。
于是直接考虑 $(T,s)$ 若 $s=u$ 成立，则是不是 $u$ 某条非树边的端点 $v$ 也成立？事实上并非如此，因为可能会存在返租边 $(dep_a<dep_b)$ 经过 $v$，但发现将 $v$ 调整为 $b$，不断经过这样的调整可能找到另外一个合法的根。比较显然，根据 $v$ 向子树通过上述的寻找方法，可以找到所有合法点。比较显然，$v$ 与 $u$ 属于同一点双，于是合法点 $s$ 在圆方树上构成联通块！
所以考虑点-边容斥，点好计算，令 $f_{s,i}$ 表示 $s$，根为 $i$ 的方案数个数。对于边，即理解为同点双的两个点 $(u,v)$，刻画一下发现 $u,v$ 可同时称为根的条件是，点双在 $T$ 中是 $u \to v$ 的链，这里直接链 dp 就 ok 了，复杂度 $O(n^22^n)$。
【T3】呜呜有没有 dalao 可以教教我 /kl