文章

【GESP】C++四级真题 luogu-B3851 [GESP202306 四级] 图像压缩

发表于 更新于
作者 OneCoder
次浏览 21 分钟阅读

GESP C++四级真题，函数、结构体、多维数组等应用练习，难度⭐⭐⭐☆☆。个人认为23年GESP考试设立初期各级考试的题难度都不小，本题应该是四级真题中难度较大的一个。在洛谷也是评定为普及/提高。

luogu-B3851 [GESP202306 四级] 图像压缩

题目要求

题目描述

图像是由很多的像素点组成的。如果用 $0$ 表示黑，$255$ 表示白，$0$ 和 $255$ 之间的值代表不同程度的灰色，则可以用一个字节表达一个像素（取值范围为十进制 0-255、十六进制 00-FF）。这样的像素组成的图像，称为 $256$ 级灰阶的灰度图像。

现在希望将 $256$ 级灰阶的灰度图像压缩为 $16$ 级灰阶，即每个像素的取值范围为十进制 0-15、十六进制 0-F。压缩规则为：统计出每种灰阶的数量，取数量最多的前 $16$ 种灰阶（如某种灰阶的数量与另外一种灰阶的数量相同，则以灰阶值从小到大为序），分别编号 0-F（最多的编号为 0，以此类推）。其他灰阶转换到最近的 $16$ 种灰阶之一，将某个点的灰阶值（灰度，而非次数）与 $16$ 种灰阶中的一种相减，绝对值最小即为最近，如果绝对值相等，则编号较小的灰阶更近。

输入格式

输入第 $1$ 行为一个正整数 $n(10\le n \le 20)$，表示接下来有 $n$ 行数据组成一副 $256$ 级灰阶的灰度图像。

第 $2$ 行开始的 $n$ 行，每行为长度相等且为偶数的字符串，每两个字符用十六进制表示一个像素。约定输入的灰度图像至少有 $16$ 种灰阶。约定每行最多 $20$ 个像素。

输出格式

第一行输出压缩选定的 $16$ 种灰阶的十六进制编码，共计 $32$ 个字符。

第二行开始的 $n$ 行，输出压缩后的图像，每个像素一位十六进制数表示压缩后的灰阶值。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
11

10
00FFCFAB00FFAC09071B5CCFAB76
00AFCBAB11FFAB09981D34CFAF56
01BFCEAB00FFAC0907F25FCFBA65
10FBCBAB11FFAB09981DF4CFCA67
00FFCBFB00FFAC0907A25CCFFC76
00FFCBAB1CFFCB09FC1AC4CFCF67
01FCCBAB00FFAC0F071A54CFBA65
10EFCBAB11FFAB09981B34CFCF67
01FFCBAB00FFAC0F071054CFAC76
1000CBAB11FFAB0A981B84CFCF66

输出 #1

1
2
3
4
5
6
7
8
9
10
11

ABCFFF00CB09AC07101198011B6776FC
321032657CD10E
36409205ACC16D
B41032657FD16D
8F409205ACF14D
324F326570D1FE
3240C245FC411D
BF4032687CD16D
8F409205ACC11D
B240326878D16E
83409205ACE11D

说明/提示

【样例 $1$ 解释】

灰阶 AB、CF 和 FF 出现 $14$ 次，00 出现 $10$ 次，CB 出现 $9$ 次，09 出现 $7$ 次，AC 出现 $6$ 次，07 出现 $5$ 次，10、11 和 98 出现 $4$ 次，01、1B、67、76 和 FC 出现 $3$ 次。

题目分析

1. 理解题目要求

这道题要求我们实现一个图像压缩算法，将256级灰阶图像压缩为16级灰阶。主要包含以下步骤：

  1. 统计原图像中每种灰阶值出现的次数
  2. 选取出现次数最多的16种灰阶值作为标准色阶
    • 如果出现次数相同，取灰阶值较小的
    • 给这16种灰阶值编号(0-F)，出现次数最多的编号为0
  3. 其他灰阶值转换为最接近的标准色阶
    • 计算与16种标准色阶的差值绝对值
    • 取差值最小的对应编号
    • 如果差值相等，取编号较小的

