GESP C++四级真题 | 202306图像压缩(二维数组、排序、结构体、进制、计数)

四季读书网 2026-03-11 13:01:32 1 0

👆点击知行合一Gesp>点击右上角“···”>设为星标🌟

大家好，我是黄老师。曾任职多家国有大型科技公司，具有多年C/C++实战经验，打造过数百万用户规模的电子终端产品。目前是一名少儿C++编程业余讲师，毕竟CSP也自称非专业。😁

已经完成《GESP一级保命系列》专栏，《GESP二级编程保命-字符图形》专栏以及《GESP二级编程保命-暴力枚举》专栏、GESP三级编程-一维数组、GESP三级编程-字符串、GESP三级编程-进制转换、GESP三级编程-位运算、GESP三级编程-排序等等三级专题，供大家参考。

现在推出《GESP四级-函数》、《GESP四级-排序》、《GESP四级-二维数组》专栏，并会分享相关实践经验，与同学们一起学习、进步。🚀

GESP C++四级真题 | 202306图像压缩(二维数组、排序、结构体、进制、计数) 第1张

欢迎关注公众号，共同学习与进步

点赞👍 | 分享🌏 | 推荐♥️ | 转发🔥 | 评论🐳

GESP四级编程考试在GESP三级编程的基础上，增加了二维数组应用，函数与异常，结构体与指针，文件操作，冒泡、选择、插入排序算法（sort），递推算法（递归函数）。括号内容虽有超纲，但是先学先受益！

四级真题：202306图像压缩
01

通过标题也能感到这是一道非常棘手的题目，综合多方面所学知识，才能解决此题。

题目描述：

GESP C++四级真题 | 202306图像压缩(二维数组、排序、结构体、进制、计数) 第4张

题目来源

