Atcoder 试题乱做 Part 1

难度标签：$\color{red}\texttt{[HARD]}$，$\color{blue}\texttt{[NORMAL]}$，$\color{green}\texttt{[EASY]}$。

[AGC002D] Stamp Rally

$\color{green}\texttt{[EASY]}$

直接整体二分，然后看连通块大小是不是 $\ge k$ 就行了。如果写类似 $\text{DFS}$ 的整体二分，由于有并查集的回滚操作，所以要按秩合并；但是如果写成 $\text{BFS}$ 版本的话，同层的修改就只有加边，不需要可回退。

另外一个做法是，首先观察到要求“最大边编号最小”，所以一定只会在编号的最小生成树上走。于是这就是一个经典的 $\text{kruskal}$ 重构树的问题。

[AGC002F] Leftmost Ball

$\color{green}\texttt{[EASY]}$

注意到将每种颜色的第一个球染白，那么一组合法的解一定满足：对于任意前缀，其中出现的颜色个数 $\le $ 白球个数。

如果逐个转移，首先复杂度极大可能是至少 $\mathcal{O}(n^2k)$ 级别，同时我们也不好确定每种颜色已经放了多少个。于是一个更有前途的想法是一次性放好同一种颜色的球。

不过这就会导致算重。具体来说，如果两个白球贴在一起，他们代表的颜色都被放在这两个白球的后面，这样两个白球就可能会导致重复计算。

于是，每次钦定当前要放在从左往右第一个空的位置，考虑当前位置是放白球，还是放一种颜色的球。因此设计 $\text{dp}$：设 $\text{dp}_{i,j}$ 表示已经放了 $i$ 个白球，已经有 $j$ 种颜色的球的位置被钦定好了。显然有 $j\le i$。转移显然可以做到 $\mathcal{O}(1)$。

因此最后复杂度是 $\mathcal{O}(n^2)$。

[AGC003E] Sequential operations on Sequence

$\color{green}\texttt{[EASY]}$

首先观察到如果 $q_i\ge q_{i+1}$，那么 $q_i$ 是一定没用的，因为他拓展出来的东西全都被 $q_{i+1}$ 吃掉了，剩下拓展出来的部分 $q_{i+1}$ 也能做到。于是，可以将 $\{q_n\}$ 转变为一个单调上升的序列。

如果依照题意模拟，可能不是特别好做。此时不妨考虑正难则反，从最后一个序列开始反向计算。具体来说，我们可以直接维护所有数组各自出现了多少次，然后会有一些前缀出现了更多次（不完整的循环）。每次只需要将序列缩短，然后重新计算贡献。

一个前缀在序列缩短的时候，其变化应该形如：被拆成若干整体加，和另外一个前缀（整除与取模）。注意到一个数被成功取模，其大小至少缩小一半，所以只需要拿 multiset 维护这样的前缀，然后每次只遍历能成功取模的部分（显然是一个后缀），这样复杂度就是 $\mathcal{O}(n\log n\log V)$。

[AGC003F] Fraction of Fractal

$\color{green}\texttt{[EASY]}$

第一步没想到。

首先将问题进行一些分类。本题最关键的是原图形联通的条件。首先，如果一个形状上下拼接能联通，且左右拼接也能联通，则说明不管如何，一定只有一个连通块。

如果上下、左右拼接都不连通，则显然分出来的图形接不起来，答案是 $c^{k-1}$，其中 $c$ 是 # 的个数。

接下来，这个问题就转化为只有左右拼接联通、或上下拼接联通，的情况了。不妨只讨论左右拼接的情况。

由于上下拼接怎样都不行，所以实际上每一行可以类似于认为是“独立的”。只需要看有多少种情况会使得左右接起来，导致连通块变少。

注意到如果在图形中出现 ##，那么就会出现两个连通块的合并。合并多少个连通块呢？这实际上就是上一个分形中，在一侧且能被拼接的连通块个数。

于是设 $c$ 是 # 的个数，$v$ 是 ## 的个数，$s$ 是“在一侧且能被拼接的 # 个数”。如果设当前连通块个数是 $k$，“在一侧且能被拼接的连通块个数”是 $m$，那么下一个连通块个数应该是：

$$ c\times k-m\times v $$

因为一个 ## 会导致 $m$ 次连通块的合并。同时，下一个图形的“在一侧且能被拼接的连通块个数”应该是：

