2022 LOJ 随机做题随笔——二月

Tag & Difficulty
Sol

难度纯粹个人评价。

02.01

3620

Tag & Difficulty Tag: observation | Difficulty: 2400
Sol codeplus 和 HDU 多校都出现过的原题 /fn 但是线性做法其实还是有点水平的。

先枚举绝对众数是谁,把非绝对众数改成 -1,绝对众数改成 1,那么需要计算的就是和大于 0 的区间数量。这容易通过前缀和然后扫一遍做到单次 \(O(n)\) 总复杂度 \(O(n^2)\),但不能接受。

注意到当元素个数很小的时候,前缀和构成的折线倾向于一直往下走,只在其中很少的有当前这个数的一部分有一段小波动。考虑利用这个性质进行优化。

不放假设当前扫到第 \(i\) 个元素,前缀和数组是 \(S\),\(0 \sim i\) 的前缀和最小值是 \(min\)。如果 \(S_{i+1} = min - 1\),那么 \(i+1\) 为右端点一定没有贡献,且紧跟在它后面的所有 \(-1\) 都一定没有贡献。这个时候可以直接不断往后找找到第一个 \(+1\) 的位置从那里开始算贡献。而 \(S_{i+1} \neq min + 1\) 时直接暴力计算贡献。假设这一部分可以做到单次 \(O(1)\)。考虑它的复杂度。假设 \(S_i = min, S_{i+1} \neq min+1\),且 \(j\) 是最靠前的位置满足 \(S_j = min+1\),如果不存在则设它是 \(n+1\)。则 \(i \sim j-1\) 里面至少有 \(\frac{j-i}{2}\) 个 +1,所以这中间暴力扫的复杂度均摊到每个 +1 上就是 \(O(+1\)元素个数\()\) 的,所有的合起来就是 \(O(n)\) 的。

维护上有一个稍微复杂的地方就是如何维护这个前缀和。一个暴力方法是维护一个桶表示每个数的出现次数然后每次加减 1 的时候用一个指针在桶上移动维护增量。直接将这个算法移植到上面这个 idea 上有一个问题:\(S_{i+1} = min - 1\) 的时候后面的一段 -1 需要在桶上打一片标记。这可以用一个前缀和来解决,也可以直接不在桶里维护 \(0 \sim min\) 的第一次 +1,也就是说桶里的所有元素实际上是真实值减 1,这样一段 1 的移动就不会对桶产生影响了。这样就做到了真正的 \(O(n)\)。

3622

Tag & Difficulty Tag: counting | Difficulty: 2000
Sol 容斥,枚举给出的 $m$ 条路径的一个子集强制它们全部同色,用并查集合并一下同色的边集,不同的边集之间没有限制所以方案数就是 $k$ 的同色边集数次方。
上一篇:jlh的童年


下一篇:虎年快乐之算法练习题22---动态规划“最少硬币问题”