把 256 级灰阶压缩为 16 级:取出现次数最多的 16 种灰阶编号 0~F,其余归到最近的。
256 级灰阶图像中,每个像素取值为 00 ~ FF(0 ~ 255)。现要压缩为 16 级(0 ~ 15)。规则:
0 ~ F,最多的编号为 0,依次类推输出第一行为 16 种选定灰阶的十六进制编码(共 32 个字符);之后 n 行输出压缩后的图像,每个像素用一位十六进制表示。
频次统计多关键字排序最近邻映射十六进制格式化
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n(10 ~ 20);随后 n 行等长偶数字符串,每 2 字符一个像素 |
| 输出 | 第一行 32 个十六进制字符;随后 n 行每个像素一位十六进制 |
| 数据范围 | 10 ≤ n ≤ 20,每行最多 20 个像素 |
| 保证 | 输入至少含 16 种不同灰阶 |
| 灰阶值 | 0 ~ 255(十六进制 00 ~ FF) |
|v − g| 最小的;并列时取编号小的(即先出现的那一种)假设图像只有 5 种灰阶(真实题目至少 16 种,这里只为演示流程):
| 灰阶值 | 出现次数 |
|---|---|
| 0x10 | 5 次 |
| 0x20 | 3 次 |
| 0x30 | 3 次 |
| 0x40 | 1 次 |
| 0x50 | 1 次 |
| 排序后 | 灰阶值 | 次数 | 编号 |
|---|---|---|---|
| 第 1 位 | 0x10 | 5 | 0 |
| 第 2 位 | 0x20 | 3 | 1 |
| 第 3 位 | 0x30 | 3 | 2 |
| 第 4 位 | 0x40 | 1 | 3 |
| 第 5 位 | 0x50 | 1 | 4 |
| 原灰阶 | 与各代表的最短距离 | 映射到编号 |
|---|---|---|
| 0x10 | 与 0x10 距离 0 | 0 |
| 0x20 | 与 0x20 距离 0 | 1 |
| 0x28 | 与 0x20 差 8、与 0x30 差 8 → 并列取编号小的 | 1 |
| 0x48 | 与 0x40 差 8、与 0x50 差 8 → 并列取编号小的 | 3 |
输出的第一行是 32 个字符,把这 16 种灰阶的十六进制依次写出、中间不加空格。
| 格式 | 正确写法 | 错误写法 |
|---|---|---|
| 第一行 | 10203040...(32 字符连写) | 10 20 30 40(有空格) |
| 压缩后的像素 | 每个像素一位十六进制,如 A | 写成两位如 0A |
0x00,如果不补 0,输出会变成 0 一位,导致总长度不是 32,格式判错。所以必须用 %02X 保证每项两位。对每个像素,在 16 个代表灰阶里线性找最近的
预先算好 256 个灰阶值各自的映射编号,之后 O(1) 查询
| 方案 | 本题运算量 | 代码量 |
|---|---|---|
| 枚举 16 种 | 约 6400 次 | 约 10 行 |
| 预处理映射表 | 约 4000 + 400 次 | 约 18 行 |
输入若干灰阶值(0~255,空格分隔),程序会选出 16 种代表灰阶并给出映射表。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int cntv[256]; // 各灰阶出现次数 int main() { int n; scanf("%d", &n); vector<string> img(n); for (int i = 0; i < n; i++) { cin >> img[i]; // 每 2 个字符是一个像素(十六进制) for (size_t j = 0; j + 1 < img[i].size(); j += 2) { int v = stoi(img[i].substr(j, 2), nullptr, 16); cntv[v]++; } } // 收集出现过的灰阶,按 (次数降序, 灰阶值升序) 排序 vector<int> vals; for (int v = 0; v < 256; v++) if (cntv[v] > 0) vals.push_back(v); sort(vals.begin(), vals.end(), [](int a, int b) { if (cntv[a] != cntv[b]) return cntv[a] > cntv[b]; return a < b; }); // 取前 16 种作为代表 vector<int> rep(vals.begin(), vals.begin() + 16); // 第一行:32 个十六进制字符 for (int k = 0; k < 16; k++) printf("%02X", rep[k]); printf("\n"); // 输出压缩后的图像 for (int i = 0; i < n; i++) { for (size_t j = 0; j + 1 < img[i].size(); j += 2) { int v = stoi(img[i].substr(j, 2), nullptr, 16); // 在 16 种代表里找距离最小的;并列时保留更小的编号 int bestK = 0, bestD = INT_MAX; for (int k = 0; k < 16; k++) { int d = abs(v - rep[k]); if (d < bestD) { bestD = d; bestK = k; } // 严格小于 -> 并列取小编号 } printf("%X", bestK); } printf("\n"); } return 0; }
d < bestD 而不是 d <= bestD?题目要求"绝对差相同时,编号较小的更近"。用严格小于更新时,只有"更近"才会替换当前答案——遇到相同距离时保留原来的(也就是编号更小的),恰好符合题意。这类"并列取最优"的题都用这个技巧。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
stoi(s.substr(j,2), nullptr, 16) | 解析十六进制像素 | 每 2 个字符一个像素 |
| 排序 lambda | 选前 16 种 | 次数降序、灰阶值升序 |
printf("%02X", rep[k]) | 第一行 | %02X 保证两位,总长恰好 32 |
if (d < bestD) | 最近邻 | 严格小于 → 并列自动取小编号 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
| 16 个不同灰阶各出现 1 次 | 按灰阶值升序取前 16 种 | 次数全相同 → 灰阶值小的优先 |
| 某灰阶出现次数最多 | 该灰阶编号为 0 | 次数最多者编号 0 |
| 距离并列的灰阶 | 映射到编号较小的那一种 | 第 0 种 0x10、第 1 种 0x20,则 0x18 映射到 0 |
| 第一行长度 | 必须是 32 个字符 | 每项两位十六进制 |
| 压缩后像素 | 每个像素一位十六进制 | 如编号 10 输出 A |
%02X),总长恰好 32。一个 256 长度的计数数组和若干小数组。
✅ 规模极小,任何实现都瞬间完成。这题的难点在于把三条规则都实现正确,而不是效率。
// 十六进制解析与输出 int v = stoi("AF", nullptr, 16); // 175 printf("%02X", 175); // "AF"(两位大写) printf("%X", 10); // "A"(一位) // 多关键字排序(次数降序,值升序) sort(vals.begin(), vals.end(), [](int a, int b) { if (cntv[a] != cntv[b]) return cntv[a] > cntv[b]; return a < b; }); // 并列取最优(保留最先遇到的) int best = 0, bestD = INT_MAX; for (int k = 0; k < 16; k++) { int d = abs(v - rep[k]); if (d < bestD) { bestD = d; best = k; } // 严格小于 }
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 多关键字排序 | 主键降序、次键升序 | 排行榜、Top-K 统计 |
| 并列取最优 | 严格小于更新 | 最近邻、最小值多个并列的题目 |
| 十六进制格式化 | %02X / %X | 所有需要固定/可变宽度十六进制输出的题 |