Whisper-6's Blog!

题意：给出一个大小为 的区间集合 。

对于区间集合 ，定义其 SAN 图为：将相交的两个区间之间连边之后产生的图。

若 SAN 图是一棵树，则称集合 是好的。

求 的好的子集的个数，答案对 取模。

，时限 。

题意：给出一个长度为 的序列 。

次询问一个区间内差值最小的对子。

，，时限。

题意：对一棵树染色，求距每个点最近的染色点的距离不超过 的染色方法总和。

• 原题：。

• 加强：。

时限 。

题意 ：两个人（A 与 B）分别从长度为 的数列两端开始取数，如果前一个人取了 个数，后一个人必须取 或 个，第一个人最开始可以取 个或 个，不能操作时结束。

A 想要最大化 A 选的数的和减去 B 选的数的和。B 想要最小化这个值。

两人均采取最优策略，求最终结果。

，时限 ，空限 。

题意：01 背包问题。

体积 ，背包总容量 ，时限 。

题意：给出一棵 个节点的树，点有点权，均为正。

定义树上有向路径 的权值为：其点权的前缀和的和。

求权值最大的有向路径。

，时限 。

题意：有 种酱。你需要若干碗拉面，可以在每碗拉面上放若干种酱，也可以不放（可能的拉面种类为 ）。

拉面集合需要满足：

• 不能出现酱一样的两碗拉面。
• 每一种酱至少在两碗拉面中加了。

求拉面集合的方案数。答案对给定的质数取模。

，时限 。

题意：有三堆牌，分别有 张。牌上写着数字 中的一个。

先从牌堆 中抽一张，接下来，牌上写着几就从几号牌堆抽取。

求在所有可能的 种牌堆方案中，先把牌堆 抽空的方案数。

答案对 取模，。

题意 ： 给出一个 层方格金字塔，自顶向下依次标号为第 到第 层。

其中第 层有 个方格。（具体形态见图）

第 层有一个 到 的排列，其他层的数字按以下规则生成：方格 中填写的整数，是方格 正下方，左下方和右下方方格中所写整数的中位数。

现在给出第 层的数字，求第一层的数字。

，时限 。

题意：给定一棵无根树。

定义 为：对所有大小为 的点集，求能够包含它的最小连通块大小之和。

对于 分别求出 。

答案对 （质数） 取模。

，时限 。