C++
B3851 [GESP202306 四级] 图像压缩
admin SU @ 2025-5-5 11:55:15

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$ 次。

admin SU @ 2025-5-5 11:57:49

已修改

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

// 定义结构体，用于存储灰阶值（十六进制形式）及其出现的次数
struct GrayLevel {
    string grayLevelHex;  // 存储十六进制形式的灰阶值，例如 "A0"
    int occurrenceCount;  // 存储该灰阶值出现的次数
};

// 用于存储所有读取的原始图像数据的向量，每个元素是一行十六进制表示的像素数据
vector<string> originalImageLines;

// 用于统计每种灰阶出现次数的 map，键是十六进制灰阶值，值是出现的次数
map<string, int> grayLevelOccurrenceMap;

// 用于存储最终选定的 16 种灰阶及其对应编码（0-F）的 map，键是十六进制灰阶值，值是编码字符
map<string, char> selectedGrayLevelEncodingMap;

// 存储所有灰阶及其出现次数的结构体向量
vector<GrayLevel> grayLevelVector;

// 自定义比较函数，用于对结构体向量 grayLevelVector 进行排序
// 先按出现次数从多到少排序，如果出现次数相同，则按灰阶值的字典序从小到大排序
bool compareGrayLevels(GrayLevel a, GrayLevel b) {
    if (a.occurrenceCount != b.occurrenceCount) {
        return a.occurrenceCount > b.occurrenceCount;
    }
    return a.grayLevelHex < b.grayLevelHex;
}

// 将十六进制字符串转换为十进制整数的函数
int hexToDec(string hexStr) {
    int result = 0;
    for (int i = 0; i <= 1; i++) {
        char ch = hexStr[i];
        int value;
        if (ch >= 'A') {
            value = ch - 'A' + 10;
        } else {
            value = ch - '0';
        }
        if (i == 0) {
            result += value * 16;
        } else {
            result += value;
        }
    }
    return result;
}

// 找到与给定灰阶最接近的已选灰阶的函数
string findClosestGrayLevel(string targetGrayLevel, vector<GrayLevel> selectedGrayLevels) {
    int minDistance = 99999999;
    string closestGrayLevel;
    for (int i = 0; i < 16; i++) {
        int distance = abs(hexToDec(targetGrayLevel) - hexToDec(selectedGrayLevels[i].grayLevelHex));
        if (distance < minDistance) {
            minDistance = distance;
            closestGrayLevel = selectedGrayLevels[i].grayLevelHex;
        }
    }
    return closestGrayLevel;
}

int main() {
    int imageLineCount;
    // 读取图像的行数
    cin >> imageLineCount;

    for (int i = 1; i <= imageLineCount; i++) {
        string line;
        // 读取每一行图像数据
        cin >> line;
        originalImageLines.push_back(line);

        int lineLength = line.size();
        for (int j = 0; j < lineLength - 1; j += 2) {
            string grayLevel = line.substr(j, 2);
            // 统计每种灰阶出现的次数
            grayLevelOccurrenceMap[grayLevel]++;
        }
    }

    // 将统计的灰阶及其出现次数存入结构体向量中
    for (const auto& pair : grayLevelOccurrenceMap) {
        GrayLevel grayLevel;
        grayLevel.grayLevelHex = pair.first;
        grayLevel.occurrenceCount = pair.second;
        grayLevelVector.push_back(grayLevel);
    }

    // 对结构体向量进行排序
    sort(grayLevelVector.begin(), grayLevelVector.end(), compareGrayLevels);

    // 输出选定的 16 种灰阶的十六进制编码，并为它们分配编码（0-F）
    for (int i = 0; i < 16; i++) {
        cout << grayLevelVector[i].grayLevelHex;
        if (i <= 9) {
            selectedGrayLevelEncodingMap[grayLevelVector[i].grayLevelHex] = char(i + '0');
        } else {
            selectedGrayLevelEncodingMap[grayLevelVector[i].grayLevelHex] = char('A' + i - 10);
        }
    }
    cout << endl;

    int firstLineLength = originalImageLines[0].size();
    for (int i = 0; i < imageLineCount; i++) {
        for (int j = 0; j < firstLineLength - 1; j += 2) {
            string grayLevel = originalImageLines[i].substr(j, 2);
            if (selectedGrayLevelEncodingMap.find(grayLevel) != selectedGrayLevelEncodingMap.end()) {
                // 如果当前灰阶在选定的 16 种灰阶中，输出对应的编码
                cout << selectedGrayLevelEncodingMap[grayLevel];
            } else {
                // 否则找到最接近的已选灰阶并输出其编码
                string closestGrayLevel = findClosestGrayLevel(grayLevel, grayLevelVector);
                cout << selectedGrayLevelEncodingMap[closestGrayLevel];
            }
        }
        cout << endl;
    }

    return 0;
}

admin SU @ 2025-5-5 11:55:46

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

// 定义一个结构体，用于存储灰阶及其出现的次数
struct jieji{
    string strvec;  // 存储十六进制表示的灰阶
    int numvec;     // 存储该灰阶出现的次数
};

// 自定义比较函数，用于对结构体向量进行排序
// 优先按出现次数从多到少排序，若次数相同，则按灰阶值从小到大排序
bool cmp(jieji a, jieji b){
    if(a.numvec != b.numvec){
        return a.numvec > b.numvec;
    }else{
        return a.strvec < b.strvec;
    }
}

// 存储原始图像数据的向量
vector<string>  oldBm;

