#2395. 图像压缩

图像压缩

[GESP202306 四级] 图像压缩

题目描述

图像是由很多的像素点组成的。如果用 00 表示黑,255255 表示白,00255255 之间的值代表不同程度的灰色,则可以用一个字节表达一个像素(取值范围为十进制 0-255、十六进制 00-FF)。这样的像素组成的图像,称为 256256 级灰阶的灰度图像。

现在希望将 256256 级灰阶的灰度图像压缩为 1616 级灰阶,即每个像素的取值范围为十进制 0-15、十六进制 0-F。压缩规则为:统计出每种灰阶的数量,取数量最多的前 1616 种灰阶(如某种灰阶的数量与另外一种灰阶的数量相同,则以灰阶值从小到大为序),分别编号 0-F(最多的编号为 0,以此类推)。其他灰阶转换到最近的 1616 种灰阶之一,将某个点的灰阶值(灰度,而非次数)与 1616 种灰阶中的一种相减,绝对值最小即为最近,如果绝对值相等,则编号较小的灰阶更近。

输入格式

输入第 11 行为一个正整数 n(10n20)n(10\le n \le 20),表示接下来有 nn 行数据组成一副 256256 级灰阶的灰度图像。

22 行开始的 nn 行,每行为长度相等且为偶数的字符串,每两个字符用十六进制表示一个像素。约定输入的灰度图像至少有 1616 种灰阶。约定每行最多 2020 个像素。

输出格式

第一行输出压缩选定的 1616 种灰阶的十六进制编码,共计 3232 个字符。

第二行开始的 nn 行,输出压缩后的图像,每个像素一位十六进制数表示压缩后的灰阶值。

样例 #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

提示

【样例 11 解释】

灰阶 ABCFFF 出现 1414 次,00 出现 1010 次,CB 出现 99 次,09 出现 77 次,AC 出现 66 次,07 出现 55 次,101198 出现 44 次,011B6776FC 出现 33 次。