比赛链接: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\)数组