AGC 专题

牛逼题专题。

PART I

菜是原罪。

AGC 001

https://atcoder.jp/contests/agc001/tasks。

B. Mysterious Light

Portal.

先照一次之后就是平行四边形，直接递归即可。代码。

C. Shorten Diameter

Portal.

按照直径的奇偶性枚举点或边即可。代码。

D. Arrays and Palindrome

Portal.

出现两个以上的奇数无解，否则错位一下就行。代码。

E. BBQ Hard

Portal.

可以抽象成 $(0,0)\rightarrow(a_i+a_j,b_i+b_j)$，也就是 $(-a_i,-b_i)\rightarrow(a_j,b_j)$，就可以直接统计了。代码。

* F. Wide Swap

Portal.

两个限制看上去就不像是人能做的东西，因此考虑构造 $Q_{P_i}=i$，然后就变成交换相邻的数值 $\ge k$ 的数了。

然后直接冒泡过去就 TLE 了，改成归并就好了。代码。

这里大致说一下为什么这个东西是对的，如果想要让 $P$ 的字典序最小，那就应该让值 $1$ 的下标尽可能小，也就是 菜肴制作 的排序方式，对于冒泡排序来说，我们必定会将 $Q_x=1$ 的 $x$ 搞到尽可能地小。实际上是要求 $Q$ 的字典序最大（翻转后）。

然后大概讲述一下本题的正常做法：如果 $|Q_i-Q_j|<k$，那么相当于它们之间的顺序无法进行更改。这样的话可以枚举两个位置，满足被定死的条件则从前面向后面的位置连边，然后建反图求字典序最大的拓扑序（但实际上这道题中这玩意儿跟求直接求最小字典序拓扑序是等价的，证明可以反证，也比较好证。也正是这个原因，排序做法才得以成立，否则让排序来做一个将其变成字典序最大的东西是做不了一点的）。

对于正常做法来说，考虑线段树优化建图。倒序枚举 $i$，然后找出 $[a_{i}-k+1,a_{i}+k-1]$ 中 $>i$ 的最小值 $x$，然后向它们连边（其实要分别找两边）。不难发现这样就可以刻画原图的连通性。代码。

AGC 002

https://atcoder.jp/contests/agc002/tasks。

D. Stamp Rally

Portal.

这个东西不难想到二分答案。建立出基于点权的 Kruskal 重构树，然后直接做就行。代码。

E. Candy Piles

Portal.

挺有意思的博弈论。

将权值从大到小排序，可以转化为网格图，那么从 $(0,0)$ 开始，操作就相当于向右或向上走一步。

两种操作

谁走到边界上的点谁就输了，因此如果从边界上的点开始，那么后手必胜。对于任意一个不在边界上的点，如果它的上面和右面都是后手必胜点，那么这个点一定是后手必败点，否则结果相反。

红色后手胜，蓝色先手胜

找到最大正方形，然后向上和右扩展即可。

红色

代码。

F. Leftmost Ball

Portal.

考虑最终形成的合法序列，一定是 $k$ 个白色球加上 $n$ 中颜色的球各 $k-1$ 个，合法情况是前缀白球个数大于等于其它颜色数。

$f_{i,j}$ 表示 $i$ 个白球，放了 $j$ 个颜色的方案数。

决策有两种：

• 放置一个白球，有 $f_{i,j}\stackrel{+}{\leftarrow} f_{i-1,j}$；
• 加入新颜色的球，即从 $f_{i,j-1}$ 转移。系数是多少？首先需要在 $n-j+1$ 中选择一个作为这时放置的颜色，将其中一个放置在第一个空位，然后剩下的 $k-2$ 个在后面的 $nk-i-(j-1)(k-1)-1$ 中找 $k-2$ 个放即可。

然后就完了。代码。

UPD

可能不更新了，以后的 AGC 题会放在加训记录里。