大家的总结都写的好多啊
专题总结就不放在这里面了
只加一些杂题和考试题吧
JOI2017Final 准高速电车, JOIOI王国, 焚风现象
A. [USACO08JAN]电话线Telephone Lines
晚上有一场牛客的 NOIP CSP 模拟赛
暴力做法是枚举一个 \(W\) 然后暴力计算
发现这个 \(W\) 具有单调性
二分加前缀和优化即可
其实很早之前就写过了, 不过今天再做发现感悟还是蛮多的
思路其实比较清晰, 我们可以对于每一个点一步一步跳
然后似乎这种等效的可以一步一步跳的就可以转换为倍增
预处理一下倍增数组
然后每个询问稍微动动灵巧的脑瓜子想一想就行了
发现一定是先走快车, 再走准快车, 再走慢车
并且这是对于相邻两个快车站内的区间
那么处理一下这相邻两个快车站的区间, 每次取能增加最多的车站的区间转移, 再次计算即可
考虑到你取得一定是一个阶梯状的东西
那么靠近左下, 右下, 左上, 右上都有可能成为最优解
全局最小值肯定会出现在这其中至少一个里面
由于要求的是最大值最小
考虑二分与全局最小值的差 \(mid\)
我们假设全集最小值出现在这个阶梯状的鬼玩意里
令全局最小值为 \(mn\), 全局最大值为 \(mx\), 那么有
阶梯状中的最大值 \(\leq mn + mid\), 另外一块中最小值 \(\geq mx - mid + 1\)
然后阶梯状的能选就选, 并且不能超过上一行的
选完后 \(check\) 一下另外一块是否满足条件即可
没了
没什么好说的, 差分数组瞎搞一下即可
先看一下是否有 \(\leq k\) 或者是没有合法方案的情况
判断完后考虑二分, 二分一个 \(mid\) , 代表我们最后付钱的那条边的价值不超过 \(mid\)
那么其余 \(> mid\) 的边, 如果在 \(1 - n\) 的路径上出现了一次, 我们就要将其免费一次
最多能免费 \(k\) 条边, 且 \(\leq mid\) 的边不需要免费
所以 $\leq mid $ 的边对答案贡献为 \(0\), \(> mid\) 的边对答案贡献为一
最后看一下 \(1 - n\) 的最短路是否 \(\leq k\) 即可
两种思路, 数据结构暴搞和差分
这里用差分
最大值最小, 考虑二分
我们二分一个最短时间 \(mid\)
把所有 \(\leq mid\) 的路径不管他, 只看 \(>mid\) 的路径是否可以全部变为 \(\leq mid\)
那么我们选的免费的那一条边必须在所有 \(>mid\) 的边的公共路径上
差分一下, 选择最长的那一条就行了
然后, 要将所有路径的都满足条件, 即是将 \(> mid\) 中最大的那一条变成 $\leq mid $ 即可
判断一下, 没了
我用的是分层图+最大流, 这个应该很容易想到
就是先建出第一天的图, 如果能全到就停止
不然就再加一天上去
本来以为会MLE, 事实上并没有???
还有一种费用流的解法, 待我去看一看
思路比较清奇的一道题
或许是最近状态还可以, 这种东西居然能够只看一眼 LCA 就想到???
真是令人懵逼, 考试的时候脑子短路
平常做题的时候转的飞起
如果这种状态能延伸到考试中每一次的成绩都会好很多吧
我们发现将一个容器倒进一个容器可以看做把两个容器倒进一个新的容器里
想到了什么, 把两个并到一个上面去, 是不是并查集
每次新开一个点, 把两个容器所在的联通块的根接上去
然后对所有倒入操作处理完后发现是一个森林
那么两个点的 LCA 的深度就是他们的反应时间, 先反应的深度更深
深度一样的反应级别优先的优先反应
所以以 LCA 的深度为第一关键字, 反应优先级为第二关键字排序
扫一遍处理一下就好了
P. S. 由于并查集和树剖的数组名字弄混了搞得我调了好久, 坑爹
其实已经做过几遍了
题目不难, 不过是一道练习单调栈的好题
我们把序列重构, 最大的放第一个, 剩下的扯出来塞后面, 最后再把最大的放后面
规定一对高度不相同的, 大的对小的造成贡献, 高度相同的, 左边对右边造成贡献
这样就不会有重复和遗漏了
现在我们要求的是一个数左边, 右边第一个比他大的数, 和他与左边第一个比他大的数之间有几个和他一样的数
第一个单调栈维护
第二个用个以权值为下标的东西记一下上一个这个权值的位置
然后贡献就是一样的数加上左右两个, 设一样的数有 \(v\) 个, 则答案为 \(v + 2\)
但是第一个数和最后一个数事实上是同一个数, 所以当一个点左边为 \(1\), 右边为 \(n + 1\)时 \(ans\) 要减一
差不多就这样了, 好题
考试时为什么不想单调栈啊, 我是傻逼吧
原文：https://www.cnblogs.com/ztlztl/p/11799926.html