洛谷网B3851、信奥公开课
解题思路
02
一、题意分析
输入是一个 256 级灰阶（0-255）的灰度图像
每个像素用两个十六进制字符表示（如 00=0, FF=255）
需要压缩为 16 级灰阶（0-15）
压缩规则（分两步）：
第一步：选出 16 种代表灰阶
统计每种灰阶值（0-255）在图像中出现的次数
取出现次数最多的前 16 种灰阶
如果次数相同，灰阶值小的优先
将这 16 种灰阶按出现次数从多到少编号为 0-F（0 号给最多的，以此类推）
注意：编号时如果次数相同，按灰阶值从小到大排，但编号顺序是次数从多到少
第二步：映射所有像素
对于每个原始像素的灰阶值，找 16 种代表灰阶中绝对值差最小的那个
如果差值相等，选编号小的代表灰阶
用该代表灰阶的编号（0-15，一位十六进制）代替原像素
输出要求：
第一行：16 种代表灰阶的十六进制值，每个两位，共 32 个字符
按出现次数从多到少的顺序（编号 0 到 F）
接下来 n 行：压缩后的图像，每个像素一位十六进制数
二、样例分析：
样例输入解析：
n=10，每行是偶数长度的十六进制字符串
每两个字符代表一个像素的灰阶值
统计灰阶出现次数（从样例说明）：
AB, CF, FF: 各 14 次（最多）
00: 10 次
CB: 9 次
09: 7 次
AC: 6 次
07: 5 次
10, 11, 98: 各 4 次
01, 1B, 67, 76, FC: 各 3 次
选出前 16 种：按次数排序，次数相同按灰阶值从小到大：
AB(14), CF(14), FF(14) → AB < CF < FF
00(10)
CB(9)
09(7)
AC(6)
07(5)
10(4), 11(4), 98(4) → 10 < 11 < 98
01(3), 1B(3), 67(3), 76(3), FC(3) → 01 < 1B < 67 < 76 < FC
前 16 种：
AB (14次) 编号0
CF (14次) 编号1
FF (14次) 编号2
00 (10次) 编号3
CB (9次) 编号4
09 (7次) 编号5
AC (6次) 编号6
07 (5次) 编号7
10 (4次) 编号8
11 (4次) 编号9
98 (4次) 编号A
01 (3次) 编号B
1B (3次) 编号C
67 (3次) 编号D
76 (3次) 编号E
FC (3次) 编号F
输出第一行： 按编号0-F的顺序，每个灰阶值用两位十六进制AB CF FF 00 CB 09 AC 07 10 11 98 01 1B 67 76 FC连接成字符串：ABCFFF00CB09AC07101198011B6776FC ✓
第二行开始： 每个原始像素找最近的代表灰阶，用其编号输出
三、建模思路
数据结构：
统计每种灰阶出现的次数
灰阶值范围 0-255，可以用数组 count[256] 统计
存储前16种代表灰阶的信息
灰阶值 value
出现次数 freq
编号 id (0-15)
struct Gray {   int value;   // 灰阶值 0-255   int freq; // 出现次数   int id; // 编号 0-15};
算法步骤：
读入图像
每行字符串，每两个字符解析为一个十六进制数（灰阶值）
存储原始像素值（方便第二步映射）
统计频率
cnt[灰阶值]++
选出前16种
将所有出现过（count>0）的灰阶按规则排序
排序规则：先按次数降序，次数相同按灰阶值升序
取前16个，分配编号0-15
构建映射表
map256to16[256]：原始灰阶值 → 代表灰阶的编号
对于每个原始灰阶值，遍历16种代表灰阶，找差值最小的
差值相同选编号小的
输出
第一行：按编号顺序输出代表灰阶值（两位十六进制）
接下来n行：输出压缩后图像，每个像素一位十六进制
四、算法选择
十六进制转换：
输入是两位十六进制字符串，如 "AB" → 数值 0xAB = 171
可以用 stoi(s.substr(pos, 2), nullptr, 16) 或手动转换
输出时，数值 0-15 转成一位十六进制字符
inthexToInt(char c) {   if (c >= '0' && c <= '9') return c - '0';   return c - 'A' + 10;}charintToHex(int x) {   if (x < 10) return '0' + x;   return 'A' + (x - 10);}
排序规则：
bool cmp(const Gray& a, const Gray& b) {   if (a.freq != b.freq) return a.freq > b.freq; // 次数多在前   return a.value < b.value;   // 次数相同值小在前}
找最近代表灰阶：在16种代表灰阶中，找到与原始像素值最接近的那个，并返回它的编号
// 初始化最小差值为一个很大的数（256），因为灰阶范围是0-255int minDiff = 256;// 初始化最佳编号为0（即使没有找到更小的，至少有个默认值）int bestId = 0;// 遍历所有16种代表灰阶for (int k = 0; k < 16; k++) {   // 计算当前代表灰阶与原始像素值的绝对差值   int diff = abs(origVal - topValues[k]);   // 判断条件：   // 1. 如果当前差值比之前找到的最小差值还小 → 更新   // 2. 如果当前差值等于最小差值，但当前代表灰阶的编号更小 → 更新   // （注意：这里 k < bestId 表示编号更小，因为编号0比编号1更优先）   if (diff < minDiff || (diff == minDiff && k < bestId)) { minDiff = diff; // 更新最小差值 bestId = k; // 更新最佳编号 }}

题解代码
03

题目综合知识点有点多，代码行数也很多，结合题目分析仔细阅读理解代码吧！

#include<bits/stdc++.h>using namespace std;const int MAXN = 25;// 20行 * 20列 = 400个像素const int MAXPIX = 405;struct Gray {    int value;   // 灰阶值 0-255    int freq;    // 出现次数    int id;      // 编号 0-15};string rows[MAXN];int pixels[MAXN][MAXN];  // 存储原始像素值int cnt[256] = {0};// 映射表int map256to16[256];inthexToInt(char c){    if (c >= '0' && c <= '9') return c - '0';    return c - 'A' + 10;}charintToHex(int x){    if (x < 10) return '0' + x;    return 'A' + (x - 10);}boolcmp(const Gray& a, const Gray& b){    if (a.freq != b.freq) return a.freq > b.freq;  // 次数多在前    return a.value < b.value;                       // 次数相同值小在前}intmain(){       int n; cin >> n;    int rowLen = 0;    // 1. 读入图像并统计频率    for (int i = 0; i < n; i++) {        cin >> rows[i];        rowLen = rows[i].length();        for (int j = 0; j < rowLen; j += 2) {            // 解析两位十六进制            int high = hexToInt(rows[i][j]);            int low = hexToInt(rows[i][j + 1]);            int val = high * 16 + low;            // 记录像素值            pixels[i][j/2] = val;            // 记录像素值出现次数            cnt[val]++;        }    }    // 2. 收集所有出现过的灰阶    Gray grays[256];    int grayCount = 0;    for (int v = 0; v < 256; v++) {        if (cnt[v] > 0) {            grays[grayCount].value = v;            grays[grayCount].freq = cnt[v];            grayCount++;        }    }    // 3. 排序选出前16种    sort(grays, grays + grayCount, cmp);    // 取前16种，分配编号    Gray top16[16];    for (int i = 0; i < 16; i++) {        top16[i] = grays[i];        top16[i].id = i;    }    // 4. 构建映射表    for (int v = 0; v < 256; v++) {        // 找最近的代表灰阶        int minDiff = 256;        int bestId = 0;        for (int k = 0; k < 16; k++) {            int diff = abs(v - top16[k].value);            if (diff < minDiff) {                minDiff = diff;                bestId = k;            } else if (diff == minDiff && k < bestId) {                bestId = k;            }        }        map256to16[v] = bestId;    }    // 5. 输出第一行：16种代表灰阶    for (int i = 0; i < 16; i++) {        int val = top16[i].value;        cout << intToHex(val / 16) << intToHex(val % 16);    }cout << endl;    // 6. 输出压缩后的图像    int cols = rowLen / 2;    for (int i = 0; i < n; i++) {        for (int j = 0; j < cols; j++) {            int id = map256to16[pixels[i][j]];            cout << intToHex(id);        }        cout << endl;    }    return 0;}