$$ m\times s $$

因为一侧的能拼接的 # 会变成 $m$ 个“在一侧且能被拼接的连通块个数”。注意到这是一个矩阵的形式，直接矩阵快速幂就行了。

$\text{upd:}$ 还有一种做法，由于是平面四联通块，所以直接考虑平面图欧拉定理，现在把问题转变为数点、边、面数。点是好算的，边就是 ## 或竖起来，面就是四个 # 的矩形。这些都可以通过类似的讨论通过矩阵来维护。$\text{sto zxy orz}$！

[AGC001F] Wide Swap

$\color{red}\texttt{[HARD]}$

果然 AT 并不是我能做的东西/kx

题目中说，如果下标 $i,j$ 满足 $j-i\ge k$，且 $|p_i-p_j|=1$，则可以交换 $p_i,p_j$。这看起来十分奇怪，考虑给他换个形式。我们考虑他的逆排列 $\{q_n\}$，那么上面这句话就变成：

如果相邻元素 $q_{i},q_{i+1}$ 满足 $|q_{i+1}-q_i|\ge k$，则可以交换 $q_{i},q_{i+1}$。

邻项交换看起来是我们更熟悉的东西。做这样一步转化有什么用？注意到只有相邻两项差距 $\ge k$ 的时候，两个元素才能交换，因此，对于任意一对 $|q_x-q_y|<k$，他们的相对关系是无法发生变化的，也就是说他们在 $q$ 中出现的先后顺序是确定的。实际上，也可以证明只要满足上述条件，任意排列都是可以构造出来的。

把这句话翻译回 $p$ 中的限制，那他应该形如：

对于任意一对下标 $|i-j|<k$，那么 $p_i,p_j$ 的相对关系不会变化。

不妨假设 $p_i<p_j$，那么可以连一条 $i\to j$ 的边，表示 $i$ 的标号 $p_i$ 应该在 $j$ 的标号 $p_j$ 之前。

于是，我们一定会连出一个 $\text{DAG}$。设 $s_i$ 表示 $i$ 在某一个拓扑序中的编号，则 $\{s_n\}$ 是一组合法的解。则现在的目标转变为，找到该 $\text{DAG}$ 的一个拓扑序，使得 $s_1$ 尽量小，其次使得 $s_2$ 尽量小......

注意到这个问题实际上就是 [HNOI2015]菜肴制作，其答案是将 $\text{DAG}$ 反向后最大字典序的拓扑序。

则现在唯一的问题在于，该图的边数高达 $\mathcal{O}(nk)$ 级别，不能暴力连边。不过，这张图的形态是很有规律的，注意到一个点是入度为 $0$ 的，当且仅当他是他向左 $k-1$、向右 $k-1$ 个点里，没有入队过的点中，$p$ 值最大的点。这明显可以通过线段树来维护，从而做到 $\mathcal{O}(n\log n)$。

[AGC001D] Arrays and Palindrome

$\color{green}\texttt{[EASY]}$

考虑对于一个固定的 $a$，如何构造一个 $b$。可以将 $a$ 抽象成一些连边，如果一组限制中使得 $x,y$ 必须相等，那么在 $x,y$ 之间连边。那么现在的目标就变成，加入一个 $b$ 使得整张图变成一个连通块。

通过一些手玩，发现好像如果存在一个 $a_i(i\ne 1,i\ne m)$ 是奇数，那不管怎么样都连不好。因此我们猜测，只有奇数个数 $\le 2$ 的时候有解（可以放在首尾）。事实上是可以证明的，具体方法是计算 $a$ 贡献的边数，只有 $a,b$ 边数之和 $\ge n-1$ 才有可能将所有元素连起来。

那么，对于一个合法的 $a$，只需要类似于将 $a$ 进行 $1$ 的偏移，就足够满足条件，因为这样每次都能将当前这个“彩虹”与上一个连接，同时当前“彩虹”的最后一个位置留空，作为下一个“彩虹”的接入口。

[AGC005F] Many Easy Problems

$\color{green}\texttt{[EASY]}$

憨憨题。

考虑计算每个点对固定 $f(i)$ 的贡献。显然，一个点 $x$ 在连通块中，当且仅当他有至少两棵子树中有关键点。所以，对于固定的 $i$，一个点 $x$ 的贡献为：

