[AGC061B] Summation By Construction 题解
pjykk
·
·
题解
卡了一车人的题，着实抽象。
题目大概是说，对完全二分图 $K_{n,n+1}$ 的每条边染色 $1,2,\cdots,n$ 使得所有颜色为 $i$ 的边恰构成长度为 $2i$ 的链（不能经过重复顶点）。
首先容易发现这个东西当 $n$ 是奇数和 $n$ 是偶数的时候性质不是很一样。我们也分两种情况讨论。
### 1. n 为奇数
容易发现，颜色为 $n$ 的边的染色方式已经固定了。
以 $n=5$ 为例：（用邻接矩阵表示，横行为左部点，竖列为右部点）
$$\begin{bmatrix}
5 & 5 & & & &\\
& 5 & 5 & & &\\
& & 5 & 5 & &\\
& & & 5 & 5&\\
& & & &5&5
\end{bmatrix}$$
容易想到仿照 $5$ 的填法填剩下的数字。具体的构造像下面这样：
$$
\begin{bmatrix}
5 & 5 & 4 & 4 &3 &3&|&&&&\\
& 5 & 5 & 4 & 4&3&|&3&&&\\
& & 5 & 5 & 4&4&|&3&3&&\\
& & & 5 & 5&4&|&4&2&2&\\
& & & &5&5&|&1&1&2&2
\end{bmatrix}
$$
当然右边多出来的部分要循环填到左边。
因为 $5=4+1=3+2$ 这样的式子，对于更大的奇数可以用同样的方法构造。
### 2. n 为偶数
显然 $n=2$ 无解。我们考虑 $n=4$ 怎么做。
首先颜色为 $n$ 的边的染色方式还是固定的：
$$\begin{bmatrix}
4 &4 & & &\\
& 4 & 4 & &\\
& &4 & 4 &\\
& & & 4 & 4
\end{bmatrix}$$
然后就不好填了。
注意到这样一个事情，像这样先右再下的折线表示的是从右部点开始，相对地先下再右的折线表示的是从左部点开始。
因为 $n$ 为偶数，原图中左部点的度数都是奇数，而右部点的度数都是偶数。
而每次加上一条路径的时候，只会使路径的两个端点的奇偶性发生变化。实际上因为路径的长度为偶数，只会使属于相同部分的两个点的奇偶性同时发生变化。
这样，已经染完了颜色为 $n$ 的边，而它是从右部点回到右部点的，为了使得度数满足要求，我们需要再找一条这两个点之间的路径，让它们的度数重新变回偶数；之后就不要再连右部点到右部点的路径了。
遵循这样的思路，并参考 $n$ 为奇数的情况可以找到这样一种构造：
$$\begin{bmatrix}
4 &4 & & &\red{2}\\
\red{1} & 4 & 4 & &\red{1}\\
\red{2}& 3 &4 & 4 &\red{2}\\
\red{2}& 3&3& 4 & 4\\
-&-&-&-&-\\
&&3&3&\\
&&&3&
\end{bmatrix}$$
这个构造也是能推广到所有 $\geqslant 4$ 的偶数的。
为了让规律更加明显，下面列出 $n=8$ 时的构造：
$$
\begin{bmatrix}
8 & 8 & & & & & & &\red{2} \\
\red{1} & 8 & 8 & & & & & &\red{1} \\
\red{2} & 7 & 8 & 8 & & & & &\red{2} \\
6 & 7 & 7 & 8 & 8 & & & & \\
6 & 6 & 7 & 7 & 8 & 8 & & & \\
5 & 6 & 6 & 7 & 7 & 8 & 8 & & \\
5 & 5 & 6 & 6 & 7 & 7 & 8 & 8 & \\
\red{2} & 5 & 5 & 6 & 6 & 7 & 7 & 8&8 \\
- & - & - & - & - & - & - & - & -\\
& & 5 & 5 & 6 & 6 & 7 & 7 & \\
& & & 5 & 5 & 6 & 3 & 7 & \\
& & & & 5 & 4 & 3 & 3 & \\
& & & & & 4 & 4 & 3 & 3\\
& & & & & & 4 & 4 & 3\\
& & & & & & & 4 & 4\\
& & & & & & & &4
\end{bmatrix}
$$
只是特殊处理了 $1,2$， 应该还算比较美观，没有那么抽象。
结合两种情况，时间复杂度 $O(Tn^2)$，做完了！