洛谷5504 [JSOI2011]柠檬
Luogu分析感觉对斜率优化那一套更熟练了呢 qwq首先有一个显然的性质：每一段左右端的贝壳大小一定相同，而且这一段的 $s_0$ 一定是左右端贝壳的大小。因为如果不是这样的话，我们显然可以把端点单独成一段，然后答案会变大。设 $dp_i$ 表示前 $i$ 个贝壳最多可以得到多少柠檬，$c_i$ 表示 $i$ 是第几个 $a_i$ 大小的柠檬，容易得到状态转移方程因为要求的是最大值，所以维护...
标签 单调栈 下的文章
- 首页
- 单调栈
CF5E Bindian Signalizing
CodeforcesLuogu分析首先我们要破环为链。这里有一个技巧是选最高的位置 $maxpos$ 拆开，因为不会有一对点跨过最高点。然后处理出以下 $3$ 个东西：$L_i$：$i$ 左边第一个比它高的位置。$R_i$：$i$ 右边第一个比它高的位置。$cnt_i$：$(i,R_i)$ 内和 $i$ 一样高的数的个数。这 $3$ 个东西可以单调栈预处理出来。然后答案差不多是容易发现这样子...
Educational Codeforces Round 64 题解
这真是一场毒瘤的 $\mathrm{Edu}$ ... 不过为什么要unr，我应该能涨一点的比赛地址Inscribed Figures简单分类讨论。如果你 WA on #3 ，建议测一下 3 1 2 ，答案应该为 6 。代码Ugly Pairs？考虑一种奇妙的构造方案。把所有的奇数字符（a、c、e、…）拿出来，从小到大排序，形成字符串 $A$ 。把所有的偶数字符（b、d、f、…）拿出来，从小...
洛谷5300 [GXOI/GZOI2019]与或和
LuoguBZOJLOJ分析依次考虑每一位。对于 $\texttt{AND}$ ，显然只有全 $1$ 矩阵才有贡献；对于 $\texttt{OR}$ ，显然只有全 $0$ 矩阵才没有贡献。那么利用单调栈求出所有的全 $1$ 和全 $0$ 矩阵即可。至于具体怎么求：假设要求全 $1$ 矩阵，那么先求出每个元素往上能扩展的 $1$ 的个数，然后对于每一行扫一遍，拿单调栈维护一下就可以求出以每个...
洛谷3722 [HNOI2017]影魔
LuoguBZOJ分析对所有询问离线处理。首先用单调栈处理出每个点左右最近的比它大的数，分别记为 $L_i$ 和 $R_i$。显然 $[L_i,R_i]$ 有 $p_1$ 的贡献；左端点在 $[L_i+1,i-1]$ 之间，右端点在 $R_i$ 的区间有 $p_2$ 的贡献；左端点在 $L_i$ ，右端点在 $[i+1,R_i-1]$ 之间的的区间有 $p_2$ 的贡献。于是离线扫描：对于第...
洛谷3246 [HNOI2016]序列
LuoguBZOJ分析莫队。重点是两个状态怎么 $O(1)$ 的转移。先来考虑从 $[l+1,r]$ 转移到 $[l,r]$ 的情况。这样子会多出来 $[l,l],[l,l+1],...,[l,r]$ 这些区间，我们来考虑这些区间的答案。先找到这段区间的最小值 $p$ ，那么右端点在 $[p,r]$ 之间的区间的贡献都是 $a[p]$ 。还剩下右端点在 $[l,p-1]$ 的情况，把这一部分...
洛谷3194 [HNOI2008]水平可见直线
LuoguBZOJ分析首先，斜率相同的两条直线，纵截距大的在上面。所以先按斜率从小到大排序，对于斜率相同的只保留纵截距最大的。然后，维护一个单调栈，斜率单调递增。考虑一条新的直线满足什么条件才能覆盖掉栈顶。经过一番分析后发现，如果新的直线与$s[top-1]$的交点在$s[top]$的右边，那么$s[top]$会被覆盖掉。这里的$s$是栈。注意，一开始要把斜率最小的直线放进来。然后这题就做完...
POJ2559 Largest Rectangle in a Histogram
POJSPOJ分析毒瘤POJ，竟然不资瓷bits/stdc++.h。用单调栈维护一下矩形就行了。单调栈经典应用。要开long long。代码#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> ...
洛谷1950 长方形
Luogu分析我们只要处理出以每个点为右下角的矩形个数和即可。然后这个可以用单调栈搞。统计答案的方式有点奇怪。代码#include <bits/stdc++.h> #define re register typedef int mainint; #define int long long using namespace std; inline int read() { ...
洛谷1169 [ZJOI2007]棋盘制作
Luogu算法对于一个国际象棋棋盘：黑色格行列奇偶性相同，白色格不同白色格行列奇偶性相同，黑色格不同那么第一种情况设0，第二种情况设1，然后悬线法求最大子矩形即可。代码#include <bits/stdc++.h> #define re register typedef int mainint; #define int long long using namespace std...