2. 关键数据结构和函数

  1. 颜色信息结构体 color_info
    • color_num: 存储颜色值(0-255)
    • freq: 存储该颜色出现的频率
  2. 16进制转换函数
    • hexstr_to_int: 将16进制字符串转为整数
    • int_to_hexstr: 将整数转为指定位数的16进制字符串
  3. 颜色转换函数 trans_color
    • 输入: 原始颜色值和16种标准色阶
    • 输出: 最接近标准色阶的编号(0-F)
    • 计算与每个标准色阶的差值，取最小值

3. 实现思路

  1. 读取和存储图像数据
    • 使用二维vector存储原始图像数据
    • 同时统计每种颜色出现的频率
  2. 确定16种标准色阶
    • 对颜色按频率排序(频率相同按颜色值排序)
    • 取前16种颜色作为标准色阶
    • 输出这16种颜色的16进制表示
  3. 压缩处理
    • 遍历原图像每个像素
    • 找到最接近的标准色阶
    • 输出对应编号(0-F)

示例代码

方法一：结构体处理(符合四级大纲要求)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <iomanip>

// 定义颜色信息结构体,包含颜色值和出现频率
struct color_info {
    int color_num;  // 颜色值
    int freq;       // 出现频率
};

// 定义全局颜色数组,用于统计256种颜色的频率
struct color_info colors[256];

// 将16进制字符串转换为整数
int hexstr_to_int(std::string str) {
    return std::stoi(str, nullptr, 16);
}

// 将整数转换为指定位数的16进制字符串
std::string int_to_hexstr(int num, int bit) {
    // 创建字符串流对象
    std::stringstream ss;
    // 设置输出格式:
    // setw(bit) - 设置输出宽度为bit位
    // setfill('0') - 不足位数用0填充
    // hex - 以16进制格式输出
    // uppercase - 字母以大写形式输出
    // num - 要转换的数字
    ss << std::setw(bit) << std::setfill('0') << std::hex << std::uppercase << num;
    return ss.str();
}

// 颜色信息比较函数,用于排序
// 频率相同时按颜色值升序,否则按频率降序
bool compare(color_info a, color_info b) {
    return a.freq == b.freq ? a.color_num < b.color_num : a.freq > b.freq;
}

// 将原始颜色转换为最接近的16种颜色之一
int trans_color(int color_num, struct color_info top_color[16]) {
    int min_diff = 1000000000;  // 初始化最小差值
    int min_index = 0;          // 记录最接近颜色的索引
    // 遍历16种标准颜色
    for (int i = 0; i < 16; i++) {
        // 计算当前颜色与标准颜色的差值的绝对值
        int diff = abs(color_num - top_color[i].color_num);
        // 如果找到更小的差值
        if (diff < min_diff) {
            // 更新最小差值
            min_diff = diff;
            // 记录对应的颜色索引
            min_index = i;
        }
        // 如果差值相等，由于i是从小到大遍历的
        // 自动保证了相等时取较小索引的规则
    }
    return min_index;
}

