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

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

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

输出 #1

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级灰阶。主要包含以下步骤：

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

2. 关键数据结构和函数

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

3. 实现思路

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

{% include custom/custom-post-content-inner.html %}

示例代码

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

#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 或其他随机访问容器中的元素进行排序。

基本语法：

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

std::sort(start_iterator, end_iterator);

start_iterator：排序开始位置（包括）
end_iterator：排序结束位置（不包括）

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

#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 2 3 4 5

示例2：降序排序

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

或使用 Lambda 表达式：

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

示例3：对结构体排序

#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;
}

输出：

Charlie 95
Alice 90
Bob 85

注意事项：

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

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

#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函数的实现方法。按照逻辑硬搓一个转换函数，减少大家对系统内置函数使用的记忆量。对小学生可能会更“友好”一些，大家按需选用即可。

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号

Last updated on 2025年8月30日

luogu-B3850 [GESP202306 四级] 幸运数 luogu-B3870 [GESP202309 四级] 变长编码