P4461 [CQOI2018]九连环

    • 339通过
    • 1K提交
  • 题目提供者 Xeonacid
  • 评测方式 云端评测
  • 标签 快速傅里叶变换,DFT,FFT 搜索 各省省选 2018 重庆
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    九连环是一种源于中国的传统智力游戏。如图所示,九个的圆环套在一把“剑”上,并且互相牵连。游戏的目标是把九个圆环全部从“剑”上卸下。

    题目描述

    圆环的装卸需要遵守两个规则:

    1. 第一个(最右边) 环任何时候都可以任意装上或卸下

    2. 如果第k 个环没有被卸下,且第k 个环右边的所有环都被卸下,则第k+1个环(第k 个环左边相邻的环) 可以任意装上或卸下

    与魔方的千变万化不同,解九连环的最优策略是唯一的。为简单起见,我们以“四连环”为例,演示这一过程。这里用1表示环在“剑”上,0 表示环已经卸下。

    初始状态为1111,每步的操作如下:

    1. 1101 (根据规则2,卸下第2 个环)

    2. 1100 (根据规则1,卸下第1 个环)

    3. 0100 (根据规则2,卸下第4 个环)

    4. 0101 (根据规则1,装上第1 个环)

    5. 0111 (根据规则2,装上第2 个环)

    6. 0110 (根据规则1,卸下第1 个环)

    7. 0010 (根据规则2,卸下第3 个环)

    8. 0011 (根据规则1,装上第1 个环)

    9. 0001 (根据规则2,卸下第2 个环)

    10. 0000 (根据规则1,卸下第1 个环)

    由此可见,卸下“四连环”至少需要10 步。随着环数增加,需要的步数也会随之增多。例如卸下九连环,就至少需要341步。

    请你计算,有n 个环的情况下,按照规则, 全部卸下至少需要多少步。

    输入输出格式

    输入格式:

    输入文件第一行,为一个整数m,表示测试点数目。

    接下来m行,每行一个整数n。

    输出格式:

    输出文件共m行,对应每个测试点的计算结果。

    输入输出样例

    输入样例#1: 复制
    3
    3
    5
    9
    输出样例#1: 复制
    5
    21
    341

    说明

    对于10%的数据,$1≤n≤10$

    对于30%的数据,$1≤n≤30$

    对于100%的数据,$1≤n≤10^5,1≤m≤10$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。