题解：AT_arc214_d [ARC214D] Distinct Sum Grid Path

ran_qwq · 2026-02-10 16:53:31 · 题解

考虑让越往右上的格子越小，越往左下的越大，这样好构造一些。

先钦定第一行和最后一列是 0。再按行从上到下，列从右到左的顺序钦定每个数，使得已钦定的路径中最大的路径之和恰好小于经过当前数的路径中最小的路径之和。具体地，设当前位置是 (i,j)，已钦定的路径中最大的路径为 (1,1)\to (i-1,1)\to (i-1,j+1)\to (i,j+1)\to (i,n)\to (n,n)，经过当前数的路径中最小的路径为 (1,1)\to (1,j)\to (i,j)\to (i,n)\to (n,n)。

比如说 n=5 的表格是这样的：

0 0 0 0 0
1 1 1 1 0
2 3 4 4 0
4 7 10 10 0
8 14 20 20 0

这样路径和 0\sim \binom{2n-2}{n-1}-1 都恰好取到一次，可以通过。

这是代码。