LuoguGym分析析合树模板题。如果两个点在析合树上的 LCA 是析点,那么答案就是这个析点对应的段;否则还要找到两个点所在的两棵子树,LCA 的儿子序列中这两个子树间的子序列才是答案。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =...
Codeforces分析考虑一个好区间实际上是 $\max-\min=r-l$。把所有询问按右端点排序,然后扫描线,则我们需要维护每个左端点到右端点的信息。考虑每个左端点维护 $(\max-\min)-(r-l)$,显然这个东西是 $\geq 0$ 的,所以我们只需要维护最小值出现次数即可,可以用线段树维护。在右移右端点时需要更新信息,用单调栈维护最值即可。但是我们要求的是所有区间,而不是右...
比赛地址Make a Rectangle求出每种边的数量,$\geq 4$ 的看成 $2$ 个,$\in[2,3]$ 的看成 $1$ 个,将最大值和次大值作为长和宽即可。代码Coloring Dominoes根据当前列和上一列的情况算出当前的方案数,用乘法原理乘起来即可。代码Don't Be a Subsequence设 $nxt_{i,j}$ 表示 $[i,n]$ 中最靠前的 $j$ 字符...
比赛地址Factors of Factorial直接把 $1\sim n$ 分解质因数即可。代码Walk and Teleport显然从左往右走是最优的,相邻两个选更小的方式即可。代码Grouping设 $dp_{i,j}$ 表示 $i$ 个人分成若干个人数 $\leq j$ 的组的方案数。转移时枚举人数 $=j$ 的组数 $k$,那么首先要在 $n-i+jk$ 个人中选出 $jk$ 个,然...
比赛地址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$ 即可。正确性不会...
LuoguLOJ分析因为 IP 地址可以看做长度为 $32$ 的二进制串,所以可以考虑用 Trie 树维护。考虑查询。可以发现一个 IP 地址的匹配最大明确度是单增的,因此求出链上修改时间的单调栈即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.co...
比赛地址STring和括号匹配是类似的,开一个栈记一下就好了。事实上只要记栈中的元素个数。代码Minimum Sum单调栈板子题。代码Tree Restoring首先找到 $d=\max\left\{a_i\right\}$,那么直径的长度为 $d$。设 $cnt_i$ 表示满足 $a_j=i$ 的 $j$ 的数量,分类讨论一下:若 $d$ 为奇数,则应有 考虑计算 $f_i$。容易发现一...
Luogu分析感觉对斜率优化那一套更熟练了呢 qwq首先有一个显然的性质:每一段左右端的贝壳大小一定相同,而且这一段的 $s_0$ 一定是左右端贝壳的大小。因为如果不是这样的话,我们显然可以把端点单独成一段,然后答案会变大。设 $dp_i$ 表示前 $i$ 个贝壳最多可以得到多少柠檬,$c_i$ 表示 $i$ 是第几个 $a_i$ 大小的柠檬,容易得到状态转移方程因为要求的是最大值,所以维护...
CodeforcesLuogu分析首先我们要破环为链。这里有一个技巧是选最高的位置 $maxpos$ 拆开,因为不会有一对点跨过最高点。然后处理出以下 $3$ 个东西:$L_i$:$i$ 左边第一个比它高的位置。$R_i$:$i$ 右边第一个比它高的位置。$cnt_i$:$(i,R_i)$ 内和 $i$ 一样高的数的个数。这 $3$ 个东西可以单调栈预处理出来。然后答案差不多是容易发现这样子...
这真是一场毒瘤的 $\mathrm{Edu}$ ... 不过为什么要unr,我应该能涨一点的比赛地址Inscribed Figures简单分类讨论。如果你 WA on #3 ,建议测一下 3 1 2 ,答案应该为 6 。代码Ugly Pairs?考虑一种奇妙的构造方案。把所有的奇数字符(a、c、e、…)拿出来,从小到大排序,形成字符串 $A$ 。把所有的偶数字符(b、d、f、…)拿出来,从小...