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

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

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

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

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

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

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

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

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

和上一篇一起的。 怎么置换群还在追我。 根据排序不等式，显然答案最大是就是排列 对应位置的数完全相同的时候。我们其实并不在乎下标，只在乎对应的值。因此我们不妨固定 ，先将 排序，对应调整 序列的位置，将对 的操作转化到对 的操作上。 显然这个游戏就变成了两个人分别选择一对 中的元素并交换。由于你需要点积增加，因此逆序对必须减少，所以游戏不可能永远进行。不妨把 看作一个置换，恒同变换是