题目链接 解析 题意就不多阐述了，看原题就够了。个人觉得这是一道练归并排序性质的好题（虽然动规/堆维护等方法似乎也可行，但我认为最朴素的方法才是最美丽的）。 再发觉贪心不可行时，我们考虑分治维护每一轮比赛可能获胜的人。假设我们以及维护好了左区间（即上一轮比赛）哪些人可能能在上一轮获得胜利（也就是能活到当前这轮）以及右区间的这个信息，我们考虑如何合并…

题目链接 题意 给定一个二分图，二分图上的每个点都有一个权值。如果一个左部点的权值和一个右部点的权值的 $\gcd$ 大于 $1$，则这两点之间有一条边。求二分图最大匹配。 解析 首先我们发现，如果暴力建边的话，我们可能会建 $n^2$ 条边，在 $100$ 组数据的情况下，非常容易 TLE。 我们考虑优化。对于一个左部点的权值和一个右部点的权值的…

题目链接 题意 星球的一天有 $h$ 小时，每小时有 $m$ 分钟。现在给定一个当前时间，询问最近的在镜中对称之后合法的时间。 解析 主要是注意一些细节。首先判断最近的对称过去合法的小时，如果给出的时间的小时本身对称过去就是合法的，那么分钟就要从给出的分钟开始找，一直找到第一个合法的。否则，如果小时与给定的不一致，分钟就一定为 $0$，即输出一定为…

题目链接 @GuidingStar 让我来做这道题目然后我就做了一下，结果因为一个愚蠢的错误调了一个小时代码…… 题意 给定一棵树，维护区间后缀积之和，支持单点修改。 解析 个人觉得没那么难想（嗯，搞死我的是细节）。 我们先考虑线段树上如何维护这个东西。我们可以在维护区间后缀积之和的同时维护一下区间积，然后合并的时候只需要将左区间后缀积之和乘上右区…

题目链接 题意 维护一棵树，支持区间求和，区间最大值，区间最小值，区间取反，单点修改。 解析 这是一道很好的树剖练手题，思维难度不高，代码存在一些细节，本题解主要来说明这一部分，也用来警醒自己做题目时需要注意细节，尽可能避免调代码调半天的情况。 边权转点权 在树剖的两边 dfs 过程中，第一遍可以将边权赋给边端点中深度较大的那一个，即儿子节点。我们…

题意 题目链接 有一棵树有粉点有黑点，从根开始走，每走到一个点都会改变颜色。求一种方案使所有点变成黑色。 解析 我们考虑使用递归的方式寻找答案。假设一棵树的深度只有 $2$，那么我们只需要从根开始，找到粉点，走过去再回来，重复几次，就可以使下一层的所有点变为黑色。 以这种方式一层一层染色，最后对于根节点，如果为黑色不用处理，否则，走下去，走回来，再…

解析 题目链接 题意很清晰了。 我们考虑凳子的折扣情况。由于凳子本身也是一个物品，那么如果存在一个比凳子贵的物品在购物车中，那么打折的是凳子，如果有一个比凳子便宜的物品在购物车中——那还不如给凳子打折呢！合着这个商场就是给凳子打折而已。 因此，由于凳子的打折情况最优就是给自己打折，那么我们将凳子按照价格排序，对于前 $k-1$ 辆购物车，每辆购物车…

题意 题目链接 从一个 $1 \sim n $ 的排列中不断选择元素放在头或尾，最终使其有序，询问操作次数。 解析 首先容易发现，至多操作 $n$ 次一定能够使其有序（一个一个拎出最小的或最大的）。 然后我们发现，$n$ 次可以变为 $n-1$ 次，我们先随意确定一个数，比它小的按顺序拎到它左边，后边亦然。 接着我们考虑，能否从确定一个数变为确定一…

题意 题目链接 询问是否：对于 $s$ 中每一个 $s_i$，都找的到一个包含它的 $s$ 的子序列（不是子串）与 $t$ 相同。 解析 首先我们考虑，必须要按顺序找到第一个子序列，否则一定是 No。 例如，若 $t=abcd$，$s$ 的前几项可以为 $aabbbcdd$，但是不能为 $acbcd$，因为第一个 $c$ 一定不满足。 找到之后，我…

题意 题目链接 给出一个长度为 $m$ 的括号串，在其前后增添字符构造长度为 $n$ 的合法括号串，求方案数。满足 $n-m \le 2000$。 解析 容易发现这是一道 dp 且复杂度基于 $n-m$。 我们已知中间的那条括号串 $S$，需要构造出左边的 $P$ 和右边的 $Q$（当然也可能为空）。通过 dp 方程转移时，考虑需要满足的两个条件，…