3.28模拟题解

3.28 模拟题解

A. border

设 k-substring 的答案为 \(f(k)\)，则有 \(f(k)\le f(k+1)+2\)，因为 \(f(k+1)\) 至少都可以从 \(f(k)\) 继承而来。

那么考虑倒序枚举 \(k\) 并计算 \(f(k)\)，我们可以先将 \(f(k)\) 设置成 \(f(k+1)+2\)，再不停将 \(f(k)\) 减小直到其合法。

如果用哈希来判断两个字符串是否相等，则复杂度就是线性的，可以用均摊的思想证明。

这道题的总结是，碰到形如对字符串的所有同类型子串求答案的题，

就可以考虑充分利用所有已知信息，来从一个子串的答案推到另一个的答案。

B. Majority

首先注意到，一个区间最多存在一个绝对众数，故考虑枚举众数 \(x\)，

并记 \(b_i=[a_i=x]-[a_i\ne x]\)，则问题等价于算 \(b\) 中和大于 \(0\) 的区间个数。

记 \(c(x)\) 为序列中 \(x\) 的出现次数，则若以 \(O(c(x)\log n)\) 的复杂度算 \(x\) 的答案，则总复杂度就是 \(O(n\log n)\)。

具体的，对固定的 \(x\)，\(b\) 序列形如 \(O(c(x))\) 个连续段，每个连续段的开头是 \(1\)，其余都是 \(-1\)，

而维护一个连续段对答案的贡献，等价于区间修改与求二维前缀和，

这可以用差分转化成单点修改与求三维前缀和，用树状数组即可，

亦可转化为区间加等差数列区间求和，用线段树也能实现。总结是可以考虑维护变化量较小的量。