G4002 [GESP202306 四级] 图像压缩 题解

知识点：进制转换、频数统计、多关键字排序、模拟。

解题思路

将每两个十六进制字符解成一个像素，统计256种值的频次。按频次降序、像素值升序选16项调色板，再为每个像素找差值最小的调色板编号。

为什么正确

排序落实调色板选取规则，逐像素穷举16个候选得到最接近颜色；相同距离保留先出现的编号。

易错点

颜色用两位大写十六进制输出，压缩后的索引用一位；频次和距离并列规则不能遗漏。

复杂度

设像素数P，时间O(P+256log256+16P)，空间O(P+256)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<string>a(n);
    int cnt[256]= {
    }
    ;
    for(string &s:a) {
        cin>>s;
        for(int j=0;j<(int)s.size();j+=2)cnt[stoi(s.substr(j,2),nullptr,16)]++;
    }
    vector<int>v(256);
    iota(v.begin(),v.end(),0);
    sort(v.begin(),v.end(),[&](int x,int y){return cnt[x]!=cnt[y]?cnt[x]>cnt[y]:x<y;});
    string hex="0123456789ABCDEF";
    for(int i=0;i<16;i++)cout<<hex[v[i]/16]<<hex[v[i]%16];
    cout<<"\n";
    for(string s:a) {
        for(int j=0;j<(int)s.size();j+=2) {
            int x=stoi(s.substr(j,2),nullptr,16),best=0;
            for(int k=1;k<16;k++)if(abs(x-v[k])<abs(x-v[best]))best=k;
            cout<<hex[best];
        }
        cout<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。