int main() {
    int n;
    std::cin >> n;
    // 存储图像的二维向量
    std::vector<std::vector<int>> colors_vec(n);
    
    // 读取输入并统计颜色频率
    // 外层循环处理n行输入
    for (int i = 0; i < n; i++) {
        std::string str;
        std::cin >> str;
        // 内层循环每次处理2个字符(1个颜色值)
        for (int j = 0; j < str.length(); j+=2) {
            // 将2个16进制字符转换为整数颜色值
            int color_num = hexstr_to_int(str.substr(j, 2));
            // 将颜色值存入二维向量对应行
            colors_vec[i].push_back(color_num);
            // 更新颜色频率统计
            colors[color_num].freq++;
            // 设置颜色值(用于后续排序)
            colors[color_num].color_num = color_num;
        }
    }

    // 按频率排序所有颜色
    std::sort(colors, colors + 256,compare);

    // 选取前16种最常见的颜色
    struct color_info top_color[16];

    // 输出16种颜色的16进制值
    for (int i = 0; i < 16; i++) {
        top_color[i] = colors[i];
        std::cout << int_to_hexstr(top_color[i].color_num,2);
    }
    std::cout << "\n";

    // 转换并输出压缩后的图像
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < colors_vec[i].size(); j++) {
            int trans_color_num = trans_color(colors_vec[i][j], top_color);
            std::cout << int_to_hexstr(trans_color_num, 1);
        }
        std::cout << "\n";
    }

}

方法一补充说明

代码中使用了C++标准库中的sort函数来对颜色信息进行排序。在 C++ 中，sort 是一个常用的排序函数，定义在头文件 <algorithm> 中。它可以用来对数组、vector 或其他随机访问容器中的元素进行排序。

基本语法：

1
2
3
4

#include <algorithm> // 需要包含这个头文件
#include <vector>

std::sort(start_iterator, end_iterator);
  • start_iterator：排序开始位置（包括）
  • end_iterator：排序结束位置（不包括）

示例1：对 vector<int> 升序排序

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> nums = {5, 3, 1, 4, 2};
    std::sort(nums.begin(), nums.end());

    for (int num : nums) {
        std::cout << num << " ";
    }
    return 0;
}

输出：

1

1 2 3 4 5

示例2：降序排序

1

std::sort(nums.begin(), nums.end(), std::greater<int>());

或使用 Lambda 表达式：

1
2
3

std::sort(nums.begin(), nums.end(), [](int a, int b) {
    return a > b; // 降序
});

示例3：对结构体排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <iostream>
#include <vector>
#include <algorithm>

struct Student {
    std::string name;
    int score;
};

int main() {
    std::vector<Student> students = {
        {"Alice", 90},
        {"Bob", 85},
        {"Charlie", 95}
    };

    std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        return a.score > b.score; // 按成绩降序
    });

    for (const auto& s : students) {
        std::cout << s.name << " " << s.score << std::endl;
    }
    return 0;
}

输出：

1
2
3

Charlie 95
Alice 90
Bob 85

注意事项：

  • sort 使用的是 快速排序（IntroSort），平均时间复杂度为 O(n log n)。
  • 适用于 随机访问迭代器（如 vector, 数组），不适用于 list（可用 list.sort()）。
  • 若你要排序的区间较大，建议传入比较函数以提高控制力。

方法二：使用map、paire（七级哈希表知识点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>

// 将16进制字符串转为整数
// 将16进制字符串转换为整数
// 参数str: 16进制字符串
// 返回: 转换后的整数
// 使用std::stoi进行转换,第二个参数nullptr表示不需要返回转换结束位置
// 第三个参数16表示按16进制转换
int hexstr_to_int(const std::string& str) {
    return std::stoi(str, nullptr, 16);
}

/*
本函数实现了一个整数到固定位数16进制字符串的转换。主要思路和原理如下：

1. 字符映射表
   - 使用静态数组hex_digits存储16进制的所有可能字符(0-F)
   - 数组索引0-15正好对应16进制的0-F
   - 使用static确保字符表只初始化一次

2. 结果字符串初始化
   - 使用std::string的构造函数创建指定长度的字符串
   - 初始全部填充'0'字符,保证位数不足时高位补0
   - bit参数控制输出的16进制位数

3. 进制转换过程
   - 从右向左(低位到高位)处理每一位
   - 使用num % 16获取当前位的值(0-15)
   - 将余数作为hex_digits的索引获取对应字符
   - num /= 16实现右移4位,处理下一个16进制位
*/
std::string int_to_hexstr(int num, int bit) {
    // 定义16进制字符表,0-F对应的字符
    static const char hex_digits[] = "0123456789ABCDEF";
    // 创建指定长度的字符串,初始全为'0'
    std::string res(bit, '0');
    // 从低位到高位,依次取num的每位转成16进制字符
    for (int i = bit - 1; i >= 0; --i) {
        res[i] = hex_digits[num % 16]; // 取余得到当前位对应的16进制数
        num /= 16;
    }
    return res;
}

