HouJikan
cjk自从明明学了树的结构,就对奇怪的树产生了兴趣...... 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?
| 题目名称 | 1663. [HNOI 2008]明明的烦恼 |
|---|---|
| 输入输出 | bzoj_1005.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cqw
于2014-06-11加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：56， 提交：347， 通过率：16.14% | ||||
 Asm.Def |
100 | 0.007 s | 0.29 MiB | C++ |
 niconicoqaq |
100 | 0.009 s | 0.33 MiB | C++ |
 葳棠殇 |
100 | 0.011 s | 0.29 MiB | C++ |
 Ngshily |
100 | 0.012 s | 0.30 MiB | C++ |
|
Ngshily |
100 | 0.013 s | 0.33 MiB | C++ |
|
niconicoqaq |
100 | 0.014 s | 0.29 MiB | C++ |
|
niconicoqaq |
100 | 0.014 s | 0.31 MiB | C++ |
 rewine |
100 | 0.014 s | 0.48 MiB | C++ |
 zys |
100 | 0.016 s | 0.29 MiB | C++ |
 stdafx.h |
100 | 0.017 s | 0.32 MiB | C++ |
| 关于 明明的烦恼 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @HouJikan :
其实……我是在拿别人代码对拍的时候发现的这个问题…… Asm.Def
2015-01-12 22:40
4楼
| ||||
|
同因为高精度数组开小了bzoj调了一下午
这里居然相比bzoj还加强了数据。。 | ||||
|
一定要注意高精度数组下标啊，我开到1000就没过去
| ||||
|
为了一个下标范围问题在bzoj上调试一晚上真是醉了= =
用到了Prufer数列、高精度和阶乘质因数分解 | ||||
【题目描述】
【输入格式】
第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1
【输出格式】
一个整数,表示不同的满足要求的树的个数,无解输出0
【样例输入】
3
1
-1
-1
【样例输出】
2
【提示】
两棵树分别为1-2-3;1-3-2