你好！我是你的OI教练。这道题《图像压缩》是 GESP 四级的一道典型的大模拟题目，结合了字符串处理、进制转换、结构体排序和贪心匹配。

它不像纯数学题那样抽象，但步骤繁琐，非常考验你把复杂逻辑拆解为代码模块的能力。

我们还是按老规矩，先在草稿纸上把逻辑理顺。

1. 读题关键词：你的“雷达”响了吗？

1. “十六进制表示一个像素”：
   • 输入的是字符串（如 00FFAB...），每两个字符代表一个数。
   • 动作：你需要写一个“切片+转码”的逻辑，把每两个字符（如 CF）切下来，转成整数（207）。
2. “统计...数量最多的前16种”：
   • 这涉及排序。
   • 排序规则：先比次数（大到小），次数一样比数值（小到大）。
   • 结果：选出来的这16个“VIP灰阶”，分别会被分配 ID 0 到 F。注意：排在第0位的 ID 就是 0，以此类推。
3. “最近...编号较小的更近”：
   • 这是压缩的核心。对于原图的每个像素 $P$，你要拿着它去和16个 VIP 灰阶 $V_0, V_1, \dots, V_{15}$ 比距离 $|P - V_i|$。
   • 坑点：如果距离一样（例如 $P=10$，VIP里有 $8$ 和 $12$，距离都是2），选编号（ID）小的那个，而不是数值小的。
   • 实现技巧：当你从 ID 0 遍历到 15 寻找最小值时，只要使用 if (dist < min_dist)（严格小于）更新，自然就能保留编号更小的（因为后面的 ID 只有距离更小才能篡位，距离相等篡位失败）。

2. 预备知识点

• 16进制转10进制：
  • 公式：'A' -> 10。"AB" = 10 * 16 + 11 = 171。
  • C++ 工具：stoi(substr, nullptr, 16) 或者手写转换函数。
• 结构体排序：
  • 定义 struct Pixel { int val; int count; }。
  • 自定义 cmp 函数。
• 模拟与映射：
  • 建立一个 vector<int> palette 存储选出的16个值，下标就是 ID。

3. 启发式教学：草稿纸上的推演

假设输入一行：00 FF 00。

1. 统计：00 出现 2 次，FF 出现 1 次。
2. 排序：
   • 00 (2次) 排第一 $\to$ ID 0。
   • FF (1次) 排第二 $\to$ ID 1。
3. 输出第一行：00FF (即 ID0 的原值 + ID1 的原值)。
4. 压缩：
   • 原像素 00 $\to$ 找最近 $\to$ 离 ID 0 (数值00) 距离0 $\to$ 输出 0。
   • 原像素 FF $\to$ 找最近 $\to$ 离 ID 1 (数值FF) 距离0 $\to$ 输出 1。
   • 原像素 00 $\to$ 输出 0。
   • 结果：010。

4. 标准代码 (NOIP C++14)

/**
 * 题目：B3851 [GESP202306 四级] 图像压缩
 * 考点：字符串切割、进制转换、结构体排序、最近邻匹配
 */

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

using namespace std;

// 1. 定义结构体存储灰阶信息
struct GrayScale {
    int val;    // 灰阶数值 (0-255)
    int count;  // 出现次数
};

// 2. 排序规则：次数优先(降序)，数值次之(升序)
bool cmp(const GrayScale &a, const GrayScale &b) {
    if (a.count != b.count) {
        return a.count > b.count; 
    }
    return a.val < b.val;
}

// 辅助函数：字符转数值 (0-9, A-F)
int charToVal(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    return c - 'A' + 10;
}

// 辅助函数：数值转字符 (0-15 -> 0-F)
char valToChar(int v) {
    if (v >= 0 && v <= 9) return v + '0';
    return v - 10 + 'A';
}

// 辅助函数：将数值转为2位16进制字符串 (如 10 -> "0A")
void printHex2(int v) {
    cout << valToChar(v / 16) << valToChar(v % 16);
}

int main() {
    // IO优化
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    // 存储每一行的原始数值，方便后续压缩
    vector<vector<int>> image(n);
    // 统计桶，下标是灰阶值 0-255
    vector<GrayScale> stats(256);
    
    // 初始化统计桶
    for (int i = 0; i < 256; i++) {
        stats[i].val = i;
        stats[i].count = 0;
    }

    // 3. 读入并解析
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        // 每两个字符为一个像素
        for (size_t j = 0; j < s.length(); j += 2) {
            // 手动解析16进制，比 substr+stoi 快且易控
            int high = charToVal(s[j]);
            int low = charToVal(s[j+1]);
            int val = high * 16 + low;
            
            image[i].push_back(val); // 存入原图
            stats[val].count++;      // 记账
        }
    }

    // 4. 排序选出前16名
    // 注意：虽然只有部分灰阶出现，但我们对所有256种排序也没问题，没出现的count是0排在最后
    sort(stats.begin(), stats.end(), cmp);

    // 提取出的16种灰阶 (palette[i] 对应 ID i)
    vector<int> palette(16);
    
    // 输出第一行：压缩选定的16种灰阶
    for (int i = 0; i < 16; i++) {
        palette[i] = stats[i].val;
        printHex2(palette[i]); // 输出如 "AB"
    }
    cout << endl;

    // 5. 压缩并输出图像
    for (int i = 0; i < n; i++) {
        for (int originalVal : image[i]) {
            int bestID = -1;
            int minDiff = 100000; // 初始化为一个很大的数

            // 遍历16种备选，找最近的
            for (int k = 0; k < 16; k++) {
                int diff = abs(originalVal - palette[k]);
                
                // 核心逻辑：这里用 < 而不是 <=
                // 如果 diff == minDiff，不更新，保留较小的 k (因为 k 是从小到大遍历的)
                // 题目要求：绝对值相等，编号(ID)较小的更近。当前 k 就是 ID。
                if (diff < minDiff) {
                    minDiff = diff;
                    bestID = k;
                }
            }
            
            // 输出压缩后的 ID (一位16进制)
            cout << valToChar(bestID);
        }
        cout << endl;
    }

    return 0;
}

