前言：

点此返回 GJ Round 目录

博客园可能食用更佳

Round 22 (11.4)

唯一一次快速补完了题

A

AT_arc077_a [ABC066C] pushpush

不懂这原题标号咋这么奇怪

给你一个序列 $a_1\dots a_n$,按照如下规则构造新序列：

• 将 $a_i$ 插入序列末尾
• 将整个序列反转

模拟 / 打表找规律：

• 当 $n$ 为奇数时，答案为 $a_n{a}_{n-2}\dots a_3{a}_1{a}_2{a}_4\dots a_{n-3}{a}_{n-1}$
• 当 $n$ 为偶数时，答案为 $a_n{a}_{n-2}\dots a_4{a}_2{a}_1{a}_3\dots a_{n-3}{a}_{n-1}$

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

B

初始给定 $n$ 个点 $(x_i,y_i)$，给两个点 $i,j(i\ne j)$ 连边的代价为 $|x_i-x_j{|}^3+|y_i-y_j{|}^3$，$q$ 次询问，每次加入一条新边，求每次将所有点连通所花费的最小代价

对原图跑 prim 求最小生成树，保留 $n-1$ 条边，再与新加入的 $q$ 条边跑 $q$ 次 kruskal，时间复杂度为 $\mathcal{O}(n^2+qm\log n+m\log m)$，其中 $m=n-1+q,\log n$ 为并查集的时间复杂度，若是并查集继续使用了启发式合并 / 按秩合并可以优化至 $\mathcal{O}(n^2+qm\alpha (n)+m\log m)$，其中，$\alpha (n)$ 为反阿克曼函数

实则还可以不跑 q 次 kruskal，直接 dfs 找环删除环上最大边边即可，时间复杂度为 $\mathcal{O}(n^2+qn)$

C

给你两个长度为 $n$ 的序列 $a,b$，保证 $\forall i,j\in [1,n]\cap \mathbb{Z},i\ne j$，都有 $a_i\ne a_j,b_i\ne b_j$，定义他们的距离为 ${\sum }_{i=1}^n(a_i-b_i{)}^2$，求距离的最小值，答案对 $998244353$ 取模，并求出最小化距离时所需要交换的次数

对于问题一，显然将 $a$ 序列中的第 $k$ 大与 $b$ 序列中的第 $k$ 大排在一起即可，易证

第二问直接 for 模拟一下每个数是否已到对应位置，总时间复杂度为 $\mathcal{O}(n\log n)$

D

魔法阵是一个任意大小的方阵，满足如下性质：

1. 设 $(i,j)$ 有 $a_{i,j}$ 个魔法石，则有 $a_{i,j}\ge m$
2. 设魔法阵大小为 $k$，任意从魔法阵中选出 $k$ 个格子，满足任意两个格子不在同一行也不在同一列，那么选出的 $k$ 个格子的石子数之和是相同的
3. 魔法阵中对角线石子数之和不能超过 $n$

多测，给定 $n,m$，求方案数，答案对 $998244353$ 取模

容易发现，$a_{i,j}=x_i+y_j$ 是一个合法的方阵

钦定 $\min (x_i)=0$，则方阵与数列之间一一对应，此时 $a_{i_j}\ge m$ 等价于 $\min (y_i)\ge m$

不妨将所有的 $y_i$ 减去 $m$，使得问题转化成至多 $(n-km)$ 个石子放入 $2k$ 个格子，且前 $k$ 个格子至少有 $1$ 个没有的方案数，容斥后得：

$$ans=\left(\genfrac{}{}{0ex}{}{n-km+2k}{2k}\right)-\left(\genfrac{}{}{0ex}{}{n-km+k}{2k}\right)$$

询问时间复杂度为 $\mathcal{O}(\sum \lfloor \frac{n}{m}\rfloor )$，然后预处理逆元的复杂度只需要 $\mathcal{O}(V)$ 即可，其中 $V$ 为值域大小