10-23 好题选讲总结

10-23 好题选讲总结

P13779 「o.OI R2」试机题 - 洛谷

注意特殊的数据范围。

\(K=2\) 就是黑白染色，然后检查黑白点数是否相等，\(K=3\) 可以 \(O(n^2)\) DP 设 \(f_{i,j,0/1}\) 表示子树内选了 \(j\) 个与 \(i\) 颜色相同的点，当前是否有相邻的同色点。

猜想 \(K\ge 4\) 一定有解。有构造，考虑三染色，然后把最多的颜色分进另外两种颜色里，容易发现最多只有长为三的路径。

P8861 线段 - 洛谷

如果没有修改，可以对 \([l_i,r_i)\) 区间加，然后查询时求区间和即可。用树状数组解决。

再考虑 \(l\le 10^5\le r\) 的部分分，那么修改就是把 \(l\) ckmax，把 \(r\) ckmin，每次把相同的位置并起来，再用一个堆维护最小的 \(l\)、最大的 \(r\)，可以做到均摊 \(O(n\log n)\)。

扩展这个做法。把线段挂在猫树上，考虑修改对 \([l0,r0]\) 取交，分为两种线段树上的区间：

• \([l0,r0]\) 不过 \(mid\)，考虑把所有有交的线段暴力下传到子区间中，这样每个线段只会下传 \(O(\log )\) 次，复杂度是对的。用堆维护线段中 \(l,r\) 的最值。
• \([l0,r0]\) 过 \(mid\)，类似上面部分分的做法，用堆维护 \(l,r\) 的最值，然后缩区间时把相同的位置并起来。

因此我们需要支持把一个集合并到另一个集合，并且还要维护每个点属于哪个集合，vector 启发式合并即可。而下传线段时需要把它从集合中删去，可以打标记。

实现时可以分别维护每个线段的左、右端点的集合编号，再用一个 std::map 用于求线段树区间上一点的集合编号。而集合合并时由于需要维护答案，因此还需要维护集合的 sz 大小，当删去线段时由于不能直接删，因此要将 sz 减一。

P10322 高洁（Purity） - 洛谷

记 \(d\) 的唯一分解为 \(\prod p_i^{t_i}\)。考虑哪些数能级小于等于 \(k\)，那么这些数的 \(k\) 次方的质因数幂次都不小于 \(d\) 的幂次，则这些数是如下式子的倍数：

\[f(k)=\prod p_i^{\lceil t_i/k \rceil} \]

于是能级大于等于 \(k(k>1)\) 的答案和为：

\[\sum _{i=1}^n i^{k+1} [f(k)\mid i][f(k-1)\nmid i] \]

\[f(k)^{k+1}\sum _{i=1}^ {n/f(k)} i^{k+1}[f(k-1)/f(k)\nmid i] \]

记 \(m=n/f(k)\)。

\[f(k)^{k+1}\Big(\sum _{i=1} ^m i^{k+1}-(\frac {f(k-1)}{f(k)})^{k+1}\sum _{i=1}^{\frac {m}{f(k-1)/f(k)}} i^{k+1} \Big) \]

当能级为 1 时，答案为

\[\sum _{i=1}^n i^2[d\mid i]=d^2\sum _{i=1}^{n/d} i^2 \]

拉插出 \(k\) 次方和即可。而能级为 \(0\) 的答案即所有不是 \(\prod p_i\) 的数，容易计算。

ABC242 Ex - Random Painting

等价于要求所有格子被染成黑色的最大时间的期望，考虑 min-max 容斥。枚举格子集合 \(S\) 计算 \(S\) 中有一个个格子被染色的最小时间的期望。即

\[E(\max(U))=\sum _{S\subseteq U} (-1)^{S+1} E(\min(S)) \]

假设有 \(cnt\) 个区间包含了 \(S\) 中至少一个格子，那么期望时间为 \(E=(1-\dfrac {cnt} {m})E+1\)，解得 \(E=\dfrac m {cnt}\)。

我们不能枚举 \(S\)，考虑 DP，设 \(f_{i,j}\) 为考虑到第 \(i\) 个格子被选，当前 \(cnt\) 等于 \(j\) 的所有带容斥系数的方案数和。先求出 \(s_{i,j}=\sum [l\in [i,j]][r\in [j,n]]\)，即 \(j\) 新增的区间数量，那么有转移：

\[f_{i,j}=-\sum _{0\le k<i} f_{k,j-s_{k+1,i}} \]

复杂度 \(O(n^3)\)。

Yet Another 伟大的数据结构问题 - 云斗学院

注意特殊的询问限制。

考虑随机异或哈希，那么 \(|S_v|-|S_u|\le 1\) 的情况是容易的。

考虑当 \(|S_v|-|S_u|=2\) 时，再维护和哈希，那么由于 \((a\oplus b)+2(a\cap b)= a+b\)，又由于 \((a\oplus b)\cap (a\cap b)=0\)，所以我们可以 check 这个式子。

正确性：把 \(a\oplus b,a\cap b\) 看成是随机的，那么不正确概率为 \((3/4)^{64}\)，大概是 \(10^{-8}\)，多跑几次就可以保证正确率。复杂度 \(O(n\log V)\)。

【UR #32】王之沉淀 - Universal Online Judge

考虑拆 01，把小于等于 \(k\) 的数变成 \(0\)，其余变成 \(1\)。将序列排序的时间即为所有 01 序列排序时间的最大值。

考虑在 01 序列上，一个 D 就是把最后一个 0 移到开头，一个 U 就是把第一个 1 移到末尾。

而一个 01 序列排序好的时间就是，使得每个分界点使得前面没有 1 或后面没有 0 的时间，对这个时间求最大值。而一个分界点的排序时间其实只跟 D 的个数与 U 的个数有关。则排一个 01 序列的时间为

\[\max _{i=1}^{n-1} \min(\lceil L1(i)/U\rceil,\lceil R0(i+1)/D\rceil) \]

其中 \(L1\) 为左侧 1 的个数，\(R0\) 为右侧 0 的个数。枚举 \(U,D\)，可以做到 \(O(n^2k)\)。

考虑一个 0 变成 1，L1 是不降的，R0 是不增的，因此取到 max 的位置在一定程度上是单调的。事实上可以维护最小的使得 \(\lfloor R0(i+1)/D\rfloor\le \lfloor L1(i)/U\rfloor\)，每次只取 \(i-1,i\) 位置的值，可以证明移动次数是 \(O(n)\) 的。复杂度 \(O(nk)\)。