CF2261H.Oh Tree Tree Tree, No Need to Leave
NOI/NOI+/CTSC
通过率:0%
时间限制:3.00s
内存限制:512MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
This is a communication problem.
There are two players: Player A (Isabel) and Player B (Tara). The jury will first interact with player A. After player A ends their interaction, the jury will interact with player B. Note that player A and player B may not directly pass information to each other; both players are only able to send information or receive information from the jury, but they may agree on the strategy they will use to communicate.
Isabel wants to send Tara a binary string b, which has size n. She can send information using a complete binary tree of exactly 2h−1 nodes, where h is a given positive integer that represents the height of the tree. The nodes have been labelled with integers from 1 to 2h−1, such that node 1 is the root, and for any non-leaf node v its left child is node 2v and its right child is node 2v+1.
Isabel writes a binary value (0 or 1) on each node of the tree. After she writes a value on each node, she sends the final tree to Tara.
However, Lord Verity (their nemesis), will try to ruin their communication attempt. After Isabel sets the value of each node, Lord Verity will perform the following actions in the order they are listed, exactly once:
1. He chooses some node u.
2. He flips the value that Isabel wrote on node u. Specifically, if Isabel wrote 0 on node u, he flips it to 1, and vice versa.
3. If node u is a leaf, he does nothing else. Otherwise, he swaps node u's child pointers. Specifically, u's left child becomes its right and u's right child becomes its left simultaneously. Then, all nodes are re-labelled such that node 1 is the root and for any non-leaf node v, its left child has label 2v and its right child has label 2v+1.

Note that Lord Verity's actions may be adaptive. This means that the node he chooses to mess with is not fixed at the start, and may depend on what Isabel writes on her tree.
After Lord Verity messes with the tree, Tara will receive the structure of the new binary tree, and the value written on each node. She does not know which node Lord Verity has messed with. Formally, she receives a new binary string l, where lu is the value written on node u after all nodes were re-labelled.
Her task is to compute the original string b.
There are only two possible combinations of n and h:
- n=1,h=2
- n=2030,h=11
The first combination will only be tested in the examples, for which a correct strategy is provided.
这是一个通信问题。
有两个玩家:玩家 A(伊莎贝尔)和玩家 B(塔拉)。裁判首先与玩家 A 交互;在玩家 A 完成其交互后,裁判再与玩家 B 交互。注意,玩家 A 和玩家 B 不能直接互相传递信息;双方都只能向裁判发送信息或从裁判处接收信息,但他们可以事先约定将采用的通信策略。
伊莎贝尔希望向塔拉发送一个长度为 n 的二进制字符串 b。她使用一棵恰好包含 2h−1 个节点的满二叉树来传递信息,其中 h 是给定的正整数,表示该树的高度。树中各节点被标号为 1 至 2h−1,满足:节点 1 为根节点;对任意非叶节点 v,其左子节点编号为 2v,右子节点编号为 2v+1。
伊莎贝尔在树的每个节点上写入一个二进制值(0 或 1)。在所有节点均被赋值后,她将最终的整棵树发送给塔拉。
然而,他们的宿敌——维里蒂勋爵(Lord Verity)将试图破坏此次通信。在伊莎贝尔完成所有节点赋值后,维里蒂勋爵将严格按照如下顺序、且仅执行一次以下操作:
-
他选择某个节点 u;
-
他翻转伊莎贝尔在节点 u 上所写的值:若原值为 0,则变为 1;若原值为 1,则变为 0;
-
若节点 u 是叶节点,则他不再进行其他操作;否则,他交换节点 u 的左右子指针(即:u 的左子节点变为其右子节点,u 的右子节点变为其左子节点),同时对整棵树重新标号,使得:新树的根节点编号为 1,且对任意非叶节点 v,其左子节点编号为 2v,右子节点编号为 2v+1。

