AtCoder Grand Contest 001

比赛链接

A - BBQ Easy

从小到大排序以后，答案就是所有奇数位置之和。

B - Mysterious Light

发现去掉前两次反射以后，剩下的是一个在平行四边形内反射的过程，且形式类似于辗转相除。具体地，

最后的答案就是 \(F(n-x,x)+n\)。

C - Shorten Diameter

直接 DP，设 \(f_{i,j}\) 表示考虑 \(i\) 子树内的一个以 \(i\) 为根的连通块，最大深度不超过 \(j\)，且直径不超过 \(K\)，的最大点数。合并子树信息是简单的。

D - Arrays and Palindrome

这个题就比较智慧了。

首先，一段长为 \(L\) 的回文串能够贡献 \(\lfloor\frac{L}{2}\rfloor\) 对相等关系。由于相等关系至少需要有 \(n-1\) 对，所以给定的 \(A\) 数组中至多有两个奇数，否则无解。

将这两个奇数放到开头和结尾，并构造 \(B:=[A_1-1,A_2,\dots,A_{M-1},A_M+1]\)。注意特判 \(M=1\) 和 \(A_1=1\) 的情况。

E - BBQ Hard

现在已经成为套路了。

答案就是

假如固定 \(i,j\)，那么这个组合数可以描述为从 \((-A_i,-B_i)\) 走到 \((A_j,B_j)\)，每次只能向上或向右走的方案数。

由于值域很小，所以可以统一进行一次 DP。时间复杂度 \(O(N+V^2)\)。

F - Wide Swap

考虑 \(P\) 的逆排列 \(Q=P^{-1}\)，在 \(Q\) 上，操作可以描述为每次交换相邻的两个差 \(\ge K\) 的元素。

考虑一对 \(i,j\) 满足 \(i<j\) 且 \(|Q_i-Q_j|<K\)，那么 \(Q_i\) 在任意时刻都一定在 \(Q_j\) 前面。并且只要对于任意 \(i,j\) 均满足这个条件，这样的 \(Q\) 就是能得到的。

根据这个条件可以建出一张 DAG，我们需要最小化这个 DAG 的一个拓扑序 \(p\) 的逆 \(p^{-1}\)。根据一个结论：

在一张 DAG 上，一个字典序最大的拓扑序 \(p\)，其逆 \(p^{-1}\) 也是字典序最大的。

所以只需要在反图上求最大拓扑序 \(p\)，然后 \(\operatorname{reverse}(p^{-1})\) 就是答案。

唯一的问题就是这张图有 \(O(N^2)\) 条边。但这也是容易的：考虑从 \(Q_i\) 连出去的边，也就是所有的 \(j<i\) 满足 \(Q_j\in (Q_i-k,Q_i+k)\)。只需要向其中 \(Q_j<Q_i\) 的最大 \(j\)，以及 \(Q_j>Q_i\) 的最大 \(j\) 连边即可。

时间复杂度 \(O(N\log N)\)。