AGC杂题乱做

热度: loading...

一些很好但是没有成套刷掉的AGC题...之后如果某一场比赛里的刷完了会把这里的搬过去。

【1】

AGC032C

给你一个无向图，将其边集划分成三部分，使得每一部分都是一个 可以重复经过多个点 的环

图论分讨好题。

首先判断由于图要满足可以拆分成多个环的性质，因此每个点的度数都必须是偶数。

然后考虑每一个点的度数，如果存在一个点的度数 $≥6$ ，那么把这个点的每两条边拿出来分裂成一个环，则满足条件。

考虑没有点的度数 $≥6$ ,如果每个点的度数都是 $2$ ，说明整张图就是一个大环，肯定不行。

考虑度数为 $4$ 的点。

如果该点只有一个，那么图形如两个环交于一点，显然不可。

如果该点有两个，分类讨论。如果图形如四条链首尾交于两个点则不行，如果其中有环仅包含其中的一个点，那么就把这个环分出来，最后一定能分出 $3$ 个，dfs判断即可。

如果该点有三个即以上，两两配对即可。

AGC032D

给定一个排列，你可以花费 $A$ 使一个区间最左边的数跑到最右边，或者花费 $B$ 的代价使最右边到最左边，求把整个序列变成升序的最少花费

相当于每次可以使每个数任意跑到左边的一个位置或右边的一个位置。考虑对于每个元素最多被操作一次，因为多次操作不如一次操作直接完成。

将元素分为两类：会被移动的和不会被移动的。可以注意到不会被移动的元素一定是原始排列中的一个上升子序列。考虑在固定了不会移动的元素之后计算贡献。设相邻的两个不会移动的元素为 $p_i$ 和 $p_{i-1}$ ，由于两个元素之间没有不会移动的元素，统计 $p_i$ 和 $p_{i-1}$ 之间小于 $p_i$ 和大于 $p_i$ 的数的数量，分别将其向左移和向右移，动态规划即可。

AGC032B

由于智推的缘故又刷了一道032...蛮简单的构造。

给定整数 $N$ ，构造一个从 $1$ 到 $N$ 编号的 $N$ 个节点的无向图，使得该图不含有重边和自环，并且是连通的，且每个节点的所有邻接节点的编号之和相同。

首先第一个想法当然是 $1-n,2-(n-1),3-(n-2)\cdots$ 这样配对。每个点的权值为 $n+1$ 。可是这个做法完全不行，根本不连通。于是考虑对上面那种连边方式取补图，于是每个点的权值变为 $\frac{n\times (n+1)}{2}-n-1$ 。这样就保证了连通性。

可是我们发现当 $n$ 为奇数的时候由于没有两个 $(n+1)/2$ ，导致无法像上面那样连边。于是我们将 $n$ 单独提出来， $1\sim n-1$ 用之前的方式连边，之后将 $1\sim n-1$ 都与 $n$ 连起来，这样每个点的点权都是 $\frac{n\times (n-1)}{2} -n +n=\frac{n\times (n-1)}{2}$ 。

APC001E 6.19

事情的起因是这样的，最近打的一场CF（#801）的D题被爆破了，原题就是ATcoder APC的原题（话说没有这个我都不知道APC）。

~~这个好像不算AGC~~

有一棵 $n$ 个节点的树，无边权。
选择 $k$ 个点。树上每个点到这 $k$ 个点的距离构成一个 $k$ 维坐标。
求得最小的 $k$ 使得每个坐标都不相同。

考虑随便设定一个节点为根。两个节点的坐标不相同当且仅当一个有两个及以上儿子的节点，其子树内没有被选定的点，因此其他点到他的两个儿子的距离都是相同的。

考虑选定两个节点之后，这两个节点之间的链都可以表示出来。因此选定两个节点后，如果两个节点可以向两端拓展，那么拓展之后表达的范围一定不会更小，因此选定的节点一定是原树中度数为 1 的叶节点。

考虑先选定所有的叶节点。同上，如果一个节点的度数大于 2 ，即其儿子大于 1，那么一定需要至少一个选定的节点。但是其有一个儿子可以不选，通过其他儿子中的点用排除法表示出来。因此每个度数大于 2 的节点可以提供一个不选的机会，dfs 搜索从每个叶子节点出来遇到的第一个度数大于 2 的节点，将其打上标记，之后用总的叶节点数减去打上标记的节点数量即可。

赏