洛谷2178 [NOI2015]品酒大会
Luogu [LOJ](https://loj.ac/problem/2133） 分析 如果两个位置是 $r$ 相似的，则它们也是 $k\in[0,r)$ 相似的。我们可以只求出 LCP 为 $r$ 时的答案，再求一遍后缀和/后缀 max 即可得到答案。 考虑两个位置的 LCP 实际上是一段区间的 $height$ 的最小值。我们可以将 $height_i$ 从大到小排序，每次加入一个 $h...
Luogu [LOJ](https://loj.ac/problem/2133） 分析 如果两个位置是 $r$ 相似的，则它们也是 $k\in[0,r)$ 相似的。我们可以只求出 LCP 为 $r$ 时的答案，再求一遍后缀和/后缀 max 即可得到答案。 考虑两个位置的 LCP 实际上是一段区间的 $height$ 的最小值。我们可以将 $height_i$ 从大到小排序，每次加入一个 $h...
Luogu LOJ 分析 考虑求出卖了 $i$ 个蔬菜时的最大收益 $ans_i$。 容易想到，我们要先卖贵的菜，且要尽量靠后卖。 用一个堆维护所有还有存货的蔬菜，然后每次选一个收益最大的放在能放的最后的一天。 通过并查集维护每一天往前到哪一天才有没有用掉卖的额度即可求出这一天。 假设最多能卖 $cnt$ 个蔬菜，则前 $i$ 天的答案为 $ans_{\min\left\{cnt,m\tim...
BZOJ 分析 设 $sum_i$ 表示 $\sum_{j=1}^i[i\text{中有球}]$。显然我们只需要知道所有的 $sum_i$ 就可以知道每个杯子中是否有球了。 考虑到如果询问了 $[i,j]$，那么一旦知道 $sum_{i-1}$ 或 $sum_j$ 中的一个就可以知道另一个。 因此考虑这样一个模型：对于每个区间 $[i,j]$ ，在 $i-1$ 和 $j$ 间连一条边权为 $...
Luogu LOJ 分析 每个集合是否合法很容易判，先把这个东西预处理出来，记为 $chk_S$ 。 设 $f_S$ 表示集合 $S$ 的答案，那么有： 子集卷积即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // ==========...
CodeForces 分析 考虑一个性质：对于一个图的所有 MST，每种边权的边的数量都相等。 因此我们把每种边权的边拿出来单独考虑。我们把并查集恢复到加该种边以前的状态，然后判断这些边加进去会不会成环即可。 现在的问题在于怎么把并查集恢复回去。显然可以可持久化并查集，但是有更优美的做法：预处理出每条边在加该种边权的边时两端点所在的连通块即可。 代码 //It is made by M_se...