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 bb, which has size nn. She can send information using a complete binary tree of exactly 2h−12^h-1 nodes, where hh is a given positive integer that represents the height of the tree. The nodes have been labelled with integers from 11 to 2h−12^h-1, such that node 11 is the root, and for any non-leaf node vv its left child is node 2v2v and its right child is node 2v+12v+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 uu.

2. He flips the value that Isabel wrote on node uu. Specifically, if Isabel wrote 0 on node uu, he flips it to 1, and vice versa.

3. If node uu is a leaf, he does nothing else. Otherwise, he swaps node uu's child pointers. Specifically, uu's left child becomes its right and uu's right child becomes its left simultaneously. Then, all nodes are re-labelled such that node 11 is the root and for any non-leaf node vv, its left child has label 2v2v and its right child has label 2v+12v+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 ll, where lul_u is the value written on node uu after all nodes were re-labelled.

Her task is to compute the original string bb.

There are only two possible combinations of nn and hh:

  • n=1,h=2n = 1, h = 2
  • n=2030,h=11n = 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 不能直接互相传递信息;双方都只能向裁判发送信息或从裁判处接收信息,但他们可以事先约定将采用的通信策略。

伊莎贝尔希望向塔拉发送一个长度为 nn 的二进制字符串 bb。她使用一棵恰好包含 2h−12^h-1 个节点的满二叉树来传递信息,其中 hh 是给定的正整数,表示该树的高度。树中各节点被标号为 11 至 2h−12^h-1,满足:节点 11 为根节点;对任意非叶节点 vv,其左子节点编号为 2v2v,右子节点编号为 2v+12v+1。

伊莎贝尔在树的每个节点上写入一个二进制值(0 或 1)。在所有节点均被赋值后,她将最终的整棵树发送给塔拉。

然而,他们的宿敌——维里蒂勋爵(Lord Verity)将试图破坏此次通信。在伊莎贝尔完成所有节点赋值后,维里蒂勋爵将严格按照如下顺序、且仅执行一次以下操作:

  1. 他选择某个节点 uu;

  2. 他翻转伊莎贝尔在节点 uu 上所写的值:若原值为 0,则变为 1;若原值为 1,则变为 0;

  3. 若节点 uu 是叶节点,则他不再进行其他操作;否则,他交换节点 uu 的左右子指针(即:uu 的左子节点变为其右子节点,uu 的右子节点变为其左子节点),同时对整棵树重新标号,使得:新树的根节点编号为 11,且对任意非叶节点 vv,其左子节点编号为 2v2v,右子节点编号为 2v+12v+1。

注意:维里蒂勋爵的操作可能是自适应的,即他所选择的扰动节点 uu 并非预先固定,而可能依赖于伊莎贝尔在树上所写的具体取值。

在维里蒂勋爵干扰完毕后,塔拉将收到这棵新二叉树的结构以及每个节点上的取值。但她不知道维里蒂勋爵具体扰动了哪一个节点。形式化地,她收到一个新的二进制字符串 ll,其中 lul_u 表示在全部重新标号之后,节点 uu 上所写的值。

她的任务是据此还原出原始字符串 bb。

仅有如下两种可能的 (n,h)(n, h) 组合:

  • n=1,h=2n = 1, h = 2
  • n=2030,h=11n = 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 tt (1≤t≤10241 \le t \le 1024). The description of the test cases follows.

The first line of each test case contains two integers nn and hh (n=1n = 1 and h=2h = 2, or n=2030n = 2030 and h=11h = 11) – the size of the string bb and the height of the binary tree respectively. Note that the combination n=1n = 1 and h=2h = 2 only appears in the examples, and not in the main tests.

The next line contains a single binary string of size nn, representing bb.

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 tt (1≤t≤10241 \le t \le 1024). The description of the test cases follows. Note that this number is equal to tt from the first run input.

The first line of each test case contains exactly two integers nn and hh — the size of the binary string bb 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−12^h-1, whose characters are l1,l2,…,l2h−1l_1, l_2, \ldots, l_{2^h-1}. Here, lil_i represents the value of the node with label ii, 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 tt (1≤t≤10241 \le t \le 1024) — the number of test cases.

The first line of each test case contains three integers nn, hh and pp (n=2030n = 2030, h=11h = 11, 1≤p≤2h−11 \le p \le 2^h-1) — the size of the string bb, the height of the tree, and the label of the node Lord Verity chooses. The label pp 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 bb of size nn — the string Isabel has to send.

Note that in hacks Lord Verity is not adaptive: he always chooses node pp, regardless of what Isabel writes.

你的代码将在每个测试用例上恰好运行两次:第一次运行时,你扮演 Isabel;第二次运行时,你扮演 Tara。

第一次运行的输入

输入的第一行包含字符串 first。其作用是让程序识别出这是第一次运行,因此应以 Isabel 的身份行动。

每个测试包含多个测试用例。第一行包含测试用例数量 tt(1≤t≤10241 \le t \le 1024)。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 nn 和 hh(取值为:n=1n = 1 且 h=2h = 2,或 n=2030n = 2030 且 h=11h = 11)——分别表示二进制字符串 bb 的长度和对应二叉树的高度。注意:组合 n=1n = 1 且 h=2h = 2 仅出现在样例中,不会出现在主测试数据中。

