题意 题目链接。 给出一颗树，走到叶子节点后可以回到它的第 $k$ 祖先，求最多可以访问多少叶子节点。 解析 定义 $f_{i}$ 为从 $i$ 节点开始走，最后走回到 $i$ 节点的贡献，$g_i$ 为从 $i$ 节点开始走，最后不用回到 $i$ 节点的最大贡献。 先预处理出从每个点开始走可以回到的最高点，对于叶子节点，初始先将其贡献打到其第 $…

题意 题目链接。 $n\times m$ 的场地上存在一些箱子，碰到了就会被推动，不可以使任何箱子被推出场地。求从 $(1,1)$ 走到 $(n,m)$ 的方案数。 解析 发现该问题类似于过河卒，考虑 dp。由于向右和向下移动所涉及的箱子不同，且如果越过了箱子就一定不会再次推到（不能往回走），考虑如下设置状态： 记 $f_{i,j}$ 为从上方走到…

题意 题目链接。 给定一个序列，每次操作可以把某个数 $+1$ 或 $-1$。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。 解析 给出一种该题题解区中都没有提到的做法：整体二分。 对于整个区间按照值域进行二分，初始值域为负极大值到正极大值，每次二分都找出 $mid$ 值的分界线，然后对于左右两个区间依次二分。由于分界线左侧的那个…

题目链接。 题意不多赘述。 解析 由于每次会将石子最多的那堆的序号加入 $S$ 中，我们考虑将原始的石子堆从大到小排序。首先我们发现如果有一堆比其他都要高，我们可以将他取到与第二高的一样高，这样的话结果只可能会更优（因为相同时优先取小的）。 依照这个思路，我们考虑按照高度一层一层取下来，这样答案会越来越优（若存在多个高度相同的，你只需要认为在取的过…

题意 题目链接。 给定一个序列，包含 $n$ 个有重量和价值的物品。需要找出一个连续区间，可以选择其中的至多 $w$ 个物品令其重量减半（向上取整）而价值不变，然后该区间重量和须不大于 $k$。求满足这样条件的总价值最大的区间。 解析 求区间最大价值容易想到双指针。考虑如何维护重量减半（以下简称打折）的 $w$ 个物品。 由于元素会有重复，考虑用两…

文/流凡 你有一群提线木偶， 整整齐齐的都是一种颜色， 你将他们看作无敌的大军， 成为你永世的骄傲。 有的木偶光泽褪了， 或是沾上了其他色彩， 你就将他们扔进箱子里， 暗无天日。 有的木偶变畸形了， 歪歪斜斜得个性十足， 你就将他们一一拆卸， 四分五裂。 有的木偶绳线断了， 自主地奋起舞蹈， 你就将他们扔进火里， 魂飞魄散。 于是， 你再去看看你的…

题意 题目链接。 记 $b_i$ 为 $a_1 \sim a_{2i-1}$ 的中位数，给定序列 $b$，询问是否存在合法的序列 $a$。 解析 考虑 $b_i$ 和 $b_{i-1}$ 的关系。我们先假设 $b_1 \sim b_{i-1}$ 均合法。 若 $b_{i-1}=b_i$，则新增的两个数只需一大一小地取即可，$b_i$ 也一定合法。 …

题意 题目链接。 有一棵红树和一棵蓝树，结点相同而边不同。双方各在某一点，只能在自己颜色的树上移动，红方先手。红方需要最大化游戏轮数，蓝方则需要最小化游戏轮数。求最终游戏轮数。 解析 首先发现，如果存在一条连接 $u,v$ 的红边，且 $u,v$ 两点在蓝树上的距离不小于 $3$，则若红方到达其中某一点且蓝方下一步抓不住他，游戏就会进行无限轮。画图…

题意 题目链接 给定一棵树，每次询问给出一个点 $u$ 和深度 $d$，询问深度为 $d$ 的点中有多少个点祖先包含 $u$。 解析 考虑用一个时间戳，记录每一个点的入栈时间 $in_i$ 和出栈时间 $out_u$，发现每一个符合条件的点 $x$ 满足 $in_u \le in_x < out_u$。由此，用 vector 维护每一层所有点…

这篇文章实际上写成于母亲节，一直忘了发出，今日方想起。 我觉得，我母亲——或者我更习惯于称之为妈妈，约莫也不会看到这篇文章吧，但是无所谓了，这一切，仅仅是我于母亲节的独白而已。 我的妈妈，真真切切是我最想要感谢的人，感谢她的抚养，感谢她的温柔，更重要的是感谢她的支持。 一直以来，她都给了我充分的选择机会，因而我才得以自己决定自己的发展方向，得以去寻…