hihoCoder Challenge 27 题解

2
0

A:

这个题目属于简单的签到题,用求最大空正方形类似的方法就可以解决。

令A[i][j]表示输入矩阵的(i,j)位置的数。
不妨令dp[i][j]表示以(i,j)这个位置为左上角的最大的福字的大小。
容易看出如果A[i][j]=A[i+1][j]-1=A[i][j+1]-1=A[i+1][j+1]-2, 那么我们就有dp[i][j] = min(dp[i+1][j],dp[i][j+1],dp[i+1][j+1]) + 1
否则的话就有dp[i][j] = 1。

B:

这个题目属于比较简单的处理题,附加一个组合小观察。

首先考虑这样一个东西,架设两个不相交的子树a和b的大小分别为A和B,
要求各自的1的数量相等的概率。
考虑每一种1的数量相等的情况,假设我们把b中的点权值都反转一下,可以发现就恰好变成了,a和b中一共有B个1的概率,
也就是comb(A+B,B)。

那么先考虑只有一个玩家的情况,根据上述公式直接计算出结果就可以了。

考虑有多个玩家的情况。我们不妨选出这样两个玩家x和y,使得删掉x和y之后,整个树分成了三部分A和B和C,见下图,B是x和y之间的子树,
A是x关于y的另一边的子树,C是y关于x的另一边的子数。

-A--x---B---y----C---
|          |  |-   |--
           |

并且满足子树A和C中都没有别的玩家。
那么,容易看到,要想让玩家x和y对应的限制成立,我们必须有A和C的子树和相同,并且子树B中所有点和都为0。
注意到我们还需要判断一下其它B中的玩家的限制是否合法,以及特别判断一下所有点的权值都是0的情况就可以了。

C:

这个题目属于比较直接的树形dp的问题。

用dp[i][j]表示当前考虑到子树i,往上有j条路径连出去。
在转移的时候计算一下如何将孩子们连上来的路径凑成对,或者将连上的路径继续往上连,或者将连上来的路径在该点结束
这几类情况就可以了。

D:

这个题目属于一个难度中等的计数题。
不妨考虑子串长度l=n-k+1的情况。
那么只有k个长度为l的子串,不妨令他们为s_1,s_2,...,s_{k}。
对于每个s_i,我们可以算出它不同于s_1,...,s_{i-2},s_{i-1}的概率, 并且可以看出这就是它的贡献。
如何计算概率可以使用容斥,枚举和哪些相同,然后进行简单的计算就行了。

  • 请问B题“所有点的权值都是0的情况”要怎么判断啊?

  • 添加评论
  • reply

0 answer(s)

write answer 切换为英文 切换为中文


转发分享