CF997E Good Subsegments
Codeforces分析考虑一个好区间实际上是 $\max-\min=r-l$。把所有询问按右端点排序，然后扫描线，则我们需要维护每个左端点到右端点的信息。考虑每个左端点维护 $(\max-\min)-(r-l)$，显然这个东西是 $\geq 0$ 的，所以我们只需要维护最小值出现次数即可，可以用线段树维护。在右移右端点时需要更新信息，用单调栈维护最值即可。但是我们要求的是所有区间，而不是右...
标签 单调栈 下的文章
- 首页
- 单调栈
AtCoder Regular Contest 081 简要题解
比赛地址Make a Rectangle求出每种边的数量，$\geq 4$ 的看成 $2$ 个，$\in[2,3]$ 的看成 $1$ 个，将最大值和次大值作为长和宽即可。代码Coloring Dominoes根据当前列和上一列的情况算出当前的方案数，用乘法原理乘起来即可。代码Don't Be a Subsequence设 $nxt_{i,j}$ 表示 $[i,n]$ 中最靠前的 $j$ 字符...
AtCoder Regular Contest 067 简要题解
比赛地址Factors of Factorial直接把 $1\sim n$ 分解质因数即可。代码Walk and Teleport显然从左往右走是最优的，相邻两个选更小的方式即可。代码Grouping设 $dp_{i,j}$ 表示 $i$ 个人分成若干个人数 $\leq j$ 的组的方案数。转移时枚举人数 $=j$ 的组数 $k$，那么首先要在 $n-i+jk$ 个人中选出 $jk$ 个，然...
AtCoder Regular Contest 063 简要题解
比赛地址1D Reversi按题意模拟即可。代码An Invisible Hand设 $p_i$ 为 $[1,i-1]$ 中最小的数，那么最大收益显然为 $\max_{i=2}^n\{a_i-p_i\}$。因为 $a_i$ 互不相同，所以我们只要统计有多少个最大值即可。代码Integers on a Tree每次找到已经确定的最小的位置，然后把周围未确定的数设为它加 $1$ 即可。正确性不会...
洛谷5768 [CQOI2016]路由表
LuoguLOJ分析因为 IP 地址可以看做长度为 $32$ 的二进制串，所以可以考虑用 Trie 树维护。考虑查询。可以发现一个 IP 地址的匹配最大明确度是单增的，因此求出链上修改时间的单调栈即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.co...
AtCoder Grand Contest 005 简要题解
比赛地址STring和括号匹配是类似的，开一个栈记一下就好了。事实上只要记栈中的元素个数。代码Minimum Sum单调栈板子题。代码Tree Restoring首先找到 $d=\max\left\{a_i\right\}$，那么直径的长度为 $d$。设 $cnt_i$ 表示满足 $a_j=i$ 的 $j$ 的数量，分类讨论一下：若 $d$ 为奇数，则应有 考虑计算 $f_i$。容易发现一...
洛谷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$ 的个数，然后对于每一行扫一遍，拿单调栈维护一下就可以求出以每个...