题意 题目链接 有若干个点和若干条边，每条边都为 $0$ 或 $1$ ，每次可以对一个点进行操作，与这个点相连的所有边的值都会改变（ $0$ 变为 $1$，$1$ 变为 $0$），现在寻求一种方案，使得所有边最终都变为 $1$ ，若找不到这种方案，输出 Impossible 。 解析 首先我们发现，每个点一定是只操作 $1$ 次或 $0$ 次的，因…

题意 题目链接 需要寻找一种可行的候选人列表并输出，注意每个人在候选人列表找出第一个自己的祖先就会送出礼物。 解析 首先，如果一个人是某一个人的送礼物目标，则这个人就一定会出现在答案序列里。 而如果一个人的祖先已经出现在名单里了的话，则这个祖先的所有儿子即使后续再在列表中出现，也是无意义的。因此我们考虑拓扑排序，建一张反图，并得出该图的拓扑序，再除…

题意 有 $n$ 个计数器和 $m$ 条电线，每个计数器都对应着一个额定值 $a_i$ ，初始时所有计数器的值均为 $0$ ,现在你可以按若干个计数器上的按钮，每次按按钮可以使该计数器以及与该计数器通过电线相连的计数器的值都 $+1$ ，每个计数器最多只能按一次。当你进行这样的操作若干次后，若有一个计数器上的值与该计数器的额定值一样，你就失败了。需…

这题搞了好久才搞过 题意 题目链接 注意，如果他有一种方案能够满足 "Win" 的条件，这时即使有环，结果仍然为 "Win" 。 解析 题目要求判断从起点走若干奇数步数能否到达一个无法走的点，即没有出度的点。因此我们只需要先标记下没有出度的点，再从起点开始 dfs ，判断有没有一次走到没有出度的点时步数为奇数步即可。 然而具体 dfs 的实现没有这…

题意 题目链接 easy version 中要求的是将第一条边最大修改为多少能够使其存在在最小生成树中。 解析 题目与最小生成树相关，又要值尽可能大，很容易想到 kruskal 算法，因为该算法是先将权值小的边加入到最小生成树中的，因此，我们希望第一条边能够尽可能晚的加入到最小生成树中，这样才能使其权值最大。 考虑到要使其尽可能晚加入而且不能不加入…

为什么这么裸的题是紫题。 题意 题目链接 注意权值最小值指的是这 $k$ 条边中权值最小的那条边的值就好，题意叙述的很清楚了。另外注意点号是从 $0$ 开始的。 解析 一看数据范围, $1 \le k \le 10^{10}$ ,很显然正常跑跑不了，既然要快速跑，而本题中又没有对边的权值进行改变，再给了每个点有且仅有一条出边，很容易就能想到倍增。 …

题意 题目链接 这里要注意的是，前继任务已经被执行过了的任务和前继任务被放进副处理器处理的任务是可以一次同时处理的，这也是题面中“或”的含义。另外， $0$ 表示只能在主处理器中处理， $1$ 表示只能在副处理器中处理。最后千万要注意，题目中所给的关系是前一个处理的前提是后一个被处理了，不要搞反。 解析 首先题面告诉我们这是一张 DAG，很容易就会…

题意 题目链接 题目中给出了一个 $N$ ，而我们要求的是有多少对$(a,b)$ 使得一个 $a$ 行 $b$ 列的矩形,满足其对角线穿过的格子数为 $N$。 解析 通过画图以及对题意的观察与分析，我们发现，对于一个 $a,b$ 互质的矩形，其对角线穿过的格子应该是呈阶梯状上升的(如图)。 我们再像小学做这类数学题一样，将这些格子推向两边，可以数出…

题意 一个长度为 $N+M$ 的 $01$ 串，包含 $N$ 个 $0$ 和 $M$ 个 $1$。 现在随机生成这个 $01$ 串，要求在它的每个前缀中，$0$ 的个数都要不多于 $1$ 的个数。 求生成合法串的概率。 解析 首先我们知道，若 $M<N$ ，答案显然为 $0$。 然后我们发现，在 $M \ge N$时，这个题面是非常难求的，我…