Whisper-6's Blog!

题意 ： 维护一个长为 的序列 ，支持下列操作 :

• 区间或
• 区间与
• 区间求

，时限 。

题意：给出一个长度为 的非负整数序列 ，记 为 中选出若干不相邻元素的和的最大值。

求下列式子的值。

答案可能较大，对 取模。

，时限 。

题意：维护 个多重集 ，初始时均为空集。

支持下列操作：

• 向 中加入 。

• 记 ，对于 ，若 ，则从 中删去一个 。

• 查询 ，或指出 均为空。

，时限 。

题意 ： 一个长度为 的字符串 ，它仅由 C 和 T 两种字母组成。

每次询问给出 和 ，求至少在 中删除多少个字符，才能保证：对于其每一个前缀和后缀，其 C 的数量都不小于 T 的数量。

，时限 。

题意：给出一棵 个节点的树，每个节点有 的概率为白色， 的概率为黑色。

求纯黑邻域的最大半径的期望，答案对 取模。

，时限 。

题意：给出一张 个点的有向图，其中 点有点权 。

对于 ，边 的权值为 。

求图的最短哈密顿环。

，时限 。

题意 ： 给出圆上均匀分布的 个点，要求连接 条弦，使得每个点只连接一条弦。

已给出 条弦，问在所有连边方案中，弦形成的联通块数目的和。

答案对 取模。

，时限 。

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

称一个长度为 的 字符串 合法，当且仅当：

初始时有两个空序列 ，按 的顺序，若 则把 添加到序列 末尾，否则添加到序列 末尾。最终 的前缀最大值个数相等。

求字典序最小的合法字符串 。

，时限 。

题意：有一棵 个顶点的树，点 有权值 。

初始时玩家在顶点 ，游戏目标是到达顶点 。

记玩家血量为 ，初始为 。第一次到达顶点 时，令 ，若此时 ，（无论 是否是终点）则游戏失败。

判断游戏是否能成功。

多组数据，，，时限 。

题意：给定一张 点 条边的有向无环图，你可以至多添加 条有向边，使得这仍然是一个有向无环图，使得字典序最小的拓扑序的字典序尽量大。

求出这个最大的最小拓扑序，并构造一种加边方案。

，时限 。