定二分所谓的界+调整法：[AGC045B] 01 Unbalanced
定二分所谓的界+调整法：[AGC045B] 01 Unbalanced
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135125239
https://www.luogu.com.cn/problem/AT_agc045_b
考虑0为1，1为-1，然后就是使前缀和极差最小。（套路1）
一个常见思路是二分，也就是定上界M，使下界尽可能大，但此题不满足单调性，所以不能够二分。
我们考虑调整法。我们先让所有？为-1
然后求出当前max值为Z。则M的下界为Z。
如果一个？由-1变1，使后缀整体+2。如果满足后缀max小于等于Z，我们就可以使其调整为1。因此我们就有了一个贪心的思路。
显然上界为Z和Z+1都要考虑，Z+2呢？
我们调整后，上界+2，但下界最多+2，也就是极差并不会变小，没有意义，所以我们直接试Z和Z+1即可。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-11-24
【NOIP2021 方差】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15598937.html 题目链接 Part A 式子化简 首先题目要求的式子就是 n2n^2n2 乘上 1n∑i=1n(ai−aˉ)2\frac{1}{n}\sum_{i=1}^n(a_i-\bar a)^2n1∑i=1n(ai−aˉ)2，其中 aˉ=1n∑i=1nai\bar a=\frac{1}{n}\sum_{i=1}^n a_iaˉ=n1∑i=1nai。 我们把这三合在一起也就是： n2×1n∑i=1n(ai−1n∑j=1n...
2023-10-03
抓住普通情况变量猜结论：ARC136C
抓住普通情况变量猜结论：ARC136C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133525236 假如不是环，我们求的就是上升的量。那么我们可以先大胆猜一波，环形结果就是上升的量。 然而我们在非环的情况是在前面补了0的，我们这里不能补0，我们就只能对最大值取max 1234n=read(); for(i=0; i<n; ++i) a[i]=read(), m=max(m, a[i]); for(i=0; i<n; ++i) k+=max(...
2021-12-21
【USACO2021 Closest Cow Wins 】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15716487.html 题目 Farmer John owns a long farm along the highway that can be considered somewhat like a one-dimensional number line. Along the farm, there are KKK grassy patches (1≤K≤2⋅1051 \leq K \leq 2\cdot 10^51≤K≤2⋅105); t...
2024-01-01
反向贪心决定博弈+博弈论中条件改变人的决策满足单调性：1229A
反向贪心决定博弈+博弈论中条件改变人的决策满足单调性：1229A 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135329131 http://cplusoj.com/d/senior/p/SS231229A 结论： 人们倒着来，每个人去掉当前对自己最不利的 因此我们有了 O(n3)O(n^3)O(n3) 考虑当一个人变了后，每个人的决策必然满足单调性，因此就可以平方了 12start coding at 20:19passing at 21:18 123...
2023-09-30
贪心找性质+DP表示+矩阵表示+线段树维护：CF573D
贪心找性质+dp表示+矩阵表示+线段树维护：CF573D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133437456 比较套路的题目 首先肯定贪心一波，两个都排序后尽量相连。我一开始猜最多跨1，但其实最多跨2，考虑3个人的情况： 我们发现第3个人没了，所以可以出现跨2的情况 然后直接上dp，由 i−1,i−2,i−3i-1,i-2,i-3i−1,i−2,i−3 转移过来。 然后这显然可以拿矩阵表示。 然后显然可以拿线段树维护。 后面三部分都是比较套路...
2021-11-18
【P2352 队爷的新书】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15574898.html 题目链接 可以发现，我们并不需要对所有节点进行枚举，我们只需要对所有端点甚至只需要枚举右端点即可。 因为如果这个不是端点，那么在它右边的点和它所在的区间个数相同，同时右边的点必然大于这个点，所以不用考虑这个点。 按照线段覆盖问题求出每个点的覆盖情况即可，也可以说是一维扫描线（雾 时间复杂度：O(nlogn)O(n\log n)O(nlogn)，主要是排序耗时间。 Code 12345678910111213141516...