原题链接 INFO 题意简述 有 棵树在一条直线上，每颗树高都为 。每棵树倒下后会带倒同方向距离小于 的树。每次随机从左右两颗树中选择一个，被砍倒的树有 的概率向左倒下， 的概率向右倒下。求最后树覆盖的期望。 不难发现任意时刻剩下来的树都是一个区间。这时候就可以从区间 dp 的角度去考虑。 我们不妨设 表示当前剩下区间 的树，在 区间内

我们给每一杯可乐先乘上 让其变成整数。 我们希望构造 ，并且要最小化 。 特判 的情况。考虑把 乘到右边去，得到 移项得到 我们另 表示这个 。我们希望用最小的 让 到达 。我们每选择一个物品，就会让 增加 。 我们对于每个 建出点来，对于每个 ，从 向 连边。我们实际上要找出原图的一个最小环。对于每个 可达的点作为源点跑多源 BFS 即可。 对于任意一组可行解，我们可以

紧急学习矩阵树定理。 矩阵树定理 矩阵树定理讲的是以下内容： 对于图 定义度数矩阵为 邻接矩阵为 定义拉普拉斯矩阵 。 求出将拉普拉斯矩阵去掉一行一列的矩阵 的行列式就是原图的生成树个数。 酷炫算术魔法！ 但是为什么？ 实际上就是一个容斥原理。 不妨考虑行列式的展开式： 来看看这个式子到底有什么组合意义。 拉普拉斯矩阵的样子就是，对角线上是点的度数，剩下的点中两点之间有边时为 ，否则

出题人以为自己出了神仙 dp 题然后被矩阵树定理杀穿了。提交记录全是矩阵树定理做法。无敌了。 为了体谅出题人，本篇题解来说说 dp 做法（绝对不是因为我不会矩阵树定理！）。 感觉是被低估的题目啊。 下文所说的 均指原题的 ，也就是每次加入点后，新加入的点和原先的连边的点形成的团的大小。 首先需要考虑树的性质。树的性质是有 条边的联通的无环的图。 你发现肯定是要对某种满足条件的加边序列进行计数，

我不会啊。 首先观察一下题目描述。 “采购方式包含了她经过的结点的次序，以及她在每条路上买不买材料，但不计她在哪个商店买了什么”。 发现等价于满足“进去买东西的点的并集恰好等于全集”的方案个数。 显然直接求需要一个状压，并不是很优秀。 但是我们发现，“进去买东西的点的并集等于某个集合的子集”的答案是好求的，你只需要只在是子集的边上买东西即可，其它边只通过。 不妨另 表示走了 步，目前在点

题目相当于要求放置磁铁的方案数，使得相邻两个磁铁的间隔不小于 。 我会状压！用 记录每个磁铁是否放过，从左往右计算。然而这个题目 ，状压并不足以通过。 我们发现状压的问题在于我们知道放了哪些磁铁防止重复放置。我们可以考虑将磁铁按照一定顺序放置，但是这样就不能从左到右转移了，因为磁铁可能是乱序的。 不妨将磁铁按照从大到小排序，这样我们只需要在放下磁铁的时候考虑限制即可。此时在位置 放下一个 的

▶INFO 题意简述 给定一个 个点 条边的图，每个边分为黑边和白边，构造一组黑边个数等于白边个数的生成树或报告无解。 容易发现如果 是偶数，那么 就是奇数不可能平均分，此时应该报告无解。 我们给黑色边定价 白色边定价 。 我们希望求一颗

又是计数，吓哭了。 计数题太困难。 考虑加入之后的双端队列里有什么性质。由于你是按照从小到大的顺序加入的，因此呈现一个两边大中间小的 V 字形。 由于题目要求第 个数是 ，那么肯定 的左侧和右侧至少有一侧取空了。由于我们是对最终序列计数，因此我们不妨钦定取空的是左边的。因此这个问题其实等价于将序列的前 个元素分成两个递减的子序列，我们将两个子序列分别称作左侧子序列和右侧的子序列，代表其中的元

这里本来应该有另外一个 DP 题的题解的。但是牛客这些题目题解更好写。 A 赛时提示说只看灰字会更容易通过。那我们分析一下灰色字体。 之前分析了给出的 galgame 链接的代码，发现之和最后一个选项有用，但是赛时感觉没啥用。 “你应该多和我聊天”和“偶尔给我送送礼物”说明前面 的个数应该大于 的个数。“然后在那个特殊节日里跟我有特殊互动”猜测是倒数第二天，因此倒数第二天进行 ，“最后在我内心

怎么都在写根号做法？ 莫队做法有点过于无脑了。 另外突然发现我之前因为和别人朝 inline 有没有用的时候交了一发这题的代码测了一下，结论是 inline 似乎确实有用。然后我以为自己做过这个题目直接交了。 讲下我的 做法。 首先判断是否有解是容易的，直接扫描线即可。但是我们要输出一个数！怎么办？ 考虑一个数的可行区间。显然满足以下两个条件。 其中 表示当前这个数上一次出现的时候， 表示下