文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

CCF-CSP真题《202305-3 解压缩》思路+python,c++满分题解

2023-08-31 17:40

关注

想查看其他题的真题及题解的同学可以前往查看:CCF-CSP真题附题解大全


试题编号:202305-3
试题名称:解压缩
时间限制:5.0s
内存限制:512.0MB
问题描述:

题目背景

西西艾弗岛运营公司是一家负责维护和运营岛上基础设施的大型企业。在公司内,有许多分管不同业务的部门都需要使用到服务器设施。为了便于管理,同时降低公司运行成本,
西西艾弗岛运营公司建设了一套私有云系统。这套私有云系统除了能提供托管的虚拟机服务外,还能提供一些其他的服务。其中,最受好评的当属日志服务。此前,各个业务系统的日志都是分散存放在各自的服务器上的,
这样不仅不方便查看和分析而且也有丢失的风险。而日志服务则能够将各个业务系统的日志统一收集起来,方便查看和管理。

日志服务器收集到的日志都是纯文本,且高度格式化。这意味着日志数据可以被压缩得非常小。但是日志数据量非常大,且对处理效率的要求较高,因此可以牺牲一定的压缩率,使用高效的压缩算法来压缩日志数据。
小 C 被安排来实现解压缩日志的程序,给定一段被压缩的日志数据,他需要将其解压缩。

问题描述

这种压缩算法产生的数据流,可以被视为是一系列的元素。元素分为两种:字面量和回溯引用。字面量包含一系列的字节,对其进行解压缩时,直接将这些字节输出即可。
回溯引用则是将此前已经解压缩得到的数据流的一部分重复输出。回溯引用可以表示为 〈o,l〉,包含两个数字,分别为偏移量 o 和长度 l。
偏移量表示从当前位置向前回溯的距离,长度表示需要重复输出的字节数。其中要求 o,l>0。若已经解压缩了 p 字节,当 o≥l 时,
表示重复输出自偏移量 (p−o)(首个字节偏移量为 0)开始的 l 个字节。例如,已经解压缩的数据流是 abcde,则回溯引用 〈3,2〉 表示输出 cd
当 oabcde,
则回溯引用 〈2,5〉 表示输出 deded

被压缩的数据格式分为两部分:导引域和数据域。其中导引域保存了原始数据的长度。设原始数据长度为 n。则 n 可以表示为 ∑k=0dck×128k,其中 0≤ck<128,且
cd≠0。导引域的长度为 (d+1) 字节,依次保存 c0+128,c1+128,⋯,cd−1+128,cd。即每个字节用低 7 位保存 ck,除了最后一个字节的最高位为 0,
其余字节的最高位为 1。例如,原始数据的长度为 1324,那么 ck 依次为:44、10,即 16 进制的 0x2C0x0A。因此引导区的长度为 2,字节序列为 0xAC 0x0A


被压缩的数据格式

数据域保存了被压缩后的数据,是连续存储的元素的序列。每个元素的第一个字节的最低两位表示了元素的类型。当最低两位为 0 时,表示这是一个字面量。如果字面量包含的字节个数为 l,且 l≤60,
那么第一个字节的高 6 位表示 (l−1)。随后的 l 字节即为字面量所包含的原始字节。例如字节 0xE8,其二进制为 1110 1000,低二位是 0,表示这是一个字面量。高六位是 111010,表示数字 58,
即表示该字面量包含 59 个字节。因此,该字节后面的 59 个字节即为字面量所包含的原始字节。如果 l>60,那么则将 (l−1) 用小端序的 1 至 4 个字节表示,存储于第一个字节的后面。
第一个字节的高六位存储的值为 60、61、62 或 63 时,分别代表 (l−1) 用 1、2、3 或 4 个字节表示。例如,字节序列 0xF4 0x01 0x0A 中,首字节的二进制为 1111 0100,低二位是 0,表示这是一个字面量。
高 6 位是 111101,表示数字 61,即表示随后有两个字节存储了字面量的长度。随后的两个字节 0x01 0x0A,按小端序组成了十六进制数 0x0A01,即十进制 2561,表示该字面量包含 2562 个字节。
随后的 2562 个字节即为字面量所包含的原始字节。


