「Summary」2022-07-21 做题记录

自闭

2022-07-21 AtCoder Beginner Contest 254

$\mathbb{D \ Together \ Square}$

link
发现 $n \le 1e5$ ，但是 $n^2 \le 1e10$ ，显然不能枚举这个完全平方数，根据一个数论常用的技巧是枚举根号内的两个因子然后判乘积。这里可以枚举这个数的最大的一个为完全平方数的因子，有点绕，将它记为 $d(i)$ 。那么 $i \times j$ 为完全平方数的条件是 $\frac{i \times j}{d(i \times j)}$ 为完全平方数。
继续想，$d$ 是完全积性的，所以式子可以化成 $\frac{i}{d(i)} \times \frac{j}{d(j)}$ ，可以开一个桶统计 $\frac{i}{d(i)}$ 的出现次数，记为 $f(x)$ ，则每一个的贡献即为 $f(x)^2$ ，答案为 $\sum_{i = 1}^{n} f(i)^2$ 。

$\mathbb{E \ Small \ d \ and \ k}$

link
开局发现每个点的度数小于 $3$ ，想了一会，不会，再看一眼，看到了 $k \le 3$ ，算了一下，最远距离不超过 $3$ 的点大概只有三四十的样子，然后写了个 $bfs$ ，脑抽，第一次在清空时写错了，慢到飞起，结果罚了一发后才对。

$\mathbb{F \ Rectangle \ GCD}$

link
有点意思，但是线段树写挂了，没调出来。

先把答案的式子表示出来，为了方便，把每一个横行的 $\gcd$ 表示成 $f(x)$ , $f(x) = \gcd(a_x, a_x + b_i, a_x + b_{i + 1}, \dotsb, a_x + b_j)$ ，总的答案就是 $\gcd(f(i), f(i + 1), \dotsb, f(j))$ 。

要用到一个数论知识 $\gcd(a_1, a_2, a_3, \dotsb, a_n) = \gcd(a_1, a_2 - a_1, a_3 - a_2, \dotsb, a_n - a_{n - 1})$ 。

把 $f(x)$ 重新表示为 $f(x) = \gcd(a_x, b_i, b_{i + 1} - b_i, \dotsb, b_j - b_{j - 1})$ ，把后面那一块单独拎出来，记为 $g = \gcd(b_i, b_{i + 1} - b_i, \dotsb, b_j - b_{j - 1})$ ，因为是个矩形，所以每一个横行的 $g$ 的是一样的，答案就重新表示成了 $Ans = \gcd(g, a_x, a_{x + 1}, \dotsb, a_y)$ 。
这个就变成了一条直线上的连续的关系，可以直接用两个线段树维护。
翻了一下正解，看到 Atcoder 的库里面自带一个 seg ，甚至可以直接维护 gcd ，简直是打网赛的标配，但我不会。。。

$\mathbb{G \ Elevators}$

link
和 $JOI$ 中的飞天鼠那道题比较像。但是更恶心，不能直接跑最短路，并且是多组询问。
一开始想了很久只能推一部分，思路是在竖直距离上不走回头路，考虑最小化水平距离上的移动，似乎可以考虑一个 $dp_{i, j}$ 表示从第 $i$ 层走 $j$ 次，能够走到的最高楼层，如果直接转，复杂度是平方级别的，之后就不会做了。。。
翻了好几篇题解才看懂，考虑一个问题，如果在最开始后最终都需要换楼，那么答案还要加上 $2$ （mark），解决办法是，在一开始走的时候尽量的往高处走，不离开这栋楼，而在最后也尽量往上面走，不离开这栋楼。
这个转移要变成倍增转移，就是说，令 $dp_{i, j}$ 表示从第 $i$ 层楼走 $2^j$ 步能到达的最高楼层。
于是就变成统计这个路途中的不包含起点和终点的最小移动次数，在最后的答案里面额外加上 $2$ 。
恶心，为啥我看不懂 std 啊。
终于看懂了，记录一下大致的思路。
首先离散化，对于每一栋楼的电梯维护一个有序集合。之后处理倍增数组，初始化时要注意 $dp_{i, 0}$ 是对三个数取最大值，分别是 $dp_{i - 1, 0}$ ，表示从上一层转，$i$ ，表示就在这一层楼不动， $mx_i$ ，表示直接走到这部电梯的顶端。
最后统计答案时分为几步，首先处理开始时的电梯和结束时的电梯，一个小细节是，如果这两部电梯有相交，表示只需要在水平方向移动一次或是不动，判断标准是起点和终点是否在一栋楼。
否则需要至少两次水平方向上的移动，这个时候需要倍增往上跳。