// 将十六进制字符串转换为十进制整数的函数
int to10(string ttt){  // 例如输入 "A0"
    int res = 0;
    for(int i=0;i<=1;i++){
        char t = ttt[i];
        int tt;
        // 判断字符是否为字母（表示大于 9 的十六进制数）
        if(t>='A'){
            tt = t - 'A' + 10;
        }else{
            tt =t -'0';
        }
        // 计算十六进制数对应的十进制值
        if(i==0){
            res += tt*16;
        }else{
            res += tt;
        }
    }
    return res;
}

// 找到最接近给定灰阶的已选灰阶的函数
string newBm(string ttt){  // 例如输入 "A0"
    int Min = 99999999;
    string ttttttt="";
    // 遍历已选的 16 种灰阶
    for(int i=0;i<16;i++){
        // 计算当前灰阶与已选灰阶的差值的绝对值
        if(abs(to10(ttt) - to10(vec[i].strvec)) < Min){
            Min = abs(to10(ttt) - to10(vec[i].strvec));
            ttttttt = vec[i].strvec;
        }
    }
    return ttttttt;
}

int main() {
    int n;
    // 读取图像的行数
    cin >> n;
    for(int i=1;i<=n;i++){
        string str;
        // 读取每一行图像数据
        cin>>str;
        oldBm.push_back(str);
        int len = str.size();
        // 遍历每一行的十六进制灰阶数据
        for(int i=0;i<len-1;i+=2){
            string ttt = str.substr(i,2);
            // 统计每种灰阶出现的次数
            m1[ttt] += 1;
        }
    }
    
    // 将统计的灰阶及其次数存储到结构体向量中
    for(const auto &m:m1){
        jieji a;
        a.numvec = m.second;
        a.strvec = m.first;
        vec.push_back(a);
    }
    // 对结构体向量进行排序
    sort(vec.begin(),vec.end(),cmp);
    
    // 输出选定的 16 种灰阶的十六进制编码，并为它们分配编号 0-F
    for(int i=0;i<16;i++){
        cout<<vec[i].strvec;
        if(i<=9){
            m2[vec[i].strvec] = char(i+'0');
        }else{
            m2[vec[i].strvec] = char('A'+i-10);
        }
    }
    cout<<endl;
    
    int len = oldBm[0].size();
    // 遍历每一行原始图像数据，进行压缩并输出
    for(int i=0;i<n;i++){
        for(int j=0;j<len-1;j+=2){
            string ttt = oldBm[i].substr(j,2);
            // 如果当前灰阶在选定的 16 种灰阶中，输出对应的编号
            if(m2.find(ttt)!=m2.end()){
                cout<<m2[ttt];
            }else{
                // 否则找到最接近的已选灰阶并输出其编号
                cout<<m2[newBm(ttt)];
            }
        }
        cout<<endl;
    }
    return 0;
}

admin SU @ 2025-5-5 11:55:28

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
/*bool cmp(const string& a,const string& b){
if(a > b){
return  true;
}else{
return  false;
}
}*/
//// 使用自定义比较函数创建 map
//map<int, int, decltype(&cmp)> myMap(cmp);
//map<string,int,decltype(&cmp)> m1(cmp);
map<string,int> m1;
map<string,char> m2;
//vector<string> strvec;
struct jieji{
	string strvec;
	int numvec;
};
vector<jieji> vec;
bool cmp(jieji a,jieji b){
	if(a.numvec != b.numvec){
		return a.numvec > b.numvec;
	}else{
		return a.strvec < b.strvec;
	}
}
vector<string>  oldBm;

int to10(string ttt){//A0
	int res = 0;
	for(int i=0;i<=1;i++){
		char t = ttt[i];
		int tt;
		if(t>='A'){
			tt = t - 'A' + 10;
		}else{
			tt =t -'0';
		}
		if(i==0){
			res += tt*16;
		}else{
			res += tt;
		}
	}
	return res;
}

string newBm(string ttt){//ttt:  A0
	int Min = 99999999;
	string ttttttt="";
	for(int i=0;i<16;i++){
		if(abs(to10(ttt) - to10(vec[i].strvec)) < Min){
			Min = abs(to10(ttt) - to10(vec[i].strvec));
			ttttttt = vec[i].strvec;
		}
	}
	return ttttttt;
}
int main() {
	int n;
	cin >> n;
	for(int i=1;i<=n;i++){
		string str;
		cin>>str;
		oldBm.push_back(str);
		int len = str.size();
		//len/=2;//每行为长度相等且为偶数的字符串
		for(int i=0;i<len-1;i+=2){
			//cout<<<<endl;//提取子串函数
			string ttt = str.substr(i,2);
			m1[ttt] += 1;
		}
	}
	
	for(const auto &m:m1){
		//cout<<m.first<<" "<<m.second<<endl;
		//strvec.push_back(m.first);
		//numvec.push_back(m.second);
		jieji a;
		a.numvec = m.second;
		a.strvec = m.first;
		vec.push_back(a);
	}
	sort(vec.begin(),vec.end(),cmp);
	/*for(const auto &i:vec){
	cout<<i.numvec<<" "<<i.strvec<<endl;
	}*/
	for(int i=0;i<16;i++){
		cout<<vec[i].strvec;
		if(i<=9){
			m2[vec[i].strvec] = char(i+'0');
		}else{
			m2[vec[i].strvec] = char('A'+i-10);
		}
	}
	cout<<endl;
	int len = oldBm[0].size();
	for(int i=0;i<n;i++){//10
		for(int j=0;j<len-1;j+=2){
			//cout<<<<endl;//提取子串函数
			string ttt = oldBm[i].substr(j,2);
			if(m2.find(ttt)!=m2.end()){
				cout<<m2[ttt];
			}else{
				//cout<<"-";
				cout<<m2[newBm(ttt)];
			}
		}
		cout<<endl;
	}
	return 0;
}