Difference between revisions of "2019 ICPC Nanjing Onsite"

From EOJ Wiki
Jump to navigation Jump to search
Line 56: Line 56:
  
 
Solved by Kilo_5723 && Xiejiadong.
 
Solved by Kilo_5723 && Xiejiadong.
 +
 +
题意:给出一个三角形和边上的一个端点,找到另一个端点,使得两个端点构成的线段将三角形分成了等面积的两部分。
 +
 +
题解:首先需要判断这个端点是否在三角形边上,即判断一个点是否在线段上,直接判断点积以及横坐标范围即可。
 +
 +
对于寻找另外一个点,我们需要先判断在哪半个三角形内,然后通过二分来确定位置。
 +
 +
当然也可以直接算出那个端点的位置。
  
 
== Problem L ==
 
== Problem L ==
  
 
Unsolved.
 
Unsolved.

Revision as of 02:56, 7 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

Solved by Kilo_5723 && Xiejiadong.

题意:给出一个三角形和边上的一个端点,找到另一个端点,使得两个端点构成的线段将三角形分成了等面积的两部分。

题解:首先需要判断这个端点是否在三角形边上,即判断一个点是否在线段上,直接判断点积以及横坐标范围即可。

对于寻找另外一个点,我们需要先判断在哪半个三角形内,然后通过二分来确定位置。

当然也可以直接算出那个端点的位置。

Problem L

Unsolved.