c语言 随机角色生成器,随机树生成器

随机树生成器

提交数: 5, 通过率: 0%, 平均分: 0

题目描述:

小Y最近有了一个随机数生成器(random number generator)。小Y想用这个随机数生成器生成 个节点的树。树为一种没有环的无向连通图。

经过小Y的研究，她发现了 种随机树生成方法。

第一种方法为首先生成一个 到 的全排列 。接着对于所有的节点 ，由 向 连一条边，其中 是 到 中的随机整数。

第二种方法为首先生成一个 到 的全排列 。接着对于所有的节点 ，由 向 连一条边，其中 是 到  中的随机整数。

第三种方法为首先有一个 个点的图，里面没有边。接着等概率地随机生成点对 ，如果当前图中 不连通，那么将边 加入到图中。重复这个过程，直到这个图连通为止。

第四种方法为在所有 个点的不同的有标号的树中，等概率地随机选取一棵树。两个树是不同的当且仅当存在一条边 只出现在其中一棵树中。比如 和 是两棵不同的树。

小Y用这四种方法生成了很多棵 个节点的树，但她忘记了这些树分别由哪种方法生成的。你能帮帮她辨认这些树由哪种随机方法生成吗？

在这个题目中令 ，也就是小Y生成的树的节点个数都为 。

输入格式:

第一行包含  个正整数 ，表示是第 组测试数据。

接下来一个正整数 ，表示有 棵树。

对于每棵树，共 行。每行包含 个正整数 ，表示这棵树中有一条节点 与节点 之间的边。

输出格式:

输出共 行，每行一个 到 之间的正整数，表示这棵树随机生成的方式。

样例输入:

见选手目录下的rng/rng.in与rng/rng.ans。

样例输出:

见选手目录下的rng/rng.in与rng/rng.ans。

提示:

【数据规模和约定】

对于所有的测试数据，保证输入的树是由上述四种方式随机生成。

各测试点满足以下约定：

测试点

m

约定

1

=2000

只会出现第1，2种生成方式

2

=3000

只会出现第1，2，3种生成方式

3

=3000

只会出现第1，3，4种生成方式

4

=4000

无

5

=4000

无

对于每个测试点，保证每种可能出现的生成方式恰好出现 次。

【评分方法】

对于每个测试点，有 个评分参数 。

如果你的输出中错误的答案个数为 那么你将获得 的分数，其中 为满足 最大的整数。如果 ，那么你将获得 分。

如果输出格式有异常你将同样获得 分，请确保你的输出中共有 行，每行为一个 到 之间的正整数。

对于每个测试点的具体评分参数见选手目录下的rng/scores。

2016年全国青少年信息学奥林匹克浙江省队选拔赛第一试

竞赛时间：2016年3月24日 8:00-13:00

题目名称

随机树生成器

旅行者

小星星

目录

rng

tourist

star

可执行文件名

rng

tourist

star

输入文件名

rng.in

tourist.in

star.in

输出文件名

rng.out

tourist.out

star.out

每个测试点时限

3秒

2秒

1秒

内存限制

256MB

512MB

512MB

测试点数目

5

10

10

每个测试点分值

20

10

10

是否有部分分

是

否

否

题目类型

传统型

传统型

传统型

是否有附加文件

是

是

是

提交源程序须加后缀

对于C++  语言

rng.cpp

tourist.cpp

star.cpp

对于C    语言

rng.c

tourist.c

star.c

对于Pascal语言

rng.pas

tourist.pas

star.pas

编译开关

对于C++  语言

-O2 -lm

-O2 -lm

-O2 -lm

对于C    语言

-O2 -lm

-O2 -lm

-O2 -lm

对于Pascal语言

-O2

-O2

-O2

时间限制: 3000ms

空间限制: 256MB

来源: 浙江省选2016day1t1