PDF《IOI 2018 中国国家集训队集中培训》

49 44

25 32

50 44 第4页共10 页IOI

2018 中国国家集训队集中培训 第二试 小Y和二叉树(binary) 小Y和二叉树(binary) 【题目背景】 小Y是一个心灵手巧的 OIer,她有许多二叉树模型. 小Y的二叉树模型中,每个结点都具有一个编号,小Y把她最喜欢的一个二叉树 模型挂在了墙上,树根在最上面,左右子树分别在树根的左下方与右下方,且他们也都 满足这样的悬挂规则.为了让这个模型更加美观,小Y选择了一种让这棵二叉树的中 序遍历序列最小的悬挂方法.所谓中序遍历最小,就是指中序遍历的结点编号序列的字 典序最小. 一天,这个模型不小心被掉在了地上,幸运的是,所有结点和边都没摔坏,但是她 想不起这个模型原来是怎么悬挂的了,也就是说:她想不起来树根节点的编号了. 小Y最近忙于准备清华集训,所以没太多时间处理别的事情,她只好找到同样心 灵手巧的你帮忙复原她的二叉树模型. 【题目描述】 给定小 Y 的二叉树模型,结点的编号为

1 ~ n ,你需要给出其可能的最小的 中序遍历,方便小 Y 更快的摆好她的模型. 【输入格式】 从文件 binary.in 中读入数据. 第一行为一个正整数 n ,表示点的个数. 后接 n 行,每行若干个整数: 第i+1行的第一个整数为 ki ,表示编号为 i 的结点的度数,后接 ki 个整数 ai,j , 表示编号为 i 的结点与编号为 ai,j 的结点之间有一条边. 同一行输入的相邻两个元素之间,用恰好一个空格隔开. 【输出格式】 输出到文件 binary.out 中. 输出共一行,n 个整数,表示字典序最小的中序遍历. 【样例

1 输入】

4 3

2 3

4 1

1 第5页共10 页IOI

2018 中国国家集训队集中培训 第二试 小Y和二叉树(binary)

1 1

1 1 【样例

1 输出】

2 1

3 4 【样例

1 解释】 样例的一组最优解如下: 其中结点

4 为根,结点

1 为结点

4 的左儿子,结点 2,

3 分别为结点

1 的左右儿子. 【子任务】 本题共

20 个测试点,每个测试点

5 分.各个测试点的数据范围如下: 第6页共10 页IOI

2018 中国国家集训队集中培训 第二试 小Y和二叉树(binary) 测试点编号 n ≤ ki 特殊条件

1 5 1,2,3 无210

3 15

4 20

5 100

6 1000

7 2000

8 5000

9 1000000 1,2 结点 i 与结点 i ?

1 相连

10 100000 无11

300000 12

1000000 13

100000 1,3 保证数据随机

14 1000000 无15

20000 1,2,3 保证数据随机

16 200000

17 100000 无18

500000 19

800000 20

1000000 随机数据的生成方式如下:对于第

13 个测试点,从一棵两个结点的树开始,每次 随机一个树上的度数为

1 的结点(即叶结点) ,并生成两个与之直接相连的结点,直到 这棵树上有 n 个结点.显然,在这个测试点中,n 是一个偶数.对于第

15 和第

16 个测 试点,从一棵一个结点的树开始,每次随机一个树上的度数不超过

2 的结点,并生成 一个与之直接相连的结点,直到这棵树上有 n 个结点. 【提示】 我们提供了一个只包含输入和输出功能的程序 binary_sample.cpp.关于该程序的 说明,见readme.txt.你可以在答题时使用该程序的代码,也可以不使用,这将与你的 得分无关. 第7页共10 页IOI

2018 中国国家集训队集中培训 第二试 小Y和恐怖的奴隶主(patron) 小Y和恐怖的奴隶主(patron) 【题目背景】 A ?ght? Count me in! 要打架了,算我一个. Everyone, get in here! 所有人,都过来! 【题目描述】 小Y是一个喜欢玩游戏的 OIer.一天,她正在玩一款游戏,要打一个 Boss. 虽然这个 Boss 有10100 点生命值,但它只带了一个随从―---一个只有 m 点生命值 的'