23.12 营业日志-526互联

营业日志重新启动。

12.04 模拟赛

170，rk 9，A 没过，太丢脸了。

D 猜数

考虑朴素的 dp：\(f_{l, r} = \min\{ \max\{f_{l, k - 1}, f_{k + 1, r}\} + k \}\)。

固定 \(l, r\) 从左往右移 \(k\)，注意到 \(f_{k+1, r}\) 递减，\(f_{l, k-1}\) 递增，找那个临界点 \(k_0\)，则在其左边一定会选择 \(k_0\)，在其右边不确定。

题解告诉我们 \(r - k_0\) 是 \(\dfrac{n}{\log n}\) 级别的。

在其右边，式子是 \(f_{k+1, r}+k\)。注意到这与 \(l\) 无关，\(l\) 只会影响 \(k\) 的取值范围，并且这个限制是不升的。因此，对于所有 \(r\) 相等的 \(f\)，可以跑一次单调队列一起解决。

真的可以吗？但是状态数会爆。注意到只有 \(r - l \leq \dfrac{n}{\log n}\) 的状态是有用的，因此有用的状态数是 \(\dfrac{n^2}{\log n}\) 个。

空间会爆。注意到 \(r\) 离当前 \(r\) 的距离超过 \(\dfrac{n}{\log n}\) 的状态也是没用的，这样状态数就是 \(\dfrac{n^2}{\log^2 n}\) 了，这就能过了。

细节有点小多，总体还行。

#515569

12.05 模拟赛

打一半下去体测，100+0+0+0。

T2 神J上树

考虑单个操作，把 \(u \times dis(u, v)\) 看成在每条边上放一个 \(u\) 的权值，那么每次会走前缀 \(\min\)，在上面加入一个点相当于进行 cmin 操作，查询是链查，上吉司机就行了。

好像有更好写的做法，但我没多想。

#517772

G

摘抄计算小练习。

做一些变换让两条线段在坐标轴上，则需要求 \(\displaystyle \int_0^b \int_0^d \sqrt{x^2+y^2} \text{d}x\text{d}y\)。\(\newcommand\d[1] {\text{d}#1}\)

参考。

\[\begin{aligned} & \displaystyle \int_0^b \int_0^d \sqrt{x^2+y^2} \d{x}\d{y} \\ = & \int_0^b \int_{0}^{\frac{d}{b}x} \sqrt{x^2+y^2} \d{x}\d{y} + \int_0^b \int_{\frac{d}{b}x}^{d} \sqrt{x^2+y^2} \d{x}\d{y} \\ = & \int_0^{\arctan \frac{d}{b}} \int_{0}^{\frac{b}{\cos \theta}} r^2 \d{r} \d{\theta} \int_{\arctan \frac{d}{b}}^{\frac{\pi}{2}} \int_{0}^{\frac{d}{\sin \theta}} r^2 \d{r} \d{\theta} \\ = & \frac{b^3}{3} \int_0^{\arctan \frac{d}{b}} \frac{1}{\cos^3 \theta} \d{\theta} + \frac{d^3}{3} \int_{\arctan \frac{d}{b}}^{\frac{\pi}{2}} \frac{1}{\sin^3 \theta} \d{\theta} \\ = & \frac{b^3}{3} \int_0^{\arctan \frac{d}{b}} \frac{1}{\cos^3 \theta} \d{\theta} + \frac{d^3}{3} \int_{\arctan \frac{d}{b}}^{\frac{\pi}{2}} \frac{1}{\sin^3 \theta} \d{\theta} \\ \end{aligned} \]

极坐标代换：

图源：http://staff.ustc.edu.cn/~rui/ppt/math-analysis/chap10_2.html

中间一步拆分：注意到角度旋转时，顶点先抵住右边界、再抵住上边界，因此以对角线为界限拆分为两个三角形。

\(\displaystyle \int r \d{\theta} \d{r}\) 是许多阴影小块的面积，拼起来才是大圆（当然，这里是长方形。）

因为，本质上是分成许多小块，每块内近似取一样的答案。

\(r^2\) 来自于 \(\d{xy} \to r\d{r}\d{\theta}\)。

\[\begin{aligned} & \int \cos^{-3} x \text{d}x \\ = & \frac{\sin x}{2 \cos^2 x} + \frac{\ln |\sec x + \tan x|}{2} + C \\ \end{aligned} \]

（这个看来只能慢慢学）

\[\begin{aligned} & \frac{b^3}{3} \int_0^{\arctan \frac{d}{b}} \frac{1}{\cos^3 \theta} \d{\theta} + \frac{d^3}{3} \int_{\arctan \frac{d}{b}}^{\frac{\pi}{2}} \frac{1}{\sin^3 \theta} \d{\theta} \\ = & \frac{b^3}{3} \int_0^{\arctan \frac{d}{b}} \frac{1}{\cos^3 \theta} \d{\theta} + \frac{d^3}{3} \int_{0}^{\frac{\pi}{2} - \arctan \frac{d}{b}} \frac{1}{\cos^3 \theta} \d{\theta} \end{aligned} \]

把式子代进去就行了。

#518185