Whisper-6's Blog!

题意：大地震把 个城市之间的全部 条道路震垮了。现在，需要紧急恢复 条原来的道路，使得任意两个城市可以互相到达。

每个城市分别存有 吨沥青。修复一条道路需要 吨沥青，如果两个城市 之间有一条损坏的道路，且两个城市的沥青总量 ，那么就可以消耗这两个城市的 吨沥青来修路。

修好了路之后，装载沥青的卡车就可以在路上跑，在这一部分连通的城市中任意地来往运送沥青了。

判定能否让 个城市连通，如果能，输出任意一种修路的方案。

，时间 。

题意：对于序列 ，定义其“前邻序列”为 ，其中 ，特殊地，若不存在 满足条件，则 。

现在给定序列 ，请问对于所有满足 的序列 ，共有多少个不同的“前邻序列”。答案对 取模。

。

题意 ： 给出一张 个点 条边的无向图 。

对于一张图，定义它是好的，当且仅当：

• 图联通

• 初始时将边染成白色，通过（多次）翻转某个点的所有邻边颜色，可以将所有边变为黑色

我们将 的 条边保留一个子集，共有 种方法，问其中多少种形成的图是好的。

答案对 取模。

，时限 。

题意：你经营一家雇用 名员工的商店。每个员工都有固定的工作周期。

具体地，从今天开始，第 位员工重复以下内容：干 天活，休息 天。

从今天开始的每一天，你可以选择的当天上班的员工之一，颁发一枚奖章。（如果没有员工上班，那天你什么也不做）

给每位员工颁发至少 枚奖牌至少需要多少天？

，，时限 。

题意 ： 给出长为 的字符串 ，字符集为 。

可执行下列操作任意次（包括零次）：

• 选定 使得 ，将 换成和原来的 均不同的字符（这个字符是确定的），并删除 。

求你能获得的不同的 的个数。

，时限。

题意：有序列 ，初始时为 ，执行下列操作 次：

• 选择一个元素，将其移到开头或结尾。

给出最终的 ，求出可能的操作方案数。答案对 取模。

，时限 。

题意 ： Snuke 使用 种卡玩游戏，卡的编号为 。初始时，Snuke 有 张 号卡。

游戏里有 种卡组，第 种卡组含 号卡的数目为 。

可以进行下列操作任意次：

• 获取一整套卡组。

• 将 张 号牌换成一张 号牌。

求 Snuke 手上牌数的最小值。

， ，时限 。

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

树上有 块石子，记第 块石子的位置为 ，则当前局面的“不稳定度”定义为 。

给出石子的初始位置，你的目标是将第 个石子移动到节点 ，每次只能将一个石子移到相邻的节点（允许多个石子放在一个节点上），最小化过程中不稳定度的最大值。

，时限 。

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

A 和 B 用这些序列玩游戏，两人轮流进行下列操作，直到所有序列的长度都变为 。

• 删除某个（长度至少为 的）序列的开头或结尾。

A 先手。A 想要最大化最终剩下的 个元素的和，而 B 想要最小化，求最终这 个元素的和。

，时限 。

题意 ：数轴上有 个球，第 个球位置为 。

初始时，数轴全为白色。可以每次选择一个球向左或者向右滚一段距离，且将滚过的部分反色。

给定 个不交的区间，要求恰将这些区间染成黑色。

求球滚过的最小总距离，或指出无解。

，时限 。