2019 ICPC Nanjing Onsite

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Solved by Xiejiadong.

题意：求一个矩阵中有多少满足下列要求的路径：

• 路径是极长的，不可在原基础上拓展；

• 路径的每一个位置单调递增且间隔为 $1$ ；

• 长度 $\ge 4$ 。

题解：用 $f[i][1/2/3/4]$ 分别表示到当前位置 $i$ 的长度分别为 $1/2/3/ \ge 4$ 的路径数量。

因为只能从值为 $x$ 的位置向 $x+1$ 的位置走，所以是一个 DAG ，按照拓扑排序顺序直接递推即可。

因为要是极长的，所以只有极小的位置能作为开头 $f[i][1]=1$ ，其余位置 $f[i][0]=0$ ；结束位置必须是极大的，统计答案的时候判断即可。

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Unsolved.

Problem L

Unsolved.