#P6586. 压缩算法

    ID: 6224 传统题 2000ms 512MiB 尝试: 18 已通过: 5 难度: 7 上传者: 标签>难度分类提高+/省选-图论状态扩展图枚举与搜索广度优先搜索模拟与实现技巧预计算转移状态去重路径恢复CF2300

压缩算法

压缩算法

题目描述

数据压缩是我们信息社会中的一项重要技术。它的目的是将给定的字符串编码为(尽可能)更紧凑的编码字符串,以便能够高效地存储和/或传输。

你需要设计一种新颖的压缩算法,以确保即使编码字符串被反转后,也能够解码为原字符串。

目前,你正在考虑以下规范作为候选方案:

  • 给定的字符串是一串十进制数字,即由0至9组成的序列。
  • 编码字符串由一系列编码词组成,每个编码词包含两个十进制数字A和L。因此,编码字符串是一串偶数个十进制数字。
  • 编码字符串 A1L1…AkLkA_1L_1\dots A_kL_k 的解码过程如下。为了简化,每个十进制数字(如 AiA_i 或 LiL_i)也视作它所表示的 00 至 99 的整数。

解码时按顺序处理每个编码词 AiLiA_iL_i:

  1. 若 Ai=0A_i=0,向已解码串末尾追加一个数字 LiL_i。
  2. 否则,若 Li=0L_i=0,不做任何操作。
  3. 否则,若 AiA_i 大于当前已解码串的长度,报告错误。
  4. 否则,重复 LiL_i 次:读取当次追加前已解码串的倒数第 AiA_i 个数字,将它追加到串末尾。每次追加后,下次读取的串也随之改变。

上述分支按顺序判断;特别地,编码词 00 输出一个 0,而 Ai>0,Li=0A_i>0,L_i=0 的编码词直接跳过,不检查距离是否越界。反转指反转整个编码串的所有数字,因此 25 反转为 52,不只是调换编码词的先后顺序。

例如,编码字符串 000125 被解码为字符串 0101010,步骤如下:

  1. 第一个编码词 00 输出 0。
  2. 第二个编码词 01 输出 1。
  3. 最后一个编码词 25 的第一个数字2表示需要输出当前已解码数字中倒数第二个数字,共需重复输出五次。
    • 第一次重复时,已解码的数字为 0 和 1,倒数第二个数字为 0,输出 0。
    • 第二次重复时,已解码的数字为 0, 1, 0,倒数第二个数字为 1,输出 1。
    • 再重复三次分别输出 0, 1, 0。

若一串编码词没有产生错误,则该编码字符串是有效的。如果编码字符串的反转也是有效的且原字符串和其反转均解码为相同的字符串,则称该编码字符串是可逆的。

例如,编码字符串 000125 不是可逆的,因为其反转 521000 会产生错误,不是有效编码。编码字符串 0010 虽然反转后有效,但不是可逆的,因为解码得到的结果不同。相反,编码字符串 0015599100 是可逆的,因为其反转 0019955100 也是有效的,并且都解码为 00000000000000000。

你希望评估此压缩方法在各种情况下的表现。你的任务是编写一个程序,对于任意给定的数字字符串,找到能够解码为该字符串的最短可逆编码字符串。

输入格式

输入包含一行,由一个非空的十进制数字字符串 s 组成。字符串的长度不超过500。

输出格式

输出能够解码为 s 的最短可逆编码字符串。如果存在多个具有相同最短长度的解码方案,请输出按字典序最小的那个。注意,可以证明对于任意输入字符串,总能存在一个可逆的编码字符串(例如,参见样例输出4)。

样例输入 1

00000000000000000

样例输出 1

0015599100

样例输入 2

0101010

样例输出 2

000122221000

样例输入 3

123123123123123123123123123123

样例输出 3

01020336699993302010

样例输入 4

123456789

样例输出 4

010203040506070809908070605040302010