AGC003

A Wanna go back home

判一下 S,NW,E 是否同时存在或者同时不存在即可。

B Simplified mahjong

考虑一种贪心,从 $1$ 到 $n$ 逐个操作,我们假定已经把 $1\sim n-1$ 给操作完了,并且 $1\sim n-1$ 的位置如果剩余奇数就会留下 $1$ 。对于 $n$ 这个位置,可以贪心一下,尽量和前面的剩下的那个先配对。如果这个位置是奇数,那么配对了必然是优秀的。否则,如果这个位置是偶数,那么这个位置本身就变成了奇数,只能往后操作,这里相当于把一个 $1$ 往后挪动了一位,感性认知一下这样贪心是对的。

C BBuBBBlesort

翻转三个位置本质上就是隔开中间进行交换。不难发现这样操作后不会改变奇偶性。

所以可以把奇数偶数位置分别拿出来,我们肯定可以通过二操作实现内部的排序。

所以现在只需要把某个数所处的位置和它应当去的位置的奇偶性弄成相同的。这个可以通过每次进行一操作来归位两个数。

不难发现不满足的一定是偶数个数,于是它除以 $2$ 就是操作个数。

D Anticube

这个数据范围不太能分解质因数。

于是考虑枚举 $\sqrt[3]{A_i}$ 内得质因子,于是我们可以把每个数分解成质数次幂不超过 $3$ ,高于 $3$ 直接 $\bmod 3$ 即可。这样操作后,不难发现每个 $A_i$ 对应着唯一一种数,也就是每个次幂取反后的数,它们俩乘起来会得到一个立方数。于是一个显然的思路就是,对于每个数求出它对应的数,然后看这俩数哪个出现的次数大,拿出现的多的。

但是这有一个问题,我们怎么求出在 $\sqrt[3]{x}$ 到 $\sqrt x$ 之间的质因子以及次数呢?

如果我们把一个数的所有不到 $\sqrt[3]{x}$ 的质因子全部除去,那么剩下的这个数一定长成 $pq,p^2,p$ 这三种形式之一。如果这个数不到 $10^5$ ,显然这个数不可能是 $p^2,pq$ 的形式,因为如果这样必然存在不到 $\sqrt[3]{x}$ 的质因子。所以我们直接给它的对应数乘上 $p^2$ 即可。

剩下的数大于了 $10^5$ 考虑如果剩下的是 $p$ ,那么明显,不可能有一个数和这个数对应。因为如果存在一个对应的数,那么这个数至少有 $p^2$ 这个因子,但是它已经爆掉 $10^{10}$ 了。

如果剩下的是 $pq$ ,那么对应数至少有 $p^2q^2$ ,它又爆掉 $10^{10}$ 了。

也就是说我们只需要判一下剩下的数是否为一个平方数,如果是,我们就给对应数乘上 $\sqrt c$ 即可。

复杂度 $O(n\sqrt[3]{A_i} + n\log n)$ 。

E Sequential operations on Sequence

不难发现如果下一步操作直接砍掉了之前的某个更长的操作,那个更长的操作就废掉了。

也就是说我们拿个栈维护一下操作序列,得到的操作序列中长度是单调递增的。也就是说只有往后插入的操作了。

考虑往后插入,如果插入的长度为 $A_i$ ,上一次插入的长度是 $A_{i-1}$ ,于是我们相当于是先进行 $\lfloor \frac{A_i}{A_{i-1}} \rfloor$ 次复读操作,然后将之前的 $A_{i} \bmod A_{i-1}$ 的前缀给放到后面。

看到取模操作可以考虑连续取模后每次折半。于是我们找到之前的第一个位置,满足 $A_j < A_i \bmod A_{i-1}$ 然后复读这个 $A_{j}$ ,再在前面找到第一个不到 $A_{i} \bmod A_{i-1} \bmod A_{j}$ 的 $\dots$ 递归即可。如果找不到这样的 $j$ 了,那么当前的长度必然不到 $n$ (因为开始长度就是 $n$ ),于是直接对一段 $1\sim n$ 的前缀进行加 $1$ 操作即可。对每个长度记录一下它被复读了多少次,再维护一个差分数组即可算答案。最后给差分数组加上第一个数字具体被复读了多少次。

每次二分找到这个位置,只会找 $\log n$ 次,复杂度 $O(n\log^2 n)$ 。

F Fraction of Fractal

开始各种看错了题意。。大概在于,黑色点开始是一个联通块,而且每次是把初始图放进新图里面。。

考虑,如果有一列最上方和最下方都黑色的,同时有一列左方右方都是黑色的,那么这个图整完后所有黑色点必然再一个联通块。(这个蛮显然的吧)

否则,如果上下,左右都不存在,那么答案显然是最后的基础块个数。(这个也蛮显然的,因为块间无法构成连通块)

否则,现在只存在只有上下有或者只有左右有的情况了。

如果只有左右有联通的条(就是样例 $1$ 的情况)。也就是说两个基础块如果左右拼接起来,就会变成一个连通块。那么对于 $k-1$ 阶的连通块,如果我们把基础块放进去,那么得到的东西的连通块个数就是黑色点的个数减去左右相邻的黑色点对数(因为每有一个这样的对就会导致黑色点连通块少一)。

于是我们维护一下当前块内的黑色点个数以及相邻黑色点个数即可。但是在操作的过程中需要考虑相邻两块间新增的相邻黑色点对数量。这个每次会正好翻基础块的最左端和最右端相同的位置数量倍,非常容易递推。而黑色点的数量也是很容易递推的。把递推写出来,设 $g(n)$ 表示 $n$ 维情况下相邻的黑色点的个数, $f(n)$ 表示 $n$ 维情况下最左端最右端相同的黑色位置数, $t(n)$ 表示 $n$ 维的黑色点的个数,于是就有

其中 $c$ 是初始的黑色点数量, $b$ 是初始的左右两端相同的数量,$a$ 是初始相邻的黑色的数量。

这个递推明显可以矩阵优化。于是就做完了。具体大概是

所以就是

中的 $0,0$ 减去 $0,1$ 即可。

复杂度 $O(HW + 2^3\log k)$

文章作者: yijan
文章链接: https://yijan.co/2020/11/18/agc003/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog