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)\)。
- AtCoder Contest Grand 001atcoder contest grand 001 authentic atcoder contest grand negative atcoder contest grand atcoder contest radius grand atcoder contest grand 022 avoidance atcoder contest grand histogram atcoder contest grand atcoder contest grand 019 atcoder contest grand 017 atcoder contest grand 039