Difference between revisions of "2019 ICPC Nanjing Onsite"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) (Created page with "== Problem A == Unsolved. == Problem B == Unsolved. == Problem C == Unsolved. == Problem D == Unsolved. == Problem E == Unsolved. == Problem F == Unsolved. == Prob...") |
Xiejiadong (talk | contribs) |
||
| Line 9: | Line 9: | ||
== Problem C == | == 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 == | == Problem D == | ||
Revision as of 07:45, 6 December 2019
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.