注意:维里蒂勋爵的操作可能是自适应的,即他所选择的扰动节点 u 并非预先固定,而可能依赖于伊莎贝尔在树上所写的具体取值。
在维里蒂勋爵干扰完毕后,塔拉将收到这棵新二叉树的结构以及每个节点上的取值。但她不知道维里蒂勋爵具体扰动了哪一个节点。形式化地,她收到一个新的二进制字符串 l,其中 lu 表示在全部重新标号之后,节点 u 上所写的值。
她的任务是据此还原出原始字符串 b。
仅有如下两种可能的 (n,h) 组合:
- n=1,h=2
- n=2030,h=11
第一种组合仅用于样例测试,且题目中已提供一种正确策略。
输入格式
Your code will be ran exactly two times on each test. On the first run, you will be Isabel, and on the second Tara.
First Run Input
The first line of the input contains the string first. The purpose of this is so your program recognizes that this is its first run, and it should act as Isabel.
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤1024). The description of the test cases follows.
The first line of each test case contains two integers n and h (n=1 and h=2, or n=2030 and h=11) – the size of the string b and the height of the binary tree respectively. Note that the combination n=1 and h=2 only appears in the examples, and not in the main tests.
The next line contains a single binary string of size n, representing b.
Second Run Input
The first line of the input contains the string second. The purpose of this is so your program recognizes that this is its second run, and it should act as Tara.
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤1024). The description of the test cases follows. Note that this number is equal to t from the first run input.
The first line of each test case contains exactly two integers n and h — the size of the binary string b and the height of the corresponding tree. The test cases may appear in a different order than in the first run.
The second line of each test case contains a binary string of length 2h−1, whose characters are l1,l2,…,l2h−1. Here, li represents the value of the node with label i, which is determined according to both Isabel's and Lord Verity's actions.
Note that after Lord Verity's actions, the labels will differ from the labels Isabel used.
Hacks
To make hacks, use the following format.
The first line contains a single integer t (1≤t≤1024) — the number of test cases.
The first line of each test case contains three integers n, h and p (n=2030, h=11, 1≤p≤2h−1) — the size of the string b, the height of the tree, and the label of the node Lord Verity chooses. The label p refers to the labelling of the tree as Isabel wrote it, before Lord Verity's actions.
The second line of each test case contains a binary string b of size n — the string Isabel has to send.
Note that in hacks Lord Verity is not adaptive: he always chooses node p, regardless of what Isabel writes.
你的代码将在每个测试用例上恰好运行两次:第一次运行时,你扮演 Isabel;第二次运行时,你扮演 Tara。
第一次运行的输入
输入的第一行包含字符串 first。其作用是让程序识别出这是第一次运行,因此应以 Isabel 的身份行动。
每个测试包含多个测试用例。第一行包含测试用例数量 t(1≤t≤1024)。随后是各测试用例的描述。
每个测试用例的第一行包含两个整数 n 和 h(取值为:n=1 且 h=2,或 n=2030 且 h=11)——分别表示二进制字符串 b 的长度和对应二叉树的高度。注意:组合 n=1 且 h=2 仅出现在样例中,不会出现在主测试数据中。
接下来一行包含一个长度为 n 的二进制字符串,表示 b。
第二次运行的输入
输入的第一行包含字符串 second。其作用是让程序识别出这是第二次运行,因此应以 Tara 的身份行动。
每个测试包含多个测试用例。第一行包含测试用例数量 t(1≤t≤1024)。随后是各测试用例的描述。注意:该数值与第一次运行输入中的 t 相同。
每个测试用例的第一行恰好包含两个整数 n 和 h —— 分别表示二进制字符串 b 的长度和对应树的高度。测试用例的顺序可能与第一次运行中的顺序不同。
每个测试用例的第二行包含一个长度为 2h−1 的二进制字符串,其字符为 l1,l2,…,l2h−1。其中,li 表示编号为 i 的节点的值,该编号由 Isabel 和 Lord Verity 的操作共同决定。
注意:在 Lord Verity 执行操作之后,节点编号将不同于 Isabel 原先使用的编号。
Hack 数据格式
要构造 Hack 数据,请使用以下格式:
第一行包含一个整数 t(1≤t≤1024)—— 测试用例的数量。
每个测试用例的第一行包含三个整数 n、h 和 p(n=2030,h=11,1≤p≤2h−1)—— 分别表示字符串 b 的长度、树的高度,以及 Lord Verity 所选择的节点编号。编号 p 指的是 Isabel 初始写下的树编号(即 Lord Verity 操作前的编号)。
每个测试用例的第二行包含一个长度为 n 的二进制字符串 b —— 这是 Isabel 需要发送的字符串。
注意:在 Hack 数据中,Lord Verity 的行为是非自适应的:他总是选择编号为 p 的节点,而不管 Isabel 写下什么内容。
输出格式
First Run Output
For each test case, output a binary string of length 2h−1, where the i-th character represents the value Isabel sets for node with label i.
Second Run Output
For each test case, output a binary string of size n, which is Tara's guess as to what b is equal to.
首次运行输出
对于每个测试用例,输出一个长度为 2h−1 的二进制字符串,其中第 i 个字符表示伊莎贝尔为标签为 i 的节点所设置的值。
第二次运行输出
对于每个测试用例,输出一个长度为 n 的二进制字符串,即塔拉对 b 取值的猜测。
输入输出样例
输入#1
first 2 1 2 0 1 2 1
输出#1
000 101
输入#2
second 2 1 2 010 1 2 001
输出#2
1 0
说明/提示
When n=1, a correct strategy is the following.
Isabel wants to send 1 bit but she has 2h−1=22−1=3 nodes available. Since Lord Verity only flips the value written on a single node, a correct strategy is to write the same value b1 on all nodes of the tree. Then, Tara outputs the most frequent value that appears in l.
Take a look at the examples. Note that the order the test cases appear in the first run is not necessarily the same as the order they appear in the second run. Here, the two test cases have been swapped.
Isabel and Tara use the aforementioned strategy only for the case b=0: Isabel writes the value 0 on all nodes of the tree, so she outputs 000. Then, Lord Verity uses his operation on node with label 3 and Tara receives l=001. Since 0 is the most frequent value in l, she outputs 0.
The other case where b=1 is used only to show how Lord Verity's action affects the tree. Specifically, Isabel chooses to write the value 0 on node 2 and the value 1 on nodes 1 and 3. Then, Lord Verity chooses to use his operation on node 1. First, the value written on node 1 becomes 0. Then, its two children are swapped, and they are re-labelled: node 2 gets label 3 and node 3 gets label 2. Therefore we get l=010. Magically, Tara can correctly determine that b=1.
IMPORTANT NOTE: In these examples, Lord Verity chose to operate on nodes 1 and 3. However, when your code runs on the examples, it is not guaranteed that Lord Verity chooses the same nodes, and therefore using the same output as the examples is not guaranteed to be correct.
当 n=1 时,一种正确的策略如下。
伊莎贝尔希望发送 1 位信息,但她有 2h−1=22−1=3 个节点可用。由于真实大人(Lord Verity)仅翻转单个节点上所写数值,一种正确策略是:将相同的值 b1 写入树的所有节点。随后,塔拉(Tara)输出 l 中出现频率最高的值。
请参看示例。注意:第一次运行中测试用例的出现顺序不一定与第二次运行中的顺序相同。此处,两个测试用例已被交换。
伊莎贝尔和塔拉仅在 b=0 的情形下使用上述策略:伊莎贝尔将值 0 写入树的所有节点,因此她输出 000。接着,真实大人对其标签为 3 的节点执行操作,塔拉收到 l=001。由于 0 是 l 中最常出现的值,她输出 0。
另一种情形 b=1 仅用于说明真实大人的操作如何影响该树。具体而言,伊莎贝尔选择在节点 2 上写入值 0,而在节点 1 和 3 上写入值 1。随后,真实大人选择对节点 1 执行操作:首先,节点 1 上的值变为 0;然后,其两个子节点被交换,并重新标号:原节点 2 获得新标签 3,原节点 3 获得新标签 2。因此最终得到 l=010。神奇的是,塔拉能正确推断出 b=1。
重要提示:在这些示例中,真实大人选择操作的节点是 1 和 3。然而,当您的代码在这些示例上运行时,不能保证真实大人会选择相同的节点,因此直接照搬示例的输出不能保证正确。
输入解题思路,AI测评打分。不知道怎么写?