A - BBQ Easy
从小到大排序以后，答案就是所有奇数位置之和。
B - Mysterious Light
发现去掉前两次反射以后，剩下的是一个在平行四边形内反射的过程，且形式类似于辗转相除。具体地，
\[F(n,x)=\begin{cases} -n & x=0\\ 2x\lfloor\frac{n}{x}\rfloor+F(x,n\bmod x) & x>0 \end{cases} \]最后的答案就是 \(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
现在已经成为套路了。
答案就是
\[\sum_{1\le i<j\le N} \binom{A_i+A_j+B_i+B_j}{A_i+A_j}. \]假如固定 \(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)\)。
标签：lfloor,AtCoder,DAG,最大,奇数,拓扑,Contest,001,答案 From： https://www.cnblogs.com/alan-zhao-2007/p/17897460.html