Contest Info

date: 2019.02.19 12:30-17:30

practice link

Solutions

A. Another LCA Problem

裸的LCT维护LCA。

B. Bar

题目大意：求 \(\sum_{n=1}^{+\infty}\frac{\ln n}{n^{s}}(s>1)\)。

题解：显然小范围暴力，大范围用积分估计。比较直接的想法是计算这个式子： \[ \sum_{n=1}^{N}\frac{\ln n}{n^{s}}+F(+\infty)-F(N) \] 其中 \(F\) 是 \(\frac{\ln n}{n^{s}}\) 的原函数。

但是观察图像可以发现，这样做会给大于 \(N\) 的每一项都带来一个较大的正误差。我们不妨把 \(F(N)\) 修改为 \(F(N+\delta)\)，这样正负误差可以部分抵消，调一下参可以通过本题。

C. Counting Palindromes

题目大意：给出一个字符串\(s\)，多次询问某个区间的回文子区间数量。

题解：先做一次manacher求出回文中心，然后推一下式子变成二维数点，扫描线或者主席树都可以，\(O(n\log{n})\).

I. Invasion

题目大意：给你 \(n\) 个不过原点的平面，问你从原点射一条射线至多能穿过多少平面。

题解：不妨把平面的法向量定向为指向原点。那么射线能穿过平面，等价于射线与原点成的夹角大于 \(\frac{\pi}{2}\)。

于是我们需要找一个半球，使得其中的法向量最多（不包括位于截面的法向量）。注意到我们如果把最优解适当地旋转一下，可以把一个法向量旋转到截面上。因此我们可以枚举一个法向量位于截面，将剩余法向量投影到该法向量代表的平面上，即转化为了一个平面问题。

时间复杂度 \(\mathcal{O}(n^{2}\log n)\)。

能用整数就 tm 用整数啊？？？

J. Jailing Rabbits

简单题。被卡几何了现场没过。

K. Key Arrays

裸的splay练习题。