GJ Round (2024.11) Round 22~?

前言： 点此 返回 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 \neq j)\) 连边的代价为 \(|x_i-x_j|^3+|y_i-y_j|^3\)，\(q\) 次询问，每次加入一条新边，求每次将所有点连通所花费的最小代价

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

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

C

给你两个长度为 \(n\) 的序列 \(a,b\)，保证 \(\forall i,j \in [1,n] \cap \mathbb Z,i \neq j\)，都有 \(a_i \neq a_j,b_i \neq 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} \geq m\)
2. 设魔法阵大小为 \(k\)，任意从魔法阵中选出 \(k\) 个格子，满足任意两个格子不在同一行也不在同一列，那么选出的 \(k\) 个格子的石子数之和是相同的
3. 魔法阵中对角线石子数之和不能超过 \(n\)

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

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

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

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

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