怎么突然简单。

AGC003

A - Wanna go back home [Safe]

题面

给定一个长为 $n$ 的由 N,S,E,W 组成的字符串，分别表示向各个方向移动一段非零的你自定的距离，问有没有一种定距离的方案使得你最后回到原点

$1\le |S|\le1000$

题解

如果只包含 NS 中的一个或只包含 WE 中的一个那么显然不行，否则一定可以

B - Simplified mahjong [Safe]

题面

给定一个长为 $n$ 的整数序列 $a$，你有 $a_i$ 张写着 $i$ 的卡片，你可以把两张卡配对当且仅当他们数字的差 $\le1$，每张卡只能用一次，问最多能配多少对

$1\le n\le10^5$

题解

贪心，按 $1\sim n$ 的顺序考虑，我们考虑一种数的时候把它用到只剩 $0/1$ 张，如果在 $i$ 的时候我们发现 $i-1$ 有剩余，那么我们优先和 $i-1$ 配对，然后我们将 $i$ 内的卡片两两配对，多余的剩到之后考虑

复杂度 $O(n)$

C - BBuBBBlesort! [Safe]

题面

有一个长为 $n$ 的数组 $a$，元素两两不同，有两种操作，一种是交换 $a_i$ 与 $a_{i+1}$，一种是交换 $a_i$ 与 $a_{i+2}$，你要将这个数组排序，问最少用几次 1 操作

$1\le n\le10^5$

题解

考虑排序后 $\{a_1,a_3,\cdots\}$ 与 $\{a_2,a_4,\cdots\}$ 的集合一定都是确定的，而我们可以用 2 操作任意调整集合内部顺序

那么我们只要每次把错集合的元素交换就可以了

复杂度 $O(n\log n)$

D - Anticube [Safe/Euclid]

题面

给定 $n$ 个正整数 $a_i$，你要选出一个子集，使得其中任意两个数乘积不为完全立方数，求最多选出多少数

$1\le n\le10^5,1\le a_i\le10^{10}$

题解

相当于不能有两个数指数加起来模 $3$ 全为 $0$，那么我们可以把指数都模 $3$ 考虑，也就是暴力将所有包含立方因子的数都除掉，这一步是 $O(n\pi(10^{\frac{10}3}))$

这样对于每个数，一定有一个唯一的数使得它乘起来为完全立方数，考虑如何求出这个数

直接暴力枚举因子显然是不行的，考虑如果这个“互补”的数 $>10^{10}$ 再算出来就没有意义了，因此我们可以先把 $\le 10^{\frac{10}3}$ 的因子全都找一遍，求出这个因子的次数

然后考虑 $>10^{\frac{10}3}$ 的因子，那么一个数至多包含两个因子，可能的情况只有 $p^2,pq,p$，在这些情况中，$p^2$ 一定对应 $p$，剩下的数如果是 $\le10^5$ 的质数，那么对应的一定是 $p^2$，否则要么是 $pq$ 要么是一个 $>10^5$ 的质数，而这两种情况的“互补”数均超过了 $10^{10}$，不用考虑，这部分的复杂度只有 $O(n+\pi(10^5))$

复杂度 $O(n\pi(10^{\frac{10}3}))$

E - Sequential operation on Sequence [Safe]

题面

一开始有一个 $1\sim n$ 的序列，$q$ 次操作，每次给定一个 $k_i$，将该序列变为长度为 $k_i$，如果长度过多直接删除，长度不够循环补全，对每个 $i\in[1,n]$，求 $i$ 在最终序列里出现了多少次

$1\le n,q\le10^5,1\le k_i\le10^{18}$

题解

不难发现只有后缀最小值有用，我们把其他的都扔掉，那么操作序列的长度递增

我们倒着考虑，可以算出每个前缀当前在序列中循环出现的次数 $f_i$，一开始只有 $f_{k_q}$ 为 $1$

我们每次遇到 $f$ 不为 $0$ 的点 $f_x$，找到最大的 $j$ 使得 $k_j<x$，那么 $f_{x\%k_j}\leftarrow f_{x\% k_j}+f_x$，$f_{k_j}\leftarrow f_{k_j}+\lfloor\frac x{k_j}\rfloor f_x$

这样每个数扩展一次只会生成一个新下标，而一个数最多取模 $\log$ 次就会变成 $1$，因此总复杂度 $O(n\log^2n)$（如果用 map 实现的话）

F - Fraction of Fractal [Euclid]

题面

给定一个 $h\times w$ 的黑白矩形 $a$，定义 $0$ 阶分形是一个黑格，$i$ 阶分形是一个 $h^i\times w^i$ 的黑白矩形，我们将其划分为 $h\times w$ 的矩形区域，每个区域内，如果对应的 $a$ 中格子是黑格，就在这个区域内放一个 $i-1$ 阶分形，否则这个格子全白

问 $k$ 阶分形有多少个黑格，保证 $a$ 中黑色格子联通

$1\le h,w\le1000,k\le10^{18}$

题解

如果 $a$ 上下堆叠与左右堆叠均能联通，那么答案为 $1$

如果 $a$ 上下堆叠与左右堆叠均不能联通，那么答案为 $cnt^k$，其中 $cnt$ 为黑格个数

否则，我们假设上下堆叠的联通

我们令 $ans_i$ 表示 $i$ 阶分形的黑格数，$cyc_i$ 表示有多少列 $j$ 满足 $(1,j)$ 为黑格且 $(h^i,j)$ 为黑格

那么 $ans_i=cnt\times ans_{i-1}-cyc_{i-1}\times edge$，其中 $cnt$ 为黑格个数，$edge$ 为满足 $a_{i,j}=a_{i+1,j}$ 的 $(i,j)$ 个数

用矩阵快速幂可以做到 $O(\log k)$