QOJ 板刷记录。

UnyieldingTrilobite · 2024-02-16 19:01:26 · 个人记录

新坑！看能坚持到啥时候不弃（

https://qoj.ac/problem/55。

题面：平面上给 n 个点，求两两欧几里得距离之和。

首先注意到 \int_0^\pi|\cos(x)|\,dx=2\int_0^\frac\pi2\cos(x)\,dx=2，同时 |\cos(x)|=|\cos(x+\pi)|，从而 \int_0^\pi|\cos(x+\theta)|\,dx=2。我们把中间这个东西展开再换个元，可知对任意实数 a,b 有 \sqrt{a^2+b^2}=\int_0^\pi|a\cos x-b\sin x|\,dx。记 f(x,a,b)=a\cos x-b\sin x，则 \sqrt{(a_1-a_2)^2+(b_1-b_2)^2}=\int_0^\pi|f(x,a_1,b_1)-f(x,a_2,b_2)|\,dx。不难发现前者加和就是我们要求的东西，把 0 到 \pi 均匀分成足够多段手动模拟一下积分就行，后面那个式子排个序拆贡献不难算。

复杂度略。

https://qoj.ac/problem/21。

题面：给定长度为 n 的序列，对每个 1\le k\le n 求出将该序列划分为 k 段并累和每段最大公约数，所得之和的最大值。

不妨原序列有序。

结论 1：至多一段所含不同元素多于一个。

证明：反证法，不妨有两段不同元素均多于一个。设第一段的最大值为 x 而第二段为 y\le x，则这两段的公约数之和不超过 \frac x2+\frac y2。现在我们令第一段只包含 x 而第二段接受原第一段的剩余部分，则两段的公约数和变为至少 x+1，更优。

以下称这样的段为特殊段。

结论 2：特殊段一定包含第一个数。

证明：反证法，若特殊段不包含第一个数（隐形要求其唯一），设其最大值为 x，最小值为 y，第一个数为 z，则这部分公约数之和不超过 z+x-y\le x，将最大数单独成段即可。

同理可知，特殊段的构成一定是一个前缀加上至多一种其他数，且这一种其他数不影响 \gcd。那么我们枚举每一种前缀 \gcd，不难发现没有直接贡献的数一定是前若干个“这个 \gcd 的倍数或重复的数”。直接算就行。

复杂度 O(n\log A)。