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

IOI

2018 中国国家集训队集中培训 第二试 时间:2017 年12 月4日08:10 ? 13:10 题目名称 小Y和地铁 小Y和二叉树 小Y和恐怖的奴隶 主 题目类型 传统型 传统型 传统型 目录 metro binary patron 可执行文件名 metro binary patron 输入文件名 metro.

in binary.in patron.in 输出文件名 metro.out binary.out patron.out 每个测试点时限 2.0 秒1.0 秒2.0 秒 内存限制

512 MB

512 MB

512 MB 测试点数目

50 20

10 每个测试点分值

2 5

10 提交源程序文件名 对于 C++ 语言 metro.cpp binary.cpp patron.cpp 对于 C 语言 metro.c binary.c patron.c 对于 Pascal 语言 metro.pas binary.pas patron.pas 编译选项 对于 C++ 语言 -O2 -lm -O2 -lm -std=c+ +11 -O2 -lm 对于 C 语言 -O2 -lm -O2 -lm -O2 -lm 对于 Pascal 语言 -O2 -O2 -O2 IOI

2018 中国国家集训队集中培训 第二试 小Y和地铁(metro) 小Y和地铁(metro) 【题目描述】 小Y是一个爱好旅行的 OIer.一天,她来到了一个新的城市.由于不熟悉那里的 交通系统,她选择了坐地铁. 她发现每条地铁线路可以看成平面上的一条曲线,不同线路的交点处一定会设有 换乘站 .通过调查得知,没有线路是环线,也没有线路与自身相交.任意两条不同的 线路只会在若干个点上相交,没有重合的部分,且没有三线共点的情况.即,如图所示 的情况都是不存在的: 小Y坐着地铁

0 号线,路上依次经过了 n 个换乘站.她记下了每个换乘站可以换 乘的线路编号,发现每条线路与她所乘坐的线路最多只有

2 个换乘站.现在小 Y 想知 道,除掉她经过的换乘站以外,这个城市里最少有几个换乘站.只有你告诉她正确的答 案,她才会答应下次带你去玩呢. 【输入格式】 从文件 metro.in 中读入数据. . 请.注.意.本.题.有.多.组.输.入.数.据. 输入数据的第一行是一个整数 T, 表示输入数据的组数. 接下来依次给出每组数据. 对于每组数据,第一行是一个整数 n,表示小 Y 经过的换乘站的数目.第二行为 n 个用空格隔开的整数,依次表示每个换乘站的可以换乘的线路编号.这些编号都在

1 ~ n 之内. 【输出格式】 输出到文件 metro.out 中. 对于每组输入数据,输出一行一个整数,表示除掉这 n 个换乘站之外,最少有几 个换乘站. 第2页共10 页IOI

2018 中国国家集训队集中培训 第二试 小Y和地铁(metro) 【样例

1 输入】

4 4

1 2

1 2

8 1

2 3

4 1

2 3

4 5

5 4

3 3

5 8

1 2

3 4

1 3

2 4 【样例

1 输出】

0 0

0 1 【样例

1 解释】 对于样例的前两组数据,一种可能的最优答案如下图所示. 【子任务】 一共有

50 个测试点,每个测试点

2 分.你只有在答案完全正确时才能得到该测试 点的全部分数,否则不得分. 对于所有测试点,以及对于样例,1 ≤ T ≤ 100,

1 ≤ n ≤ 44.对于每个测试点,n 的 范围如下表: 第3页共10 页IOI

2018 中国国家集训队集中培训 第二试 小Y和地铁(metro) 测试点编号

1 ≤ n ≤ 测试点编号

1 ≤ n ≤

1 2

26 32

2 3

27 33

3 4

28 33

4 5

29 34

5 6

30 34

6 8

31 35

7 9

32 35

8 10

33 36

9 11

34 36

10 12

35 37

11 13

36 37

12 14

37 38

13 15

38 38

14 16

39 39

15 17

40 39

16 20

41 40

17 22

42 40

18 24

43 41

19 26

44 41

20 28

45 42

21 30

46 42

22 30

47 43

23 31

48 43

24 31