1862

这位大佬想出来的题解是真的牛，很强的逻辑推理能力。大佬博客为：https://blog.csdn.net/Muelsyse_/article/details/132385030?spm=1001.2014.3001.5501 ......

传送门 题解 因为有这个操作：将序列 \(a\) 加上 \(\{n, n - 1, \cdots, 1\}\)，考虑差分。 那么显然每次操作会将差分数组中的每个元素减去 \(1\)，如果差分数组中有 \(0\)，就会把 \(0\) 删除。 所以可以发现差分数组中剩下的一定是操作前的最大值。 由于操作 ......

题目链接 先不考虑修改操作。 直接模拟题目意思，可以发现最后留下的一定是最小的数字（因为相同的数每次会保留第一个）。我当时是顺着这个思路做的题目，现在想想反过来想好像会让问题变得更简单，即认为每次保留最后一个相同的数字。 那么现在每次留下的就是最后一个数字，显然每次操作会让这个数字加一，只需要考虑一 ......

洛谷 \(P1862\) 输油管道问题 如果只有一口井，那么显然是越近越好。如果有两口井，那么显然是有以下三种情况： 两口井都在主管道北边，那么这个时候的两个连接管道的长度和肯定大于两口井的\(Y\)坐标之差。 两口井都在主管道南边，和情况1是一样的 两口井，一个在主管道南边，一个在主管道北边，那么 ......

先注意到我们娱乐值损耗的多少只与最后一场电影有关系，所以假设最后一场电影看的下标为 $k$，那么最后就要减去 $d \times k$。 得出这个性质之后开个小根堆反悔贪心即可，首先 $a_i0$ 的，如果还没到 $m$ 场电影，我们就直接往里塞就可以，如果到了，我们就进行反悔操作，取出已选的贡献最 ......

## 思路 对于一个数组，每次操作会缩短排序后的数组的相邻两个数的差距，所以总共会执行 $k$ 次操作，其中，$k$ 为排序后的数组的相邻两个数的最大差距。 因为每次操作都会对最大数加 $1$，所以答案就是 $\text{数组中的最大数} + \text{排序后的数组的相邻两个数的最大差距}$。 因 ......

## 思路 假设总共耗时是 $s$ 秒，那么最多可以消灭的总生命值是 $s\times(w+f)$。 所以我们可以先求出所有怪物的生命值之和 $sum$，那么，至少需要时间 $t=\lfloor \frac{sum}{w+f} \rfloor$。 然后我们可以算出用这些时间最多可以用水魔法消灭的生命 ......

## 思路 题目要求 $m \le 2\times n$，而 $a_i$ 被取出来，只需要 $a_{i-1}\le a_i$ 即可，$a_i$ 被取，只关系于 $a_{i-1}$ 的大小。 因为第一个数是必取的，所以我们可以每两个数之间加一个数，以满足除了 $b_1$ 以外的其他 $b_i$ 会被取 ......

## 思路 原题中已经告诉了我们一种快速判断的方法，我们可以用这个方法来判断。 观察一下横着摆的方式，第一列的高度为 $a_i\ge 1$ 的个数，第二列的高度为 $a_i\ge 2$ 的个数 $\cdots$。 所以我们只需要逐列判断两种方式的高度是否一样就行了。 因为题目中给定了数组 $a$ 是 ......

## 思路 容易发现如果长度为 $x$ 的序列 $a$ 中每个数都不一样，那么无论数是什么，方案数总是一样，这种情况下方案数是 $\frac{x\times (x-1)}2$。 我们再对序列 $a$ 添加一些已经存在的数，如果添加了一个 $k$，则会方案数会加 $1$，也就是多了一个 $\{k,k\ ......

## 思路 假设我们选择了第 $p_1,p_2 \cdots p_x$ 场电影，那么减去的舒畅值是 $d\times(p_1+p_2-p_1+\cdots+p_x-p_{x-1})=d\times p_x$ 所以减去的舒畅值，只与最后一场电影的天数有关。 所以我们可以枚举最后一场电影在第几天，假设在 ......

## 思路 假设总共耗时是 $s$ 秒，那么最多可以消灭的总生命值是 $s\times(w+f)$。 所以我们可以先求出所有怪物的生命值之和 $sum$，那么，至少需要时间 $t=\lfloor \frac{sum}{w+f} \rfloor$。 然后我们可以算出用这些时间最多可以用水魔法消灭的生命 ......

bitset 优化可行性 DP。 注意到所有怪物需要魔法的和是一定的，问题转为判定是否能够恰好消耗 $i$ 点水魔法和 $sum-i$ 点火魔法，用 $f_i$ 表示这种分割方案是否可行，直接 dp 大概率会超时，使用 bitset 优化即可，最后根据 $f_i$ 统计答案。 代码： ```cpp ......