AGC001 做题小记

比赛链接:AGC001

写完AGC003发现忘记写AGC001了……赶紧来补一发。

(刷新以获取数学公式)

E. BBQ Hard

题意

给定 $n$ 和数组 $A$, $B$， 求:

$$\sum_{i≠j}\dbinom{A_i+A_j+B_i+B_j}{A_i+A_j}$$

$n ≤ 200000$, $A[i], B[i] ≤ 2000$

题解

亮点在于模型转化。

考虑坐标平面上的 $n$ 个点 $(A_i, B_i)$, $\dbinom{A_i+A_j+B_i+B_j}{A_i+A_j}$ 就是从 $(-A_i, -B_i)$ 走到 $(A_j, B_j)$ 的方案数。

求和的话只是可以有多个起点而已。DP即可。

注意要去掉 $(-A_i, -B_i)$ 走到 $(A_i, B_i)$ 的贡献。

代码

F. Wide Swap

题意

给定 $1$ ~ $n$ 的一个排列 $p$ 和整数 $K$ ， 每次可以选择两个数 $i$, $j$ 满足 $j - i ≥ K$ 且 $abs(p_i - p_j) = 1$, 然后交换 $p_i$, $p_j$。

问最小可以得到的字典序。

n ≤ 500000

题解

$j - i >= K$ 这个限制非常难处理。所以我们转而在 $p$ 的逆上进行操作。

令 $q_{p_i} = i$, 交换的限制就变成了：选择两个绝对值差大于 $K$ 的相邻数。

注意到 $q$ 字典序最小等价于 $p$ 字典序最小。而如果两个数绝对值差小于$K$，他们的相对顺序不可能改变。

对这样的限制连边，就变成了求字典序最小的拓扑序列。

但是这样连出的边数是 $O(n ^ 2)$ 的。考虑对它进行优化。

数 $x$ 只会向 $(x - K, x)$ 和 $(x, x + K)$这两段区间连边。而每段区间只需连这段区间中已经出现过且下标最小的数即可，线段树维护一下。

最后别忘记再还原到 $p$数组

代码