// 颜色频率比较函数
// 参数:
// - a,b: 待比较的两个颜色频率对(颜色值,出现次数)
// 返回: 比较结果
// 规则: 频率高的优先;频率相同时颜色值小的优先
bool compare_pair(const std::pair<int, int>& a, const std::pair<int, int>& b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}

// 将颜色值映射到最接近的标准颜色索引
// 参数:
// - color_num: 原始颜色值
// - top_color: 标准颜色表
// 返回: 最接近的标准颜色的索引(0-15)
int trans_color(int color_num, const std::vector<int>& top_color) {
    int min_diff = 1000000000; // 初始化最小差值
    int min_index = 0; // 记录最小差值对应的颜色索引
    // 遍历所有标准颜色
    for (int i = 0; i < 16; ++i) {
        // 计算当前颜色与标准颜色的差值
        int diff = std::abs(color_num - top_color[i]);
        // 如果找到更小的差值,更新记录
        if (diff < min_diff) {
            min_diff = diff;
            min_index = i;
        }
    }
    return min_index;
}

int main() {
    int n;
    std::cin >> n; // 读入图像行数

    // 创建二维vector存储图像数据
    std::vector<std::vector<int>> colors_vec(n);
    // 创建vector存储每种颜色的频率统计
    // pair的first存颜色值,second存频率
    std::vector<std::pair<int, int>> color_freq(256, {0, 0});

    // 读入图像数据并统计颜色频率
    for (int i = 0; i < n; i++) {
        std::string str;
        std::cin >> str;
        // 每两个字符表示一个颜色值
        for (size_t j = 0; j < str.length(); j += 2) {
            // 转换16进制字符串为整数
            int color_num = hexstr_to_int(str.substr(j, 2));
            // 保存颜色值
            colors_vec[i].push_back(color_num);
            // 更新颜色频率统计
            color_freq[color_num].second++;
            color_freq[color_num].first = color_num;
        }
    }
    
    // 按频率排序所有颜色
    std::sort(color_freq.begin(), color_freq.end(), compare_pair);

    // 选取前16种最常见的颜色
    std::vector<int> top_color;
    for (int i = 0; i < 16 && i < (int)color_freq.size(); ++i) {
        top_color.push_back(color_freq[i].first);
    }

    // 输出16种标准颜色的16进制表示
    for (int i = 0; i < 16; i++) {
        std::cout << int_to_hexstr(top_color[i], 2);
    }
    std::cout << "\n";

    // 输出压缩后的图像
    for (int i = 0; i < n; i++) {
        for (size_t j = 0; j < colors_vec[i].size(); j++) {
            // 将每个颜色映射到最接近的标准颜色
            int trans_color_num = trans_color(colors_vec[i][j], top_color);
            // 输出映射后的颜色索引(1位16进制)
            std::cout << int_to_hexstr(trans_color_num, 1);
        }
        std::cout << "\n";
    }
}

方法二补充说明

与方法一相比，除了改用map和pair替代原结构体实现外，还特意修改了int_to_hexstr函数的实现方法。按照逻辑硬搓一个转换函数，减少大家对系统内置函数使用的记忆量。对小学生可能会更“友好”一些，大家按需选用即可。

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲、真题讲解、知识拓展和练习清单等详见【置顶】【GESP】C++ 认证学习资源汇总

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
GESP, 四级
GESP C++ 函数 结构体 多维数组 排序
本文由作者按照 CC BY 4.0 进行授权