BZOJ 1089: [SCOI2003]严格n元树(dp+python)

Description

  如果一棵树的所有非叶节点都恰好有n个儿子,那么我们称它为严格n元树。如果该树中最底层的节点深度为d
(根的深度为0),那么我们称它为一棵深度为d的严格n元树。例如,深度为2的严格2元树有三个,如下图:

给出n, d,编程数出深度为d的n元树数目。

Input

  仅包含两个整数n, d( 0   <   n   <   =   32,   0  < =   d  < = 16)

Output

  仅包含一个数,即深度为d的n元树的数目。

Sample Input

【样例输入1】
2 2
【样例输入2】
2 3

【样例输入3】
3 5

Sample Output

【样例输出1】
3
【样例输出2】
21

【样例输出2】
58871587162270592645034001

今天下午花了一点时间看了一些py的东西,然后上网查了查py这东西在oj上给怎么交题以及注意事项之类的。感谢韩司机教我了一下py的基本知识。。。
 因为OJ上py都是按照字符串来读入数据的,所以我们需要用相应的字符串函数把数据切分出来。比如读入了整数n。我们就需要:

strip()是把字符串的左右空格去掉,split是按照空格或者tab来切分。

回到这道题目,一开始想直接计算答案,看有没有什么规律。发现不会做。。。问了一下别人,发现计算前缀和就可以了。

设dp[i]为高度小于等于i的所有严格n元树的方案数。我们想一下怎么计算出dp[i+1]来。高度不超过i+1的严格n元树一定是由n棵不超过i的严格n元树加上一个根节点组成的。那么很明显dp[i+1]=dp[i]^n了。但是这样的话我们只考虑了有子树的情况,但是只有一个根节点的情况也是合法的。dp[i+1]=dp[i]^n+1.

不过需要特判一下d=0的情况,因为dp[-1]貌似是变成了dp数组里的最后一个数字。

然后py直接水过。。。的确是比Java好用很多。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注