接下来一行包含一个长度为 nn 的二进制字符串,表示 bb。

第二次运行的输入

输入的第一行包含字符串 second。其作用是让程序识别出这是第二次运行,因此应以 Tara 的身份行动。

每个测试包含多个测试用例。第一行包含测试用例数量 tt(1≤t≤10241 \le t \le 1024)。随后是各测试用例的描述。注意:该数值与第一次运行输入中的 tt 相同。

每个测试用例的第一行恰好包含两个整数 nn 和 hh —— 分别表示二进制字符串 bb 的长度和对应树的高度。测试用例的顺序可能与第一次运行中的顺序不同。

每个测试用例的第二行包含一个长度为 2h−12^h-1 的二进制字符串,其字符为 l1,l2,…,l2h−1l_1, l_2, \ldots, l_{2^h-1}。其中,lil_i 表示编号为 ii 的节点的值,该编号由 Isabel 和 Lord Verity 的操作共同决定。

注意:在 Lord Verity 执行操作之后,节点编号将不同于 Isabel 原先使用的编号。

Hack 数据格式

要构造 Hack 数据,请使用以下格式:

第一行包含一个整数 tt(1≤t≤10241 \le t \le 1024)—— 测试用例的数量。

每个测试用例的第一行包含三个整数 nn、hh 和 pp(n=2030n = 2030,h=11h = 11,1≤p≤2h−11 \le p \le 2^h-1)—— 分别表示字符串 bb 的长度、树的高度,以及 Lord Verity 所选择的节点编号。编号 pp 指的是 Isabel 初始写下的树编号(即 Lord Verity 操作前的编号)。

每个测试用例的第二行包含一个长度为 nn 的二进制字符串 bb —— 这是 Isabel 需要发送的字符串。

注意:在 Hack 数据中,Lord Verity 的行为是非自适应的:他总是选择编号为 pp 的节点,而不管 Isabel 写下什么内容。

输出格式

First Run Output

For each test case, output a binary string of length 2h−12^h-1, where the ii-th character represents the value Isabel sets for node with label ii.

Second Run Output

For each test case, output a binary string of size nn, which is Tara's guess as to what bb is equal to.

首次运行输出

对于每个测试用例,输出一个长度为 2h−12^h-1 的二进制字符串,其中第 ii 个字符表示伊莎贝尔为标签为 ii 的节点所设置的值。

第二次运行输出

对于每个测试用例,输出一个长度为 nn 的二进制字符串,即塔拉对 bb 取值的猜测。

输入输出样例

  • 输入#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=1n=1, a correct strategy is the following.

Isabel wants to send 11 bit but she has 2h−1=22−1=32^h-1=2^2-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 b1b_1 on all nodes of the tree. Then, Tara outputs the most frequent value that appears in ll.

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=0b = 0: Isabel writes the value 00 on all nodes of the tree, so she outputs 000000. Then, Lord Verity uses his operation on node with label 33 and Tara receives l=001l = 001. Since 00 is the most frequent value in ll, she outputs 00.

The other case where b=1b = 1 is used only to show how Lord Verity's action affects the tree. Specifically, Isabel chooses to write the value 00 on node 22 and the value 11 on nodes 11 and 33. Then, Lord Verity chooses to use his operation on node 11. First, the value written on node 11 becomes 00. Then, its two children are swapped, and they are re-labelled: node 22 gets label 33 and node 33 gets label 22. Therefore we get l=010l = 010. Magically, Tara can correctly determine that b=1b = 1.

IMPORTANT NOTE: In these examples, Lord Verity chose to operate on nodes 11 and 33. 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=1n=1 时,一种正确的策略如下。

伊莎贝尔希望发送 11 位信息,但她有 2h−1=22−1=32^h-1=2^2-1=3 个节点可用。由于真实大人(Lord Verity)仅翻转单个节点上所写数值,一种正确策略是:将相同的值 b1b_1 写入树的所有节点。随后,塔拉(Tara)输出 ll 中出现频率最高的值。

请参看示例。注意:第一次运行中测试用例的出现顺序不一定与第二次运行中的顺序相同。此处,两个测试用例已被交换。

伊莎贝尔和塔拉仅在 b=0b = 0 的情形下使用上述策略:伊莎贝尔将值 00 写入树的所有节点,因此她输出 000000。接着,真实大人对其标签为 33 的节点执行操作,塔拉收到 l=001l = 001。由于 00 是 ll 中最常出现的值,她输出 00。

另一种情形 b=1b = 1 仅用于说明真实大人的操作如何影响该树。具体而言,伊莎贝尔选择在节点 22 上写入值 00,而在节点 11 和 33 上写入值 11。随后,真实大人选择对节点 11 执行操作:首先,节点 11 上的值变为 00;然后,其两个子节点被交换,并重新标号:原节点 22 获得新标签 33,原节点 33 获得新标签 22。因此最终得到 l=010l = 010。神奇的是,塔拉能正确推断出 b=1b = 1。

重要提示:在这些示例中,真实大人选择操作的节点是 11 和 33。然而,当您的代码在这些示例上运行时,不能保证真实大人会选择相同的节点,因此直接照搬示例的输出不能保证正确。

输入解题思路,AI测评打分。不知道怎么写?

首页