资源简介

UZBEKISTAN
ballmachine
Day 1 Tasks
IOI 2026 TASHKENT
Chinese(CHN)
弹球机
Madina发明了一台弹球机，以供参加IOI的人们娱乐。机器的内部构造是这样的：
·机器有N个结点，编号为从0到N一1。结点N一1被称作根。
·对每个结点u(0≤uu的某个结点P,而结点u则是
P叫的子结点。根结点没有父结点。没有子结点的结点被称为叶结点。
你不知道N以及各个结点u的父结点Pu。不过，Madina会告诉你叶结点的数量M,而这些叶结点
的编号为0,1，·，M一1。你的任务是，通过操作机器来确定它的内部构造。
机器的每个结点上最多可以放一个球，而且每个球都有一个非负整数值。如果某个结点上有值为心的球，
我们就说这个结点的值为x。某个结点上如果放了一个球，就称为是被占的；否则，它就是空的。在最开
始时，所有结点都是空的。
你可以做如下两种操作：
·insert(U,X):尝试把值为X的一个新球放到叶结点U处。
。如果叶结点U是被占的，该操作将返回false并且不会放上这个球。
。如果叶结点U是空的，这个球将会放到结点U上。接下来，这个球会不断地从当前所在结
点移向它的父结点，前提是父结点是空的。当遇到根结点或者某个结点的父结点已经被占，
移动就会停止。该操作将返回true。
·collect(0:如果根结点是空的（这意味着机器是空的），collect将返回一个空数组。否则，下面
所给出的递归函数traverse将收集当前机器中所有球的值，并且放进数组S。最初数组S是空
的，并且以调用traverse(N·l)开始。
traverse(u):
将结点u上的球的值追加到S的末尾
令c[u]为u的被占子结点的列表
根据c[u]上球的值，对c[u]进行非降排序（如果有多个结点的值相同，
它们可能会以任意顺序出现)
对于c[u]中的每个V:
traverse(v)
在该函数结束后，所有球都将被移出该机器，而collect则返回S。
ballmachine (1 of 6)
例如，设想有某台机器，它有N=7个结点，对应的父结点的数组为P=[4,6,5,5,6,6]。左图给出了
标有结点编号的空机器，而右图则给出了在某个1 nsert操作序列（该序列将在例子一节中给出）完成后
的可能状态。
6
5
20
10
20
在collect()被调用时，根结点（结点6）是被占的，所以S被初始化成S=[],而traverse(6)
将被调用。
traverse(6):结点6的值为0；将其追加到S并得到S=0。结点6的子结点是4,1和5，而且
全部都是被占的。它们的值分别是20,10和20。非降排序得到c6=[1,5,4(注意，c6=[1,4,5]
也是对的，因为结点4和5有相同的值)。该函数将根据这个排序，对c6]中的每个结点调用
traverse。
·traverse(1):结点1的值为10；将其追加到S将得到S=[0,10]。结点1没有被占的子结
点，因此该调用结束。
·traverse(5):结点5的值为20；将其追加到S将得到S=0,10,20]。结点5有一个被占的
子结点2，因此c5)=2而该函数将调用traverse(2)。
。traverse(2):结点2的值为30；将其追加到S将得到S=0,10,20,30]。结点2没有
被占的子结点，因此该调用结束。
。当前执行将返回到traverse(5),而它已经处理了c5]中的全部子结点，因此该调用结
束。
·traverse(4):结点4的值为20；将其追加到S将得到S=[0,10,20,30,20]。结点4没有被
占的子结点，所以该调用结束。
所有的调用结束，而且没有剩余结点需要处理。最终，所有球将被从机器中移出，而co1Lct将返回数
组S=0,10,20,30,20。
你的任务是确定结点数量N,并且给出能够刻画机器构造的父结点数组
R=[R0,1,,RN一2，不过那些中间结点（既非叶结点也非根结点）的编号方案可以有所不
同。形式化地来说，对于某个所给出的数组R,如果能够对机器中的各个结点赋以不同的编号[叫
(0≤L[uballmachine (2 of 6)

展开更多......

收起↑