AGC001

AGC001

A - BBQ Easy [Safe]

题面

给定 $2n$ 个数 $a_1,a_2,\cdots,a_{2n}$，要求分成 $n$ 个包含两个数的组，使得每个组的最小值之和最大

$1\le n\le100$

题解

排序后求 $a_1+a_3+\cdots+a_{2n-1}$

复杂度 $O(n\log n)$

B - Mysterious Light [Safe]

题面

有边长为 $n$ 的等边三角形 $\Delta ABC$，在 $AB$ 边上有一点 $P$，满足 $AP=x$，从 $P$ 朝平行于 $BC$ 的方向射出一束光，这条光会在三角形的边上以及自己曾经经过的路线上反弹，求光线回到 $P$ 时经过的路线长度

$1\le x<n\le 10^{12}$

题解

考虑这条光的路径，一定是先反射两次之后在一个平行四边形内乱射

定义 $F(n,m)$ 表示一个边长为 $n$ 和 $m$ 的平行四边形内，光从一个 120° 角的角平分线射出并到达对角时经过的长度

那么有转移式子：

$$F(n,m)=\left\{\begin{matrix} n,&n=m\\ F(m,n),&n<m\\ F(n-m,m)+2m,&n>m \end{matrix}\right.$$

把减法换成取模就是 $O(\log n)$ 了

C - Shorten Diameter [Safe]

题面

给定一棵 $n$ 个点的树，求最少删多少点使得剩下的树联通且直径长度 $\le k$

$1\le n\le2000$

题解

枚举删完后的直径中点，那么距离这个点 $>\frac k2$ 的肯定都不能要，把所有中点的答案取一个 min 即可

实现细节：在每条边之间都加一个新点，这样就避免了讨论中点在点上还是在边上的问题

复杂度 $O(n^2)$

D - Arrays and Palindrome [Euclid]

题面

给定长为 $m$ 的正整数数组 $a$，满足 $\sum a_i=n$，你需要重排数组 $a$ 并构造一个正整数数组 $b$，满足 $\sum b_i=n$，且对于一个长为 $n$ 字符串 $s$，如果满足对于任意 $i$，满足 $s[(a_1+a_2+\cdots+a_{i-1}+1):(a_1+a_2+\cdots+a_i)]$ 是回文串，且对于任意 $i$，满足 $s[(b_1+b_2+\cdots+b_{i-1}+1):(b_1+b_2+\cdots+b_i)]$ 是回文串，那么可以推断出 $s$ 的所有字符全相等

给出一种构造方案，无解输出 Impossible。

$1\le n\le10^5,1\le m\le100$

题解

人类智慧题。

一个长为 $x$ 的回文串会带来 $\lfloor\frac x2\rfloor$ 个字符相等的限制，因此我们可以假设每个字符贡献 $0.5$ 个限制，且每出现一个长为奇数的回文串就会 “损失” $0.5$ 的限制，而我们通过 $a$ 和 $b$ 最多有 $n$ 个限制，我们至少需要 $n-1$ 个限制才能推出所有字符相等，因此 $a$ 和 $b$ 中一共最多只有 $2$ 个奇数长的限制，如果 $a$ 中超过这个可以直接输出 Impossible

手模可以发现：

如果有 $s[a:b]$ 为回文串且 $s[a:b-1]$ 为回文串，那么能得到 $s[a:b]$ 全相等

如果有偶数 $x$，且 $s[i:i+x-1]$ 与 $s[i+1:i+x]$ 均为回文串，那么能得到 $s[i:i+x]$ 全相等

那么我们可以给出构造：

如果 $a$ 中有 $0$ 个奇数，我们什么都不做

如果 $a$ 中有 $1$ 个奇数，我们把奇数放到 $a$ 的开头，剩下的随意

如果 $a$ 中的有 $2$ 个奇数，我们把奇数放到 $a$ 的开头和末尾，剩下的随意

那么我们的 $b$ 就是 $[a_1-1,a_2,a_3,\cdots,a_{m-1},a_m+1]$，注意去除掉长度变成 $0$ 的段

特判 $n=1$ 的情况

复杂度 $O(n)$

E - BBQ Hard [Keter]

题面

给定长为 $n$ 的数组 $a_i$ 和 $b_i$，求：

$$\sum_{i=1}^n\sum_{j=i+1}^n\binom{a_i+b_i+a_j+b_j}{a_i+a_j}$$

$2\le n\le2\times10^5,1\le a_i,b_i\le2000$，对 $10^9+7$ 取模

题解

乘 $2$ 再加上 $i=j$ 的情况，我们就可以把 $j$ 的范围也变为 $[1,n]$

对于一个特定 $(i,j)$，这相当于求 $(-a_i,-b_i)$ 走到 $(a_j,b_j)$ 的情况，而我们要求的就是对于所有这些情况之和

那么我们把点放在一个二维平面上，所有 $(-a_i,-b_i)$ 为起点，所有 $(a_i,b_i)$ 为终点，然后令 $dp_{x,y}$ 表示所有起点到达 $(x,y)$ 的方案数之和，直接对于每个整点转移即可

复杂度 $O(n+(\max a_i)^2)$

F - Wide Swap [Euclid]

题面

给定一个长为 $n$ 的排列 $p_i$，你可以交换两个排列中的元素 $p_i,p_j$，当且仅当 $j-i\ge k$ 且 $|p_i-p_j|=1$

问交换之后得到的字典序最小的排列

$1\le n\le5\times10^5$

题解

我们考虑求出原排列的逆排列 $a_i$，也即「$i$ 出现在哪个位置」，那么我们可以交换 $a_i,a_j$ 当且仅当 $|i-j|=1$ 且 $|a_i-a_j|\ge k$，这看起来就比原问题好看多了。

$p$ 的字典序最小，相当于先让第一位最小，再让第二位最小，以此类推，那么就相当于在 $a$ 中让 $1$ 的位置最小，再让 $2$ 的位置最小，以此类推

如果存在 $i<j$，满足 $a_i<a_j$，那么它们的相对顺序改变一定不优，如果满足 $|a_i-a_j|<k$，那么相对顺序一定无法改变，也即如果 $i<j$，$a_i<a_j+k$，那么它们的相对顺序一定不会改变，这样一定是最优的 $a$

因此，我们按下标顺序考虑 $a$ 序列，增量构造出排列 $b$，每次找到当前的 $b$ 中最后一个 $<a_i+k$ 的数，然后将 $a_i$ 插入在这个数之后，用平衡树实现即可

注意最后要把 $b$ 转回原来的排列

复杂度 $O(n\log n)$