AGC题解合集 - Blog

善用Ctrl+F,某些篇幅过长的题解用Link。

AGC001E

Description:
给出 $a_ i,b_ i(1\leq i\leq n)$ ,求 $\sum_ {1\leq i < j\leq n}(^{a_ i+a_ j}_ {a_ i+b_ i+a_ j+b_ j})$

$Solution$ :
对于每一对pack(i,j)，可以理解为从 $(-a_ i,-b_ i)$ 走到 $(a_ j,b_ j)$ 处的方案数。
假如说现在可以匹配自己而且pack(i,j)与pack(j,i)不同。
这时将所有pack放到一个图中就变成：左下的n个点 $(-a_ i,-b_ i)$ 到右上的n个点 $(a_ i,b_ i)$ 的总方法数
（任意一个出发任意一个到达）
这种情况对于每一个点DP出从左下的n个点中任意一个出发到他的方案数。
(不过这个DP式dp[i][j]+=dp[i-1][j]+dp[i][j-1]好像有点熟悉……)
减去自己到自己，再除以2就是答案了。
code

AGC001F

Description:
给出一个长度为n的排列p，每次操作你可以交换任意两个满足 $|i-j|>=k$ 并且 $|p_ i-p_ j|=1$ 的 $p_ i$ 和 $p_ j$ 。
求任意次操作之后所得的最小字典序的排列。

$Solution$ :
令q[p[i]]=i，那么操作就变成了交换相邻两个差的绝对值>=k的位置。
有结论当 $p$ 字典序最小时 $q$ 的字典序也是最小的。
对于 $q$ 的操作有很明显的限制：两个差小于k的元素的相对位置不能被改变。
对于每一对差小于k的点，前向后连边，跑最小拓扑序就是答案了。
但问题是现在k可能是n级别，需要减少连边数量。
现在考虑序列中前向后的三个点x,y,z，x到y有边，y到z有边，x到z有边。这时候x到z的是无用的。
再回忆一下x连出的边指向点的集合：在x之后的(x-k,x+k)。（()表示开区间）
对于(x-k,x)和(x,x+k)，每个区间内的点两两有边。
所以一个点只用向这两个区间中离它最近的点连边，剩下的，连向的点会帮忙处理。
线段树维护一下。
code

AGC005C

Description:
给出一个数组a。
要求构造一颗树，使节点i距离最远的点的距离为 $a_ i$ 。

$Solution$ :
定义dis为要求离它距离最远的点与它的距离
很显然这里距离最远的两个点构成了树的直径。
加入这两个点dis不相等，那就完了。

既然已经构造出树的直径，那dis的最小值也确定了。
分奇偶讨论一下树的直径与dis最小值的关系。
假如 $dis_ {min}!=(dis_ {max}+1)/2$ ，那也完了。
如果除了树的中心还有点 $dis=dis_ {min}$ ，那也完了。
这是一条链，到端点的距离是线性的，所以两边都各需要dis在 $(dis_ {min} dis_ {max})$ 上每个位置的一个数。
剩下的dis在 $(dis_ {min},dis_ {max}]$ 之间的数，可以挂在直径上，不会影响结果。
code

AGC008F

Description
Solution

AGC010E

Description:
一个长度为n的序列。
先手可以任意打乱，然后后手可以执行若干次以下操作：交换两个相邻且互质的数。
先手希望字典序最小，后手希望字典序最大，最后序列会变成啥样？

$Solution$ :

对于两个不互质的数 $a,b$ ，他们的相对顺序不会被改变。

把原序列中所有gcd不为 $1$ 的对都连上边，这样我们就得到了一个简单无向图。
对于每一个联通块，先手要做一些事情。
对于这个联通块建立序列的某个位置，先手必须要保证它最小，而且这个联通块中与他互质并比他大的数不能通过交换达到这个位置。
那也就是说必须通过gcd链到达那个点，那个点才不会“篡位”
先手的最优策略是把每个连通块最小的点作为起点，然后每次找到最小且没走过的点走过去。
这样对于每个联通块直接从最小的点开始从小到大深搜建立拓扑图正好就是想要的东西了。
后手就是每次找入度为0且的点中最大的，然后把这个点删掉。
code

AGC012E

Description:
一排点，两点间有距离。
初始你有一个行走值v，如果相邻两点距离不超过v你可以自由在这两点行走。
当v大于0时，你可以选择某一时刻突然飞到任意点，这样做后v会减半（下取整）。
问从每个位置初始出发能否到达所有位置。

$Solution$ :
通过状压枚举前后缀就可以枚举所有情况了。
预处理left[i,j]表示在i行走值已经减半j次能往左走到哪，同理有right。
我们每次从i点出发，用行走值v可以走到[l,r]。
那么你需要将接下来的行走值分成两部分然后覆盖[1,l-1]和[r+1,n]。
我们希望预处理一个mi[i]表示用行走值中的一部分覆盖[1,i]，另一部分能覆盖[x,n]，x的最小值是多少。
然后为了这个先状压DP一下，设f[s]表示用s集合里的行走值覆盖[1,x]最大的x是多少，每次可以枚举一个不在s里的i然后转移，用这个i去覆盖接下来一段。
同理会有个g[s]表示覆盖[x,n]。
于是接下来再枚举拿哪些覆盖前缀即可处理mi。
在预处理时不考虑扔掉不跳跃的行动力，最后手动处理一下。
还有记得没有行动力也可以通过跳转来占据一个点，所以要多加一个行动力为0的段。
code

AGC013D

Description:
在箱子里放n个球，有黑白两色。
执行m轮操作：
抓箱子里一个球堆在塔顶。
往箱子里放入一个黑球和一个白球。
再抓箱子里的一个球堆在塔顶。
求塔的方案数（按颜色看）

$Solution$ :
先假设有 $x$ 个红色， $n-x$ 个蓝色。
发现会有一些性质：

每步操作前后球的总个数为 $n$
一个合法的数列有多个初始的 x 值，对于最小的 x 值，在操作的过程中，x 会变成0

所以统计一下中途 $x$ 有变成0的数目就是答案。
code

AGC019F

Description:
n+m个询问，有n个询问的答案是Yes，其余m个是No。
你依次回答这些询问，每个询问给出Yes或No，给出后告诉你答对了没有。
求最优策略下你期望答对的询问个数。

$Solution$ :
可以把(n,m)这个二元组看成一个网格，目标是走到(0,0)。
最优策略是选择剩余多的，一样多乱猜一个（其实也没有其他策略了……）
先考虑暴力，统计每一条边会被经过次的次数，每条边的贡献=max{x,y}/(x+y)* 次数，然后除以总方案数就是答案。
画一条y=x的直线。
你假设从一个(i,i)走到(0,0)中途不到对角线。
那么显然你会一直猜同一个，一定会答对i个。
发现从(n,m)到(0,0)无论中途多曲折，经过对角线多少次，我们一个部分一个部分分开，都会答对对应次。
因此无论如何都会答对n次。
如果走到对角线上，我们会乱猜，只有1/2几率对。
因此对于对角线上每一个点统计经过它的方案数即可。
code