题目详情题解（0）讨论（0）提交记录（0）

AT_abc413_e.[ABC413E] Reverse 2^i

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个 $ (1,2,3,\ldots,2^{N}) $ 的排列 $ P=(P_0,P_1,\ldots,P_{2^{N}-1}) $。

你可以进行如下操作任意次（也可以一次都不做）：

  • 选择满足 $ 0\leq a\times 2^{b} < (a+1)\times 2^{b} \leq 2^{N} $ 的非负整数 $ a,b $，将 $ P_{a\times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1)\times 2^{b}-1} $ 反转。这里，反转指的是将 $ P_{a\times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1)\times 2^{b}-1} $ 同时替换为 $ P_{(a+1)\times 2^{b}-1}, P_{(a+1)\times 2^{b}-2},\ldots,P_{a\times 2^{b}} $。

请你求出通过若干次操作后，能得到的 $ P $ 的字典序最小的排列。

有 $ T $ 组测试数据，请分别输出每组的答案。

输入格式

输入通过标准输入给出，格式如下：

$ T $ $ \textrm{case}_1 $ $ \textrm{case}_2 $ $ \vdots $ $ \textrm{case}_T $

其中 $ \textrm{case}_i $ 表示第 $ i $ 个测试用例，格式如下：

$ N $ $ P_0 $ $ P_1 $ $ \ldots $ $ P_{2^N-1} $

输出格式

输出 $ T $ 行。第 $ i $ 行输出第 $ i $ 个测试用例的答案。

输入输出样例

  • 输入#1

    4
1
1 2
2
1 3 4 2
2
2 3 4 1
3
8 3 4 2 1 5 7 6

    输出#1

    1 2
1 3 2 4
1 4 2 3
1 5 6 7 2 4 3 8

说明/提示

数据范围

  • $ 1\leq T\leq 10^{5} $
  • $ 1\leq N\leq 18 $
  • $ P $ 是 $ (1,2,3,\ldots,2^{N}) $ 的一个排列
  • 对于每个输入文件，所有测试用例的 $ 2^N $ 之和不超过 $ 3\times 10^{5} $
  • 输入均为整数

样例解释 1

对于第 $ 1 $ 个测试用例，如果对 $ P $ 不进行任何操作，则 $ P=(1,2) $，这是字典序最小的排列。因此答案为 $ (1,2) $。

对于第 $ 2 $ 个测试用例，选择 $ a=1,b=1 $ 进行操作后，$ P=(1,3,2,4) $。无论对 $ P $ 进行多少次操作，都无法得到比 $ (1,3,2,4) $ 更小的排列。因此答案为 $ (1,3,2,4) $。

对于第 $ 3 $ 个测试用例，按如下顺序操作可以得到 $ P=(1,4,2,3) $：

  • 选择 $ a=0,b=1 $ 进行操作，$ P=(3,2,4,1) $。
  • 选择 $ a=0,b=2 $ 进行操作，$ P=(1,4,2,3) $。
    无论对 $ P $ 进行多少次操作，都无法得到比 $ (1,4,2,3) $ 更小的排列。因此答案为 $ (1,4,2,3) $。

由 ChatGPT 4.1 翻译

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

首页