Difference between revisions of "2019 ICPC Nanjing Onsite"

From EOJ Wiki
Jump to navigation Jump to search
 
(10 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
== Problem A ==
 
== Problem A ==
  
Unsolved.
+
Solved by Kilo_5723.
 +
 
 +
题意:求从 $[1,n]$ 中随机取出至少多大的子集,能保证其中的数有至少一对存在倍数关系。
 +
 
 +
题解:通过样例猜出答案是 $\lfloor\frac{n+3}{2}\rfloor$,稍微又想了想,最坏的情况是不停的取最大的,这个时候答案应该确实是这样。
  
 
== Problem B ==
 
== Problem B ==
  
Unsolved.
+
Solved by Kilo_5723.
 +
 
 +
题意:遍历一个矩阵,使得被访问过的块之间一直有只经过被访问的块的最短路,求方案数。
 +
 
 +
题解:模拟之后发现起点只能是角块,而且确定起点之后只可能是新增一行或一列,因此 $dp[i][j]=dp[i-1][j]+dp[i][j-1]$,而 $dp[x][1]=dp[1][x]=1$。得出 $dp[n][m]=C_{n+m-2}^{n-1}$,答案就是角块数量与 $C_{n+m-2}^{n-1}$ 的乘积。
  
 
== Problem C ==
 
== Problem C ==
Line 31: Line 39:
 
== Problem E ==
 
== Problem E ==
  
Unsolved.
+
Solved by Weaver_zhu.
  
 
== Problem F ==
 
== Problem F ==
  
Unsolved.
+
Solved by Xiejiadong.
 +
 
 +
题意:给出一个字符串,统计一个区间里面和给出字符串的公共前缀长度 $\ge k$ 的数量。
 +
 
 +
题解:把所有的模式串插入 Trie ,如果我们把插入 Trie 的模式串按照 dfs 序编号。
 +
 
 +
公共前缀长度 $\ge k$ 的所有字符串所在的结尾结点,一定是当前字符串第 $k$ 位对应的 Trie 上结点的孩子,所以一定是 dfs 序标号以后连续的一段。
 +
 
 +
于是可以通过差分,变成询问给定区间中 $\le k$ 的数量。
 +
 
 +
然后交换操作,可以变成单点修改操作,于是这部分就需要用树套树来维护了。
  
 
== Problem G ==
 
== Problem G ==
Line 59: Line 77:
 
== Problem J ==
 
== Problem J ==
  
Unsolved.
+
Solved by Weaver_zhu.
  
 
== Problem K ==
 
== Problem K ==
Line 72: Line 90:
  
 
当然也可以直接算出那个端点的位置。
 
当然也可以直接算出那个端点的位置。
 
== Problem L ==
 
 
Unsolved.
 

Latest revision as of 10:40, 7 December 2019

Problem A

Solved by Kilo_5723.

题意:求从 $[1,n]$ 中随机取出至少多大的子集,能保证其中的数有至少一对存在倍数关系。

题解:通过样例猜出答案是 $\lfloor\frac{n+3}{2}\rfloor$,稍微又想了想,最坏的情况是不停的取最大的,这个时候答案应该确实是这样。

Problem B

Solved by Kilo_5723.

题意:遍历一个矩阵,使得被访问过的块之间一直有只经过被访问的块的最短路,求方案数。

题解:模拟之后发现起点只能是角块,而且确定起点之后只可能是新增一行或一列,因此 $dp[i][j]=dp[i-1][j]+dp[i][j-1]$,而 $dp[x][1]=dp[1][x]=1$。得出 $dp[n][m]=C_{n+m-2}^{n-1}$,答案就是角块数量与 $C_{n+m-2}^{n-1}$ 的乘积。

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

Solved by Weaver_zhu.

Problem F

Solved by Xiejiadong.

题意:给出一个字符串,统计一个区间里面和给出字符串的公共前缀长度 $\ge k$ 的数量。

题解:把所有的模式串插入 Trie ,如果我们把插入 Trie 的模式串按照 dfs 序编号。

公共前缀长度 $\ge k$ 的所有字符串所在的结尾结点,一定是当前字符串第 $k$ 位对应的 Trie 上结点的孩子,所以一定是 dfs 序标号以后连续的一段。

于是可以通过差分,变成询问给定区间中 $\le k$ 的数量。

然后交换操作,可以变成单点修改操作,于是这部分就需要用树套树来维护了。

Problem G

Unsolved.

Problem H

Solved by Xiejiadong.

题意:已知有 $a$ 个人说真话,$b$ 个人说假话,$c$ 个人乱说话,问至少询问几次,可以得到正确答案。

题解:显然,要得到正确答案,我们只能从真话的人中得到。但由于不知道哪些人是说真话的,所以只能数量取胜,也就是只有 $a > b+c$ 的时候才有可能得到答案。

显然这种时候,要数量取胜,至少询问 $2(b+c)+1$ 次。

但是注意到有一个特殊情况 $a=1,b=0,c=0$ 的时候,其实不需要任何的询问。

Problem I

Unsolved.

Problem J

Solved by Weaver_zhu.

Problem K

Solved by Kilo_5723 && Xiejiadong.

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

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

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

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