字面量,长度不超过 60 字节 


字面量,长度超过 60 字节 

当元素首字节的最低两位是 01 时,表示这是一个回溯引用 〈o,l〉,且 4≤l≤11,0 高 3 位存储于首字节的高 3 位中。(l−4) 占 3 位,存储于首字节的 2 至 4 位中。如下图所示:

 7 6 5 4 3 2 1 0   7 6 5 4 3 2 1 0
+-----+-----+-+-+ +----------------+
|o(h3)| l-4 |0|1| |o (lower 8 bits)|
+-----+-----+-+-+ +----------------+

例如,字节 0x2D 0x1A,其首字节的二进制为 001 011 01,其最低两位为 01,表示这是一个回溯引用,其中 2 至 4 位是 011,表示数字 3,意味着 (l−4)=3,即 l=7。
其高 3 位是 001,与随后的字节 0x1A 组成了十六进制数 0x11A,即十进制 282,表示 o=282。因此,该回溯引用是 〈282,7〉。


回溯引用,形式 1 

当元素首字节的最低两位是 10 时,表示这是一个回溯引用 〈o,l〉,且 1≤l≤64,0 (l−1) 占 6 位,存储于首字节的高 6 位中。例如,字节 0x3E 0x1A 0x01,其首字节的二进制为 0011 1110,其最低两位为 10,表示这是一个回溯引用,其中高 6 位是 001111,表示数字 15,
即 (l−1)=15,即 l=16。随后的两个字节 0x1A 0x01,按小端序组成了十六进制数 0x011A,即十进制 282,表示 o=282。因此,该回溯引用是 〈282,16〉。


回溯引用,形式 2 

我们规定,元素的首字节的最低两位不允许是 11。如果出现了这种情况,那么这个数据域就是非法的。

压缩后的数据为合法的,当且仅当以下条件都满足:

  1. 引导区的长度不超过 4 字节;
  2. 引导区能被正确恢复为原始数据的长度;
  3. 每个元素的首字节的最低两位不是 11
  4. 每个元素都能按照规则被恢复为原始数据;
  5. 得到的原始数据长度恰好等于引导区中编码的原始数据长度。

输入格式

从标准输入读入数据。

输入包含有若干行,第一行是一个正整数 s,表示输入被解压缩数据的字节数。

接下来有 ⌈s8⌉ 行,表示输入的被解压缩的数据。每行只含有数字或字母 a 至 f
每两个字符组成一个十六进制数字,表示一个字节。除了最后一行,每行都恰有 8 个字节。输入数据保证是合法的。

输出格式

输出到标准输出中。

输出解压缩后的数据,每行连续输出 8 个字节,每个字节由两位十六进制数字(数字或字母 a 至 f)表示;但最后一行可以不满 8 个字节。

样例输入

81
8001240102030405
060708090af03c00
0102030405060708
090a0b0c0d0e0f01
0203040506070809
0a0b0c0d0e0f0102
030405060708090a
0b0c0d0e0f010203
0405060708090a0b
0c0d0e0fc603000d
78

样例输出

0102030405060708
090a000102030405
060708090a0b0c0d
0e0f010203040506
0708090a0b0c0d0e
0f01020304050607
08090a0b0c0d0e0f
0102030405060708
090a0b0c0d0e0f0d
0e0f0d0e0f0d0e0f
0d0e0f0d0e0f0d0e
0f0d0e0f0d0e0f0d
0e0f0d0e0f0d0e0f
0d0e0f0d0e0f0d0e
0f0d0e0f0d0e0f0d
0e02030405060708

样例说明

上述输入数据可以整理为:

80 01
24 0102030405060708090a
f0 3c
    000102030405060708090a0b0c0d0e0f
      0102030405060708090a0b0c0d0e0f
      0102030405060708090a0b0c0d0e0f
      0102030405060708090a0b0c0d0e0f