5. 数据生成器 (1.in - 10.in)

为了满足题目要求（至少16种灰阶，偶数长度字符串等），生成器需要做特殊处理。

/**
 * B3851 数据生成器
 * 生成 1.in/1.out ~ 10.in/10.out
 */

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <set>

using namespace std;

// ==========================================
// Part 1: 标准题解逻辑 (用于生成 .out)
// ==========================================
struct GrayScale { int val; int count; };
bool cmp(const GrayScale &a, const GrayScale &b) {
    if (a.count != b.count) return a.count > b.count; 
    return a.val < b.val;
}
int charToVal(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    return c - 'A' + 10;
}
char valToChar(int v) {
    if (v >= 0 && v <= 9) return v + '0';
    return v - 10 + 'A';
}
string intToHex2(int v) {
    string s = "";
    s += valToChar(v / 16);
    s += valToChar(v % 16);
    return s;
}

void solveAndOutput(int n, const vector<string>& raw_lines, ofstream& fout) {
    vector<vector<int>> image(n);
    vector<GrayScale> stats(256);
    for (int i = 0; i < 256; i++) { stats[i].val = i; stats[i].count = 0; }

    for (int i = 0; i < n; i++) {
        for (size_t j = 0; j < raw_lines[i].length(); j += 2) {
            int val = charToVal(raw_lines[i][j]) * 16 + charToVal(raw_lines[i][j+1]);
            image[i].push_back(val);
            stats[val].count++;
        }
    }

    sort(stats.begin(), stats.end(), cmp);
    vector<int> palette(16);
    for (int i = 0; i < 16; i++) {
        palette[i] = stats[i].val;
        fout << intToHex2(palette[i]);
    }
    fout << endl;

    for (int i = 0; i < n; i++) {
        for (int val : image[i]) {
            int bestID = -1, minDiff = 9999;
            for (int k = 0; k < 16; k++) {
                int diff = abs(val - palette[k]);
                if (diff < minDiff) {
                    minDiff = diff;
                    bestID = k;
                }
            }
            fout << valToChar(bestID);
        }
        fout << endl;
    }
}

// ==========================================
// Part 2: 数据构造逻辑
// ==========================================
int randInt(int min, int max) {
    return rand() % (max - min + 1) + min;
}

void makeData(int fileId) {
    string inName = to_string(fileId) + ".in";
    string outName = to_string(fileId) + ".out";
    ofstream fin(inName);
    ofstream fout(outName);

    // 约束: 10 <= N <= 20
    int N;
    if (fileId <= 3) N = 10;
    else if (fileId <= 7) N = randInt(11, 19);
    else N = 20;

    fin << N << endl;

    // 约束: 每行最多20像素(40字符)，长度相等且为偶数
    // 约束: 至少16种灰阶
    int width = randInt(16, 20); // 保证宽一点容易凑齐16种颜色
    vector<string> lines(N);

    // 为了保证至少16种不同颜色，我们先生成一个包含至少16种颜色的池子
    set<int> colorPool;
    while(colorPool.size() < 16) {
        colorPool.insert(randInt(0, 255));
    }
    vector<int> mandatoryColors(colorPool.begin(), colorPool.end());

    // 填充图像
    int colorIdx = 0;
    for (int i = 0; i < N; i++) {
        string line = "";
        for (int j = 0; j < width; j++) {
            int val;
            // 前16个像素强制使用不同的颜色，确保满足题目条件
            if (colorIdx < 16) {
                val = mandatoryColors[colorIdx++];
            } else {
                // 剩下的随机，稍微倾向于重复以测试排序
                if (randInt(0, 10) < 7) val = mandatoryColors[randInt(0, 15)];
                else val = randInt(0, 255);
            }
            line += intToHex2(val);
        }
        lines[i] = line;
        fin << line << endl;
    }

    // 生成答案
    solveAndOutput(N, lines, fout);

    fin.close();
    fout.close();
    cout << "Generated Case " << fileId << endl;
}

int main() {
    srand((unsigned)time(NULL));
    for (int i = 1; i <= 10; i++) {
        makeData(i);
    }
    return 0;
}

教练总结

1. 细节决定成败：这题的逻辑链条很长（输入->解析->统计->排序->映射->输出）。在考场上，建议先把 charToVal 这种小工具写好并测试无误，再写主逻辑。
2. 理解“ID”：很多同学会混淆“数值”和“ID”。
   • 数值是 00-FF (0-255)。
   • ID 是 0-F (0-15)，是数值在排行榜上的名次。
   • 输出的压缩图像是 ID，不是数值！
3. 贪心策略的实现：在找最近邻时，利用循环顺序来自然处理“距离相等选ID小”的要求，是代码简洁的关键。