Whisper-6's Blog!

题意 ： 给出排列 。

Alice 需要将 划分为恰好 个连续区间，然后 Bob 将它们重新排列并拼接，得到排列 。

Alice 时希望 的字典序最小，B 希望 的字典序最大，求最终得到的 。

，时限 。

题意 ： 给定 个点 条边的无向图，边有边权。

每条边有 的概率被删除，求最后这张图的最大基环树森林（可以有普通树）的边权和的期望。

答案对 取模。

，，时限。

题意：给定一个 个点的内向森林，其中 号点为某个树的根。

你需要将这个森林连成一棵以 为根的有根树，并使得最终树（对应的无根树）的最大匹配尽可能大。

，时限。

题意： 有 个布尔变量 ，给出 个限制。

限制形如 （ 为 ）（ 为 ）

一共 次询问，每次询问给出一个区间 。求最少把 划分成多少段连续的区间，使得每段里的限制都可以得到一组合法解。如果无论如何都无法得到合法解，输出 -1。

，，，时限 。

题意 ： 给出一棵 个点的树，选出一些点使得两两距离 ，最大化选出的点数。

，时限。

题意 ： 求出满足下列条件的序列 的数目 ：

• 含有 个 和 个 。
• 恰有 个 满足 的和为 。

，，时限。

对于排列计数 DP 问题，一种经典的手段是插入法：从小到大插入元素。

插入法会破坏相邻项，若问题关心相邻项，则不易考虑。此时可以用并段法：按某种顺序填写数字，并考虑目前已有的连续段。

若问题关心排列数字的大小，可以从小到大插入，构造排列的过程可视为“水淹笛卡尔树”。

题意 ： 给定一棵树，现在需要为每一个点填写权值 ，每条边填写运算 。

填写完后，每次可以选择一条边 收缩，收缩产生的新点权值为 。（其中 是运算）

对于所有 种填写方案，求满足“存在一种收缩顺序使得最终剩余的点权值为 ”的方案数。

，时限。

题意 ： 给出一棵 个点的外向树 ，以及 条额外的边，满足加入这些边之后图 是 DAG。

对于点对 ，若在 中 不能到达 ，但是在 中 可以到达 ，则称点对 是好的。

每次询问给出 ，求有多少对好的 满足 。

，时限。

• 参考资料：《数论选讲》in APIO2024 by zhoukangyang.（多元积性函数）

讲义里提到本题的 做法，但没有细说。我将详细地陈述此做法。