c6 0300
0d 78

首先读入第一字节 80,其最高位为 1,于是继续读入第二字节 01,其最高位为 0,因此读入引导区结束。得到 c0=0,c1=1,
原始数据长度为:0×1280+1×1281=128。

然后继续读入字节 24,其二进制是 0010 0100,最低两位为 00,表示这是一个字面量,取其高六位,是十进制数字 9,
表示这个字面量的长度为 10。接下来读入 10 个字节,得到字面量 0102030405060708090a

然后继续读入字节 f0,其二进制是 1111 0000,最低两位为 00,表示这是一个字面量,取其高六位,是十进制数字 60,表示此后的一个字节是字面量的长度减 1。
继续读入字节 3c,得到数字 60,表示这个字面量的长度是 61,接下来读入 61 个字节。

然后继续读入字节 c6,其二进制是 1100 0110,最低两位为 10,表示这是一个回溯引用,取其高六位,是十进制数字 49,表示回溯引用的长度 l 是 50。
随后继续读入两个字节 0300,按小端序组成十六进制数 0x0003,即十进制 3,表示回溯引用的偏移量 o 是 3。因此,这个回溯引用是 〈3,50〉。
由于 50=16×3+2,将此时缓冲区中最后三个字节 0d 0e 0f 重复输出 16 次,然后继续输出 0d 0e,补足共 50 个字节。

然后继续读入字节 0d,其二进制是 0000 1101,最低两位为 01,表示这是一个回溯引用,取其位 2 至 4,是 011,是十进制数字 3,表示回溯引用的长度 l 是 7。
随后读入一个字节 78,其二进制是 0111 1000,与本元素首字节 0d 的最高三位 000 拼合得到 000 0111 1000,是十进制数字 120,表示回溯引用的偏移量 o 是 120。
因此,这个回溯引用是 〈120,7〉。此前已经输出了 121 字节,此时从缓冲区开始的偏移量 121−120=1 的位置开始输出 7 个字节,即 02030405060708

此时,输入已经处理完成,共输出了 10+61+50+7=128 字节,与从引导区中读入的原始数据长度一致,因此解压缩成功。

子任务

对于 10% 的输入,解压缩后的数据长度不超过 127 字节,且仅含有字面量,每个字面量元素所含数据的长度不超过 60 字节;

对于 20% 的输入,解压缩后的数据长度不超过 1024 字节,且仅含有字面量,每个字面量元素所含数据的长度不超过 60 字节;

对于 40% 的输入,解压缩后的数据长度不超过 1024 字节,且仅含有字面量;

对于 60% 的输入,解压缩后的数据长度不超过 1024 字节,且包含的回溯引用的首字节的最低两位都是 01

对于 80% 的输入,解压缩后的数据长度不超过 4096 字节;

对于 100% 的输入,解压缩后的数据长度不超过 2MiB(2×220 字节),且 s≤2×106,且保证是合法的压缩数据。

真题来源:解压缩

感兴趣的同学可以如此编码进去进行练习提交

题目理解:

        给你一段压缩过的代码,可以拆分为引导域和数据域,引导域决定了解压缩后的数据长度,数据域也是可以分段的,每一段由其第一个字节的最低两位决定,若为00,则是字面量,若为01或10,则为回溯引用。输出解压缩后的数据,8字节为一行,最后一行允许不到8个字节。

思路分析:

        由于要多次读取字节,所以最好封装一个函数来 读取字节 ,记录当前读到的位置。由于要进行小端序调整字符串,可以考虑封装一个函数来 按小端序调整字符串 。由于01和10结尾都要回溯引用,也可以封装一个函数来 填充字符串 。由于用字节处理太麻烦了,可以使用 stoi()——有符号整型 或者 stoul——无符号整型 来进行进制转换。

 c++满分题解:

