做题记录 25.9.3

· · 个人记录

\purple\odot AT_arc165_f [ARC165F] Make Adjacent

令 l_x,r_x 为值 x 的两次出现位置，对于 x,y 若 l_x<l_y,r_x<r_y，则 x 必然在 y 之前

将 (l_x,r_x) 放到欧氏平面上，按顺序取出数字，则一个数字能被取出当且仅当其左下角没有点，一个点向右上角的点连有向边，则转化为求字典序最小拓扑序

线段树优化建图即可，注意求字典序最小时认为额外点的字典序为 0

时间复杂度 O(n\log^2 n)，空间复杂度 O(n\log n)

代码

参考

发现字典序为 0 的点有 O(n\log n) 个，非 0 的有 n 个，因此前者用队列维护，后者用堆维护可以做到时间复杂度 O(n\log n)

存在空间复杂度 O(n) 时间复杂度 O(n\log n) 的解法

\blue\odot AT_abc345_f [ABC345F] Many Lamps

一个大小为 l 的连通块中至多选择 2\lfloor\frac l2\rfloor 个，若 k 超过 2\lfloor\frac l2\rfloor 的总和或 k 为奇数则显然无解，否则一个连通块中选择偶数个，搜索树上从下往上确定即可

时间复杂度 O(n+m)

代码

\purple\odot AT_arc199_c [ARC199C] Circular Tree Embedding

显然一棵树合法当且仅当对于每个子树，对于每个排列，都恰好存在一个区间（环意义下的区间）使得区间内数的集合等于该子树内结点编号集合

显然任意一个排列整体加上一个数（\bmod n 意义下，且 0\to n）相当于环旋转，不影响解的合法性，因此先令所有排列的 1 出现在第一个位置

显然所有排列同步置换不影响合法解数量，因此将第一个排列调整为 [1,2,3,\cdots,n]（其他排列同步变换）

此时可断环为链，即不需要考虑区间覆盖一个前缀和一个后缀的情况，且子树恰好对应一个区间（[l,r] 中结点编号集合恰好为 [l,r]\cap \mathbb N）

令 o_{l,r} 表示 [l,r] 能否作为一个子树（是否对于任意排列，都有区间 [l,r] 的极差等于 r-l），容易 O(mn^2) 预处理

令 f_{l,r} 表示 [l,r] 作为一个子树的方案数，令 g_{l,r} 表示 [l,r] 划分为若干子树的方案数，则 f_{l,r}=[o_{l,r}]\sum_{k=l}^r g_{l,k-1}g_{k+1,r}，g_{l,l-1}=1,g_{l,r}=\sum_{k=l}^r f_{l,k}g_{k+1,r}

总时间复杂度 O(mn^2+n^3)

代码

参考