$$ \binom{n}{i}-\sum_{s_j} \binom{s_j}{i} $$

其中 $s_j$ 是删去 $x$ 之后每个子树的大小。前面是可以快速计算的，关键是后面的部分。不妨记 $c_k$ 表示删去每个点后，大小为 $k$ 的子树有多少个，则后面这个就是：

$$ \sum_{k=1}^n c_k\times \binom{k}{i} $$

一开始以为本质不同的 k 只有根号个，然后直接冲了个暴力，于是 T 飞了

把组合数拆开，差卷积形式，直接卷一下就行了。

[AGC006C] Rabbit Exercise

$\color{green}\texttt{[EASY]}$

这就是命运？要是在 NOIP 之前做到这道题了我 tm 做 variance 的时间直接减 1h/px/px/px

注意到将 $x$ 关于 $y$ 对称后会到点 $2y-x$，考虑计算期望，则进行一次操作之后，$x_i$ 期望变成：

$$ \dfrac{1}{2}(2x_{i+1}-x_{i}+2x_{i-1}-x_{i})=x_{i+1}+x_{i-1}-x_i $$

这和 $\text{NOIP}$ 的 $\text{variance}$ 操作是一模一样的，直接转化为差分数组的 $\text{swap}$，然后就只需要对置换做 $k$ 次方就行了。

时间复杂度为 $\mathcal{O}(n)$。

[AGC006E] Rotate 3x3

$\color{blue}\texttt{[NORMAL]}$

首先注意到构成一列的元素是不会改变的，只有顺序会发生变化。因此，我们可以将 $3\times n$ 的矩形压缩为长度为 $n$ 的序列 $\{a_n\}$，其中第 $i$ 个元素有正负，表示这一列元素是正序还是倒序。

则一次操作相当于交换距离为 $2$ 的两个 $a_i$，然后将这两个 $a_i$ 及其中间的 $a_i$ $\times -1$。注意到操作可逆，所以现在只需要将给定序列变回 $a_i=i$。

显然，下标奇偶性不同的 $a_i$ 是不可能进行交换的，于是将其按照下标分为奇偶两种进行分类讨论。对于两个同奇偶的下标 $i,j$，在交换他们的时候，可以选择 $i,j$ 中间一个与他们奇偶不同的下标 $k$，使得 $k$ 的正负性也变化。具体方法是先交换 $i\to k-1$，$j\to k+1$，然后交换 $i,j$ 再做回去，只有 $i,j,k$ 的正负性可能变化。

这样就可以通过交换两次 $i,j$，做到不改变 $i,j$ 的正负性，同时改变 $i,j$ 中间 $2$ 个跟马腾奇偶性不同的位置的正负性。（自己推的时候只注意到能同时改变两个相邻偶数/奇数位置的正负性）

于是现在只需要先忽略正负，将奇偶全部还原，然后再考虑用上述操作修改正负性。

将奇偶换到正确的位置，需要的操作次数奇偶性不变（和逆序对奇偶性一致），于是例如把奇数改好后，对偶数的正负性的改变次数奇偶性是确定的，反之同理。

则只需要知道在位置移动完毕后，奇偶的负数个数是否都是偶数就行了，因为这样就能通过上述操作将其全部变为正数。特殊的一点在于，如果 $1$ 移动之后变成负数，是不可能通过上述操作变正的，不过可以通过一些简单的操作将 $3$ 的正负性和 $1$ 交换，这都是一些细节。

所以只需要对奇数、偶数下标分别计算逆序对奇偶性即可。时间复杂度 $\mathcal{O}(n)$。太懒了所以写的带 log

[AGC005D] ~K Perm Counting

$\color{green}\texttt{[EASY]}$

显然考虑容斥，设 $f_i$ 表示至少 $i$ 个位置不满足的方案数，则最后答案是：

$$ \sum_{i=0}^n f_i\times (-1)^i $$

一个位置不满足条件，则他只有至多两种取值，这样会构成若干条链，其中“取值”与“下标”在链上交替出现，每次只需要从链上选取不相邻的若干条边就可以表示一种有若干个位置不满足的方案（相邻则说明一个下标出现两个取值/一个取值在两个下标出现），这个方案数明显是一个组合数。

由于数据范围很小，所以暴力做卷积就好了，记得剩下的部分要乘上阶乘。时间复杂度 $\mathcal{O}(n^2)$。