AGC001

第一次尝试 AGC。

A（最优化、贪心）

排序之后隔一个选一个即可。

B（递推）

定义 \(f(a,b)\) 表示底为 \(b\) 腰为 \(a\) 的等腰梯形从右上角开始的答案，可以在 \(f(a,b)\) 和 \(f(b\bmod a,a)\) 间建立联系，复杂度是 \(O(n\log n)\) 的。

C（DP、树的直径）

条件相当于 \(\forall i,j,\text{dist}(i,j)\leq k\)，考虑怎么在 DP 过程中满足这个条件。可以把 \(\text{dist}\) 拆开然后在 LCA 处判断，容易想到定义 \(f_{i,j}\) 表示 \(i\) 子树内深度最大为 \(j\) 删除的最小点数，容易得到转移。理论上应该有 \(O(n\log n)\) 线段树合并做法？

正解是枚举一个点，然后把超过 \(k/2\) 的点删掉。大概尝试构造决策方案使得其满足条件且包含最优解，这样决策量就减少了。

D（构造，拆分子问题）

不会构造。

可以把回文条件看成两个点，点之间连边，最后要满足图联通。注意到图的一个性质 \(\text{deg}_i\leq 2\)，所以最后的结构是链或者环，链的话需要满足自环最多两个，也就是说若 \(a\) 包含至少 \(3\) 个奇数就无解。

先考虑构造 \(m=2\)，可以想到 \(b=\{n\}\)，不过这不能扩展到更大的情况。考虑 \(m=3\)，那么可以把整体向右边平移一位，这样每个位置可以给后面留一个“接口”，这样就可以把所有点连接起来。

不过奇数还是需要单独考虑，把奇数放在首尾就可以解决问题。

E（计数、组合意义）

原题实际上就是求 \(\sum\limits_{i<j}\binom{a_i+b_i+a_j+b_j}{a_i+a_j}\)。注意到值域比较小但是仍然没有什么比较好的方法。

一个比较厉害的做法是考虑组合数的组合意义，可以发现这个组合数实际上就是 \((-a_i,-b_i)\) 到 \((a_j,b_j)\) 的方案数。那么把这个东西拉到平面上 DP 就可以了。复杂度平方。

F（排列问题、条件转化）

好厉害 QAQ

原题的操作比较恶心，考虑 \(P\) 的逆排列 \(Q\) 上对应的操作：对于 \(|Q_i-Q_{i+1}|\geq k\) 则交换 \(Q_i\) 和 \(Q_{i+1}\)。由于交换的是相邻的数所以对于 \(|Q_i-Q_j|<k\) 则这两个数的相对位置不会改变。对应到原排列上就是 \(|i-j|<k\) 则 \(P_i,P_j\) 的相对大小不变。

然后排列的条件就相当于整数对 \((i,j)\) 满足 \(P_i<P_j\)，需要最小化 \(P\) 的字典序。大致思路是建图，然后把大的位置安排上更大的数。可以证明这样是对的，因为对于两个排列，在去除相同的前缀后，字典序更小的排列的对应位置把字典序更大的对应位置的值扔到了更后面的地方，所以算法一定会选择前者。

然后用线段树做一下就好了。