luogu#P10038. 「FAOI-R2」Program of atom(x) 2027 (D)

    ID: 13999 远端评测题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>动态规划,dp2024洛谷原创提交答案Special JudgeO2优化区间 dp构造

「FAOI-R2」Program of atom(x) 2027 (D)

题目背景

这是来自 20272027 年的 FAOI 的一道题目,是一道带有 SPJ 的传统题。


自从 krjt 上次被 160160JC 后,他换了一个「量子密码锁」,并用它锁上了自己的电脑包——打不开密码锁,就取不出包里的电脑。理论上,一旦 krjt 忘了密码,就连造这把锁的人也打不开。

然而,这把锁并非固若金汤。有一天,krjt 突然对化学产生了浓厚的兴趣。他拿起那把锁,放在酒精灯上加热,结果发现: 在高温环境下,这把锁内的原子(严格来说是「离子」,下同)排布变得不稳定,这将导致它瘫痪。

题目描述

krjt 找来了密码锁的说明书:

在密码锁中,有一条长度为 nn(不能更改,nn 的具体取值见密码锁铭牌)的链,链上共有 nn 个结点。每个结点上可以存放至多一个原子。初始时,1,2,,n1,2,\ldots,n 号原子以某个顺序(可以由用户自行调整)被存放在其中,每个结点存放一个原子。

定义 ii 号原子的电荷量为 i!=1×2×3××ii!=1 \times 2\times 3 \times \ldots \times i

现有一个计时器 bb(单位为秒),其初值为 00

密码锁被加热后,以下事件依次循环发生,直至达成终止条件:

  1. 位于链两端的原子被移除(这不会使链变短),不再对后续事件产生影响
  2. 判定终止条件:
    • 若此时链中剩下不多于 11原子(也可以是 00),则达成终止条件,密码锁瘫痪(此时计时器 bb 的值不会增加 11);
    • 否则,将计时器 bb 的值增加 11
  3. 给每个原子标定运动方向(标定的运动方向是临时的,只生效一次,在下一次标定前会被重置):
    • 计算它左边所有原子的电荷量之和,设计算结果为 xx
    • 计算它右边所有原子的电荷量之和,设计算结果为 yy
    • 如果 x<yx<y,则标定方向为「向左」;
    • 如果 x>yx>y,则标定方向为「向右」;
    • 可以证明,xyx \ne y
  4. 所有原子按照所标定的运动方向,移动一条边的距离,来到相邻的结点。

此外,krjt 从铭牌上读取到了 nn 的值。

krjt 定义,密码锁的瘫痪用时,为它瘫痪时 bb 的值。当然,krjt 希望密码锁尽量安全,因此他想最大化密码锁的瘫痪用时

为了不让更多人再次 JC krjt,请问:他该如何排列密码锁中 nn 个原子的初始顺序?

输入格式

一行一个正整数,nn

输出格式

一行 nn 个正整数,一个 1n1 \sim n 的排列,表示你给 krjt 规划的排列方案:从左到右(或者从右到左,可以证明它们的瘫痪用时相等)依次输出 nn 个原子的编号。

答案可能有多个,输出一个即可。

1
1
2
1 2
3
2 1 3
4
4 2 3 1
5
5 4 1 2 3
6
2 4 5 1 6 3

提示

样例解释:

66 个样例的瘫痪用时分别为 0,0,0,1,1,20,0,0,1,1,2 秒。

实际上,枚举可知:当 n6n \le 6 时,输出任何一个 1n1 \sim n 的排列都能 AC。

下面对样例 66 进行模拟。在链的描述中:

  • 00 表示该结点为空;
  • ii 表示该结点上存放着 ii 号原子;
  • (x,y)(x,y) 为计算结果。
  1. 初始的链245163\color{blue}2-4-5-1-6-3
  2. bb 初始为 00
  3. 位于两端的原子被移除,链变为 045160\color{blue}0-4-5-1-6-0
  4. bb 增加至 11
  5. 计算44 个原子(从左向右)的结果分别为 $(\color{red}0\color{black},841),(\color{red}24\color{black},721),(\color{red}144\color{black},720),(145,\color{red}0\color{black})$;
  6. 根据结果,左边 33 个原子(4,5,14,5,1向左运动,最右边的原子(66向右运动,链变为 451006\color{blue}4-5-1-0-0-6
  7. 位于两端的原子被移除,链变为 051000\color{blue}0-5-1-0-0-0
  8. bb 增加至 22
  9. 计算22 个原子(从左向右)的结果分别为 $(\color{red}0\color{black},1),(120,\color{red}0\color{black})$;
  10. 根据结果,左边的原子(55向左运动,右边的原子(11向右运动,链变为 500100\color{blue}5-0-0-1-0-0
  11. 位于两端的原子被移除,链变为 000100\color{blue}0-0-0-1-0-0
  12. 此时链中只剩下 11 个原子(11),反应结束,密码锁瘫痪

综上,样例 66 的瘫痪用时为 22 秒。


本题共 100100 个测试点,分别有 n=1,2,,100n=1,2,\ldots,100,每个 11 分。

对于 100%100\% 的数据,1n1001 \le n \le 100