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

1 输入】

2 5

3 0

0 2

0 2

2 0

2 1

1 1

3 10

3 10

1 3

10 3

20 1

3 10

3 30

3 1

0 0

100 0

1000 0

1 3

10 3

1000000000 【样例

1 输出】

6 11

16 1000001 第3页共10 页IOI

2018 中国国家集训队集中培训 第四试 我的生命已如风中残烛(game) 【样例 2】 见选手目录下的 game/game2.in 与game/game2.ans. 【样例

2 解释】 为了选手的身体健康,可怜决定临时加上一个大样例.但是因为是 IOI 赛制,可怜 不想让大样例太强. 大样例如下图所示: 其中两种颜色的'

'

点'

'

分别表示钉子和询问.为什么询问看起来像是一个点呢,因 为每一个询问都是长度为

1 的线段,而坐标范围又很大,所以看起来就是一个点啦. 不难发现每一个询问的答案都是 1. 【子任务】 对于前 10% 的数据,n ≤ 2. 对于前 20% 的数据,n ≤ 3. 对于前 30% 的数据,n ≤ 10. 对于前 60% 的数据,n ≤ 100,m ≤ 100. 对于 100% 的数据,1 ≤ n ≤ 500,1 ≤ m ≤ 500,1 ≤ T ≤ 10. 对于 100% 的数据,0 ≤ |xi|, |yi|, |sxi|, |syi|, |txi|, |tyi| ≤

104 ,1 ≤ Li ≤

109 . 第4页共10 页IOI

2018 中国国家集训队集中培训 第四试 榕树之心(core) 榕树之心(core) 【题目背景】 深秋.冷风吹散了最后一丝夏日的暑气,也吹落了榕树脚下灌木丛的叶子.相识数 年的 Evan 和Lyra 再次回到了小时候见面的茂盛榕树之下.小溪依旧,石桥依旧,榕 树虽是历经荣枯更迭,依旧亭亭如盖,只是 Evan 和Lyra 再也不是七八年前不经世事 的少年了. '

'

已经快是严冬了,榕树的叶子还没落呢. '

'

榕树是常绿树,是看不到明显的落叶季节的. '

'

唉.想不到已经七年了呢. 榕树还是当年的榕树, 你却不是当年的你了. '

'

其实又有什么是一成不变的呢,榕树常绿,翠绿树冠的宏观永恒,是由无数细小 树叶的荣枯更迭组成的.在时间的流逝中一切都在不断变化着呢. '

'

但你看这榕树,日日如此,季季如此,年年如此,仿佛亘古不变般,盘根错节,郁 郁葱葱.我在想,或许成为一棵树更好吧,任时间从枝叶间流过,我只守这一片绿荫就 好. '

'

榕树固然长久,但在这无限的时光里,终归是要湮灭于尘土的.与其像榕树一般, 植根于一方泥土中感受年复一年的四季更替.倒不如在有限的时间里看过尽可能多的 世界吧.再说了,榕树虽生长缓慢,却依旧会在每年春天抽出一根新的枝条去向外探索 的呢. '

'

真的吗,榕树在她漫长的一生里,就是这样往外一步步探索的吗? '

'

毕竟就算树冠看起来一成不变,榕树也会随着时间周期变化,春天到了自然就是 生长的时候了,她也应当做出对应的表现吧. '

'

相比于对季节更替做出本能的生长,我倒宁愿相信,榕树有一颗活跃的的,探索 的心. '

'

其实榕树是有心的,榕树刚刚种下的时候,心就在根的地方发芽了.以后每年春 天榕树长出新枝条的时候,心就会向着新枝条的方向移动一点,这样就能更靠近外面 的世界了.你看这头顶上的枝条,纵横交错,其实心已经在这枝杈间,移动了数十载了 呢. '

'

哇,也就是说,这密密麻麻的树杈中的某个地方,藏着这棵榕树的心吗? '

'

没错,可是要知道它在哪,就得另花一番功夫了. '