2024年国际信息学奥林匹克竞赛（IOI）试题

THE 36"INTERNATIONAL nile ALEXANdrIA OLYMPIAD IN INFORMATICS Day 1 Tasks EGHPT 202H Chinese (CHN) 尼罗河船运(nile) 你想通过尼罗河来运输N件手工艺品。这些手工艺品从0到N-1编号。第i(0<i<N)件手工艺 品的重量是W[i]。 为了运输这些手工艺品,你使用了特制的船。每艘船最多可以运两件手工艺品。 如果你决定将单件手工艺品放在一艘船上,那么这件手工艺品的重量可以是任意的。 · 如果你想把两件手工艺品一起放在同一艘船上,你必须保证这艘船的平衡。具体来说,如果手工艺 品p和q(0<p<q<N)的重量差的绝对值不超过D,即满足W[pl-W[qll<D,那么你可 以将它们一起放在同一艘船上。 你必须付费来运一件手工艺品,其运费取决于同一艘船上所运载的手工艺品数量。手工艺品 (0<i<N)的运费是: · Ai,如果你把手工艺品i单独放在船上,或者 Bi,如果你把手工艺品i和另一件手工艺品一起放在船上。 注意在第二种情况中,你要为船上两件手工艺品都支付运费。具体来说,如果你决定用同一艘船运输手工 艺品p和q(0<p<q<N),你需要支付Bp]+B[q]。 一件手工艺品单独用一艘船运输的费用,总是比与其他手工艺品合用一嫂船时的费用要高,所以对任意满 足0<i<N的i,都有B]<Ai]。 麻烦的是,由于尼罗河变化莫测,导致D的值经常改变。你的任务是回答Q个问题,从0到Q一1编 号。这些问题用一个长度为Q的数组E来描述。问题i(0<j<Q)的答案,是在D的值等于Ei 时运输所有N件手工艺品的最小总代价。 实现细节 你需要实现以下函数。 std: :vector<long long> calculate costs( std::vector<int>W, std::vector<int> A. std::vector<int> B, std::vector<int> E) · W,A,B:长度均为N的整数数组,分别给出手工艺品的重量和运费 · E:长度为O的整数数组,给出每个问题中的D值。 nile(1of3) · 该函数应该返回一个包含Q个整数的数组R,给出运输手工艺品的最小总代价,其中Ril对应D 等于Ej](对每个满足0<j<Q的j)时的运费。 ·对于每个测试用例,该函数恰好被调用一次。 约束条件 · 1<N<100000 ·1<Q<100000 · 对每个满足0<i<N的i,都有1<Wlil<10 · 对每个满足0<i<N的i,都有1<B[]<A]<10{ ·对每个满足0<j<Q的j,都有1<Ej]<10 子任务 子任务 分数 额外的约束条件 6 1 Q<5;N<2000;对每个满足0<i<N的i,都有W[]=1 13 Q<5;对每个满足0<i<N的i,都有Wlil=i+1 3 $7 Q<5;对每个满足0<i<N的i,都有Al]-2且B]-1 4 11 Q<5;V<2000 5 20 Q<5 15 6 对每个满足0<i<N的i,都有Ai]=2且Bi]=1 7 18 没有额外的约束条件。 例子 考虑以下调用。 calculatecosts([15,12,2,10,21]. [5,4,5,6,3], [1,2,2,3,2], [5.9,1]) 在该例子中,我们有N一5件手工艺品和Q一3个问题 在第一个问题中,D=5。你可以把手工艺品0和手工艺品3放在同一艘船上(因为15一10<5), 而其他手工艺品都各自放在不同的船上。这使得运输所有手工艺品的总代价最小,即 1+4+5+3+3-16。 在第二个问题中,D一9。你可以把手工艺品0和手工艺品1放在同一嫂船上(因为15-12<9), 而把手工艺品2和手工艺品3放在同一艘船上(因为2一10<9)。剩下的手工艺品单独用一嫂船运 nile (2of3) 输。这使得运输所有手工艺品的总代价最小,即1+2+2+3+3=11。 在最后一个问题中,D一1。你需要把每件手工艺品都单独用一艘船运输。这使得运输所有手工艺品的总 代价最小,即5+4+5+6+3=23。 因此,该函数应该返回[16,11.23]。 评测程序示例 输入格式: N w[]A[]B[o] W[1]A[1]B[1] _ W[N-1] A[N-1] B[N-1] 0 Ef] E[] ,_ E[Q-1] 输出格式: R[o] R[1] . R[S-1] 这里,S是calculate costs所返回的数组R的长度 nile(3of3) THE 36"INTERNATIONAL message ALEXANdFIA OLYMPIAD IN INFORMATICS Day 1 Tasks EGHDT 202H Chinese (CHN) 消息篡改者 (message) Aisha和Basma是两位互相通信的朋友。Aisha有一条消息M想要发给Basma:该消息是由S个比特 (即若干0或1)组成的序列。Aisha通过发送数据包来跟Basma通信。一个数据包是由31个比特组成 的序列,对应的位置从0到30编号。Aisha想向Basma发送消息M时,会发送若干数据包。 然而第三个人Cleopatra在破坏Aisha和Basma之间的通信,能够篡改发送的数据包。在每个数据包 中,Cleopatra可以修改恰好15个位置的比特。具体来说,给定长度为31的数组C,其中每个元素为0 或1,含义如下: · Clil一1表示位置为i的比特可以被Cleopatra修改。我们称此类位置是被Cleopatra控制的。 · C[i]一0表示位置为i的比特不能被Cleopatra修改。 数组C恰好包含15个1和16个0。当发送消息M时,Cleopatra控制的位置集合对于所有数据包都是 相同的。Aisha清楚地知道哪15个位置被Cleopatra控制。Basma只知道有15个位置被Cleopatra控 制,但不知道是哪些位置。 令A为Aisha决定要发送的数据包(称之为原始数据包)。令B为Basma收到的数据包(称之为篡改数 据包)。对每个在0<i<31的i都有: · 如果Cleopatra不能控制位置为i的比特(Cil一0),那么Basma将能收到Aisha发送的第i个 比特(B]一A]): 否则,如果Cleopatra控制了位置为i的比特(Ci]三1),那么Bil的值由Cleopatra决定。 每个数据包发送后,Aisha会立刻知道被篡改后的数据包内容。 当Aisha发送完所有数据包后,Basma按照发送顺序接收到所有被篡改的数据包,她必须重建原始消息 M。 你的任务是制定并实现某种策略,使得Aisha给Basma发送消息M时,Basma能够从篡改数据包中恢 复M。具体来说,你要实现两个函数,第一个函数进行Aisha的动作:给定消息M和数组C,给 Basma发送若干数据包来传输消息。第二个函数进行Basma的动作:给定若干篡改数据包,恢复原始消 息M。 实现细节 你要实现的第一个函数是 void send message(std::vector<bool> M, std::vector<bool> c) message (1of4) · M:长度为S的数组,描述Aisha想要发给Basma的消息。 · C:长度为31的数组,标记Cleopatra控制的数据包中的位置。 · 每个测试用例中,该函数最多可被调用2100次。 该函数调用以下函数来发送数据包 std::vector<bool> send packet(std: :vector<bool>A) · A:原始数据包(长度为31的数组),表示Aisha发送的比特。 此函数返回篡改数据包B,表示Basma接收到的比特。 · 此函数在send message的一次调用过程中最多被调用100次 你要实现的第二个函数是 std::vector<bool>receive message(std::vector<std::vector<bool>>R · R:描述若干篡改数据包的数组。这些数据包源自Aisha在一次send message调用时发送的若干 数据包,且按照Aisha的发送顺序排列。R的每个元素是长度为31的数组,表示一个篡改数据 包。 该函数应返回包含S个比特的数组,且与原始消息M相同。 · 每个测试用例中,该函数可能被调用多次。对于每次sendmessaae的调用,对应地该函数要有 恰好一次调用。函数receive message的调用顺序不必与对应的send messaqe调用顺序一 致。 注意在评测系统中,send messaae和receive messaae两个函数是在不同的程序中来调用的 约束条件 · 1<S<1024 · C恰好有31个元素,且其中16个为0,15个为1。 子任务与评分 如果在任意的测试用例中,函数sendpacket的调用不符合上述规则,或者某个函数 receive message的调用的返回值不正确,你的解答在该测试用例上得0分。 否则,令Q为所有测试用例中,每次sendmessage调用时调用函数sendpacket的次数的最大值。 令X等于: ·1,如果Q<66 . 0.95-66,如果66<Q<100 ·0,如果100<Q 那么,得分将由以下式子计算获得: message (2of4) 子任务 分数 额外的约束条件 1 $0·t $<64 2 90.X 没有额外的约束条件。 注意在某些测试用例中,评测程序的行为是自适应的。这意味着sendpacket的返回值可能取决于它的 输入参数和以前调用该函数的返回值。 例子 考虑以下调用. sendmessage([o,1,1, o], [,。,,,,,,⊙,,,:,,,。,, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]) Aisha试图发给Basma的消息是[0.1.1.0]。数据包的第0至第15个比特不能被Cleopatra修改,而第 16至第30个比特可以被Cleopatra修改。 为便于解释这个例子,我们假设Cleopatra的行为是确定性的:她交替地用0和1填充所控制的比特,也 就是她把她控制的第一个位置赋0(例子中的第16位),把她控制的第二个位置赋1(第17位),把她 控制的第三个位置赋0(第18位),以此类推。 Aisha可以做出的一种决定是在一个数据包中发送原始消息中的两个比特,例如她是这样做的:通过她控 制的前8个位置来发送第一个比特,通过她控制的接下来8个位置来发送第二个比特。 于是Aisha发送以下数据包 sendpacket([o,,,⊙,6,e,。,⊙,1,1,1,1,1,1,1,1, 。,,,,,,,,。,,,,,,]) 由于Cleopatra可以更改最后15个比特,所以Aisha决定随意设置它们,因为它们可能会被覆盖。使用 前面假定的Cleopatra的策略,该函数返回 0,0,0,0,0,0,0,0.1,1.1.1,1.1,1,1,0,1,0,1,0,1,0,10,10,1.0,1,0。 Aisha决定在第二个数据包中发送M的最后两个比特,与之前类似 send_packet([1,1,1,1,1,1,1,1,9,,,。,6,。,0,9, 0,。,,,,,⊙,⊙,,,,,,⊙,。]) 根据假定的Cleopatra的策略,该函数返回: message (3 of4) 1.1.1.1.1.1.1.1.0.0.0.0.0.0.0.0.0.1.0.1.0.1.0.1.0.1.0.1.0.10 Aisha还可以发送更多的数据包,但她没有这样做。 然后评测程序进行以下函数调用 receivemessage([[o,,,⊙,⊙,。,。,,1,1,1,1,1,1,1,1, 0,1,⊙,1,6,1,⊙,1, 。,1,。,1,。,1,], [1,1,1,1,1,1,1,1, 。,,⊙,, 9,1,⊙,1:⊙,1,⊙,1,⊙,1,⊙,1,⊙,1, )]) Basma按照如下方式恢复消息M。她从每个数据包中提取出第一个连续出现两次的比特,以及最后一个 连续出现两次的比特。也就是说,她从第一个数据包提取出两个比特[0.1,从第二个数据包中提取出两 个比特[1.0l。把它们放在一起,她恢复了消息[0.1.1.0],这是对receive message调用的正确返回 值。 可以证明,在假设的Cleopatra的策略下,对于长度为4的消息,不管C的值是多少,Basma这样做能 够正确恢复M。然而,一般情况下这并不正确。 评测程序示例 评测程序示例不具备自适应性,Cleopatra的行为是确定性的,她交替地用0和1来填充她控制的比特, 就像她在例子中所做的那样。 输入格式:输入第一行包含一个整数T,指定测试用例的数量。接下来有T组测试用例,每组测试用例都 按以下格式描述: S M[o] M[1] 1 M[S-1] c[]C[1]... C30] 输出格式:评测程序示例按照输入的顺序,用以下格式输出T组测试用例的结果 K. D[] 1 D[1] 1..D[L-1] 这里,K是sendpacket的调用次数,D是receivemessage返回的消息,L是它的长度。 messaoe (4 of 4 THE 36"INTERNATIONAL tree ALEXANdrIA OLYMPIAD IN INFORMATICS Day 1 Tasks EGUDT 202H Chinese (CHN) 树上代价(tree) 有一棵包括N个结点的树,结点从0到N一1编号。结点0是树的根。除根以外的每个结点都有唯一的 父结点。对所有满足1<i<N的i,结点i的父结点为Pl,这里有Pi]<i。我们约定P0l=-1。 对所有结点i(0<i<N),i的子树是如下结点组成的集合 .2,以及 · 所有父结点为i的结点,以及 · 所有父结点的父结点为i的结点,以及 · 所有父结点的父结点的父结点为i的结点,以及 · 以此类推。 下图给出了一个包含N一6个结点的树的例子。每个箭头都从某个结点连向它的父结点(根结点除外 因为它没有父结点)。结点2的子树包括结点2.3.4和5。结点0的子树包括树中的全部6个结点,而结 点4的子树仅包括结点4自己。 每个结点都被赋以非负整数的权重。我们将结点i(0<i<N)的权重记为Wil。 你的任务是写一个程序来回答Q个询问,其中每个询问都用一对正整数(L,R)来表示。对于询问的回 答,应按照如下要求进行计算。 对树中的每个结点,都指派一个整数,称为系数。这样的指派结果被描述成一个序列 Cl0].....C[N一1,这里Cli](0<i<N)是指派给结点i的系数。我们称该序列为-个系数序列 注意,系数序列中的元素可以取负值、0或正值。 对某个询问(L.R),一个系数序列被称为是有效的,如果对于每个结点i(0<i<N)都有如下条件成 立:结点i的子树中的系数之和不小于L且不大于R。 对于一个给定的系数序列C0.....C[N-1],结点i的代价为ClilI·W],这里Cill表示C[il的绝 对值。最后,总体代价为所有结点的代价之和。你的任务是,对于每个询问,计算出可以由某个有效系数 tree(1of4) 序列达到的最小总体代价 可以证明,对于任意询问,都至少存在一个有效的系数序列。 实现细节 你需要实现如下两个函数: void init(std::vector<int>P, std::vector<int>W) · P,W:两个长度为N的整数数组,记录了结点的父结点和权重。 · 对于每个测试样例,在评测程序与你的程序开始交互时,该函数将被恰好调用一次。 long long query(int L, int R) · L,R:两个整数,描述一次询问。 · 对于每个测试样例,在1nit被调用后,该函数将被调用Q次。 · 该函数应该返回对给定询问的答案。 约束条件 · 1<N<200000 ·1<Q<100000 · P0]=-1 对所有满足1<i<N的i,都有0<Pil<i 对所有满足0<i<N的i,都有0<Wlil<1000000 · 在每次询问中,都有1<L<R<1000000 子任务 子任务 分数 额外的约束条件 10 1 Q<10;对所有满足1<i<N的i,都有W[Plill<W[i] 2 13 Q<10; N<2000 3 18 Q<10;N<60000 4 _ 对所有满足0<i<N的i,都有W[il=1 1 对所有满足0<i<N的i,都有Wi]<1 6 22 1-1 7 19 没有额外的约束条件。 tree (2of 4) 例子 考虑如下调用: init([-1,),],[1,1,1]) 这棵树包含3个结点:根结点以及它的2个子结点。所有结点的权重均为1。 query(1,1) 本次询问有L三R=1,这意味着每个子树中的系数之和都必须等于1。考虑系数序列[-1.1.1l。这棵 树以及相应的系数(在阴影矩形中)图示如下。 #回 1① 2① 对每个结点i(0<i<3),i的子树中全部结点的系数之和均为1。因此,系数序列是有效的。总体代 价的计算如下: 结点 权重 系数 代价 1 0 -1 1-11-1 1 1 1 11|:1-1 2 1 1 11:1-1 因此总体代价为3。这是唯一的有效系数序列,因此调用应该返回3。 query(1,2) 对于该询问的最小总体代价为2,可以在系数序列为0.1.1时达到。 评测程序示例 输入格式: tree (3of4)