#include using namespace std;const int N = 2e6 + 10;int n, idx, p; // 当前已经解压缩了 p 字节,下一个读的是第 idx 下标的字符string res; // 解压后的数据string readBytes(int num){    char byte[2 * num];    for (int i = 0; i < 2 * num; i ++) cin >> byte[i];    idx += num * 2;    return string(byte, 2 * num);}void trackBack(int o, int l){    int start = res.length() - o * 2;    int len = o * 2;    string back_track_string = res.substr(start, len);    int cnt = 0;    while (cnt < l * 2 - l * 2 % len)    {        res += back_track_string;        cnt += len;    }    res += back_track_string.substr(0, l * 2 % len);}int main(){    cin >> n;    string bts;    vector c;    int v_c;    // 读入字节 直到最高位为0    while ((bts = readBytes(1)) >= "80")    {        v_c = stoi(bts, nullptr, 16);        v_c -= 128;        c.push_back(v_c);    }    // 最高位为0时,直接保存到c里    v_c = stoi(bts, nullptr, 16);    c.push_back(v_c);    // 引导区结束,计算原始数据长度    int length = 0;    for (int i = 0; i < c.size(); i ++) length += c[i] * pow(128, i);    while (idx < n * 2)    {        // 接下来是数据域        // 读入一个字节        bts = readBytes(1);        string string_to_binary = bitset<8>(stoi(bts, nullptr, 16)).to_string();        string lowest_two_digits = string_to_binary.substr(6, 2);        if (lowest_two_digits == "00")        {            string high_six_digits = string_to_binary.substr(0, 6);            int ll = stoi(high_six_digits, nullptr, 2);            // l <= 60,高六位 ll 表示 l - 1            if (ll <= 59)                res += readBytes(ll + 1);            else            {                // 第一个字节的高六位存储的值为 60、61、62 或 63 时,分别代表 l - 1 用 1、2、3 或 4 个字节表示                int literal_length = ll - 59;                // 按照小端序重组字符串 0x01 0x0A => 0x0A01                string string1 = readBytes(literal_length);                string string2;                // 字符串每两位反转                for (int i = string1.length() - 2; i >= 0; i -= 2)                    string2 += string1.substr(i, 2);                int l = 1 + stoi(string2, nullptr, 16); // 字面量长度                res += readBytes(l);            }        }        else if (lowest_two_digits == "01")        {            // 第 2 ~ 4 位即 从下标 3 开始的三位 001 011 01            string two_to_four_digits = string_to_binary.substr(3, 3);            // l - 4 占 3 位,存储于首字节的 2 至 4 位中            int l = stoi(two_to_four_digits, nullptr, 2) + 4;            // o 占 11 位,其低 8 位存储于随后的字节中,高 3 位存储于首字节的高 3 位中            string high_three_digits = string_to_binary.substr(0, 3);            string next_byte_binary = bitset<8>(stoi(readBytes(1), nullptr, 16)).to_string();            int o = stoi(high_three_digits + next_byte_binary, nullptr, 2);            // 回溯引用            trackBack(o, l);        }        else if (lowest_two_digits == "10")        {            string high_six_digits = string_to_binary.substr(0, 6);            // l 占 6 位,存储于首字节的高 6 位中            int l = stoi(high_six_digits, nullptr, 2) + 1;            // o 占 16 位,以小端序存储于随后的两个字节中            string string1 = readBytes(2);            string string2;            // 字符串每两位反转            for (int i = string1.length() - 2; i >= 0; i -= 2)                string2 += string1.substr(i, 2);            int o = stoi(string2, nullptr, 16);            // 回溯引用            trackBack(o, l);        }    }    for (int i = 0; i < res.length(); i ++)    {        cout << res[i];        // 输出,每16个字符加一个换行        if ((i + 1) % 16 == 0) cout << endl;    }    // 若最后一行不能凑8个,则补一个换行    if (res.length() % 16) cout << endl;    return 0;}

 运行结果:

来源地址:https://blog.csdn.net/weixin_53919192/article/details/131565864

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