5月记录

76.CF1967 Codeforces Round 942 (Div. 1)

CF1967A

CF1967B1

\[b\times \gcd(a,b)|a+b \to qi^2|(p+q)i \to qi|(p+q)\to q|p \to b|a \]

反过来也能推到。

CF1967B2

\[a+b|b\times \gcd(a,b) \to (p+q)i|qi^2\to (p+q)|qi \to (p+q)|i \]

枚举 \(p,q\)，因为 \(p<i,pi< n\)，所以 \(p^2< \sqrt n\)，\(q\) 同理。

容易做。

CF1967C

一个树状数组的结构。

相当于 \(k\) 次前缀和下的组合系数。

用树状数组模拟求出 \(a_1\cdots a_{i-1}\)，乘上对应系数可以求出 \(a_i\)。

CF1967D

CF1967E1

经典双直线 \(\mathcal O(n\sqrt n)\)。

77.CF1965

78.CF1969

CF1969E

记录每个点上的数前一个出现和后一个出现的位置。

合法区间是 \(n\) 个二维矩阵。

扫描线求出 \(l_i\) 表示以 \(i\) 为右端点，最大的不合法左端点。

按照 \(l_i\) 排序，最大的 \(l_i\) 一定要修改（必要性），记已经修改过的 \(\min(l_i)\) 为 \(mn\)，若之后的 \(l_i\)，有 \(i\ge mn\)，则跳过，一定最优。

79.CF335E

考虑知道 \(B\) 求 \(A\)。

对于一个高度为 \(i\) 的楼房，概率为 \(\frac{1}{2^i}\)，高度 \(\ge i\) 的概率为 \(\frac{1}{2^{i-1}}\)，小于的概率即为 \(1-\frac{1}{2^{i-1}}\)。

考虑从一栋楼的第 \(i\) 层出发的通道的期望长度（除去最左点），则有：

\[p\sum_{k=0}^{+\infty}(1-p)^k(k+1)=\frac{1}{p}=2^{i-1} \]

得到对于 \(B\) 的贡献也是 \(2^{i-1}\)，所以 \(A=B\)。

注意，这里只能推出 \(B\) 走第 \(i\) 层的通道对 \(A\) 的贡献。

再考虑知 \(A\) 求 \(B\)。

这里就不同了，因为 \(A\) 对每一层不同的分配数量对 \(B\) 的贡献都有一个不同系数。

考虑从低往上考虑，不断将最大值限制提高。

设当前高度为 \(x\)，长度为 \(j\)，则有：

\[(n-j)P(\ge x)^2P(<x)^{j-1}(2^{i-1}-2^{i-2}(1+\sum_{k=0}^{j-1}\frac{k\cdot P(=x)^k}{P(<x)^k})) \]

再加上高度为 \(1\) 的 \(n\)。

时间复杂度 \(\mathcal O(nm)\)，好像可以矩阵优化。