AGC 颓废记录

hzr 每天教我一道 AGC。

AGC001

AGC001C Shorten Diameter

AGC001D Arrays and Palindrome

AGC001E BBQ Hard

容易发现 \({a_i+b_i+a_j+b_j\choose a_i+b_i}\) 是 \((-a_i,-b_i)\) 到 \((a_j,b_j)\) 的格路行走方案数，然后你在第三象限建 \(n\) 个源，第一象限建 \(n\) 个汇，暴力 dp 即可。

AC

AGC001F Wide Swap

首先转逆排列，\(q_i\) 为 \(i\) 这个数的位置，那么就是若 \(|q_i-q_{i+1}|\geqslant k\) 则能交换两个相邻的数，在最小化 \(q_i=1\) 的 \(i\) 的情况下，最小化 \(q_j=2\) 的 \(j\)，然后是 \(q_k=3\) 的 \(k\)……

显然 \(q_i\) 差小于 \(k\) 的数对不能更改相对顺序，我们将这些数按照其位置顺序连有向边，那么最后的，\(q\) 就是这张图的一个拓扑序，最小化上述内容是一个经典问题 P3243 [HNOI2015]菜肴制作，其做法是：

将所有边反向，拓扑排序每次取编号最大的点删除，最后将拓扑序翻转。（证明略去）

然后考虑优化这个过程，我们只需要建一棵线段树维护区间 \(\min\)，一开始 \(deg=0\) 的结点就是满足 \([i-k+1,i+k-1]\)，然后每删一个点就检测其两边长度为 \(k\) 的区间的最小值是否能进入队列即可。

AC

AGC039

AGC039D Incenters