草庐IT

CCF-CSP真题《202212-3 JPEG 解码》思路+python，c++满分题解

Hulake_ 2023-04-22 原文

想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全

试题编号：202212-3
试题名称：JPEG 解码
时间限制：1.0s
内存限制：512.0MB
问题描述：

问题背景

        四年一度的世界杯即将画上尾声。在本次的世界杯比赛中，视频助理裁判（Video Assistant Referee, VAR）的应用可谓是大放异彩。VAR 使用视频回放技术帮助主裁判作出正确判罚决定。西西艾弗岛足球联赛的赛场上也引入了一套 VAR 设备。作为技术供应商的技术主管小C，需要存储和编码 VAR 产生的图像数据。小 C 分析比较发现，JPEG 编码算法可以达到较好的压缩效果，并且质量损失是可以接受的。因此，小 C 决定使用 JPEG 编码算法来存储和传输图像数据。JPEG 是一种常用的图片有损压缩算法，它的压缩率高，但是压缩后的图片质量下降较多。JPEG 图片的压缩率一般在 10:1 到 20:1 之间，一般用于存储照片等图片质量要求不高的场景。

        为了简化问题，我们以灰度图片为例，介绍 JPEG 编码算法的过程。一张灰度图片，可以被视为由多个像素点组成。每个像素点对应一个 0 到 255 之间的数值，用于表示像素点的亮度。JPEG 编码算法将图片分割为 8×8 的小块，每个小块被称作一个最小编码单元。对每个小块进行如下的计算：

  1. 将每个像素点的数值减去 128，使得每个像素点的数值都在 -128 到 127 之间。
  2. 将每个小块的像素点排成一个 8×8 的矩阵，并对矩阵进行离散余弦变换（DCT）。进行离散余弦变换后，仍然得到一个 8×8 的矩阵，矩阵中的每个元素都是实数，并且所得矩阵的左上方的数字的绝对值较大，右下方的数字的绝对值较小，甚至接近 0。
  3. 对矩阵进行量化操作。量化操作是指将矩阵中的每个元素都除以一个数字，并取整数。量化操作的目的是为了减少矩阵中的数据，从而减少编码后的文件大小。量化操作的数字越大，矩阵中的数据就越少，但是压缩后的图片质量也会越差。
  4. 对矩阵进行 Z 字形扫描。Z 字形扫描是指从左上角开始，沿着 Z 字形的路径扫描矩阵中的元素，将扫描到的元素依次排成一个数组，由于 Z 字形扫描的路径是从左上角到右下角，数组结尾处可能存在着连续的 0，为了节省空间，可以不存储这些连续的 0。得到的数据被称为扫描数据。

        最后，将得到的各个小块的扫描数据采用哈夫曼编码进行压缩，并置于必要的数据结构中，就能得到一张 JPEG 图片了。

问题描述

        在本题中，你需要实现一个能够解码 JPEG 图片的一个最小编码单元的程序。解码的步骤与上述编码的步骤相反，具体的步骤是：

  1. 读入量化矩阵 Qi,j，其中 i,j 的取值范围为 0∼7。

  2. 初始化一个 8×8 的矩阵 M，令 Mi,j=0。

  3. 读入扫描数据，将扫描数据按照这样的顺序写入矩阵 M：从左上角 M0,0 开始，接下来填充它的右侧相邻的元素 M0,1，然后依次向左下方填充直至 M1,0，接下来从它下侧相邻的元素 M2,0 开始，依次向右上方填充直至 M0,2，依次类推，循环往复，直至填充满整个矩阵或用尽所有扫描数据，如图所示。

    填充顺序

  4. 将矩阵 M 中的每个元素都乘以量化矩阵 Q 中的对应元素。

  5. 对矩阵 M 进行离散余弦逆变换，得到一个 8×8 的矩阵 M′。其中，逆变换的公式如下：

  6. 将矩阵 M′ 中的每个元素都加上 128，并取最接近的整数（四舍五入）。如果得到的整数大于 255，则取 255；如果得到的整数小于 0，则取 0。得到的矩阵即为解码后的图片。例如，假设给定的量化矩阵是：

    给出的扫描数据是：-26, -3, 0, -3, -2, -6, 2, -4, 1, -3, 1, 1, 5, 1, 2, -1, 1, -1, 2, 0, 0, 0, 0, 0, -1 -1，那么填充后的矩阵 M 是：

     与量化矩阵逐项相乘后的矩阵是：

     经过离散余弦逆变换后的矩阵 M′ 是：

    经过加 128 后并取整的矩阵是：

输入格式

从标准输入读入数据。

输入的前 8 行，每行有空格分隔 8 个正整数，是量化矩阵。

接下来的 1 行是 1 个正整数 n，表示扫描数据的个数。

接下来的 1 行是 1 个数字 T，取值为 0、1 或 2，表示要进行的任务。

接下来的 1 行，有空格分隔的 n 个整数，是扫描数据。

输出格式

输出到标准输出中。

输出共 8 行，每行有 8 个空格分隔的整数，表示一个图像矩阵。

当 T 取 0 时，输出填充（步骤 3）后的图像矩阵；当 T 取 1 时，输出量化（步骤 4）后的图像矩阵；当 T 取 2 时，输出最终的解码结果。

样例输入

16 11 10 16 24 40 51 61
12 12 14 19 26 58 60 55
14 13 16 24 40 57 69 56
14 17 22 29 51 87 80 62
18 22 37 56 68 109 103 77
24 35 55 64 81 104 113 92
49 64 78 87 103 121 120 101
72 92 95 98 112 100 103 99
26
2
-26 -3 0 -3 -2 -6 2 -4 1 -3 1 1 5 1 2 -1 1 -1 2 0 0 0 0 0 -1 -1

样例输出

62 65 57 60 72 63 60 82
57 55 56 82 108 87 62 71
58 50 60 111 148 114 67 65
65 55 66 120 155 114 68 70
70 63 67 101 122 88 60 78
71 71 64 70 80 62 56 81
75 82 67 54 63 65 66 83
81 94 75 54 68 81 81 87

样例说明

本组样例即为题目描述中的样例。

子任务

对于 20% 的数据，有 T=0；

对于 40% 的数据，有 T=0 或 1；

对于 100% 的数据，有 T∈{0,1,2}，且 n∈[0,64]，并且量化矩阵中的各个元素 qi,j 满足 0<qi,j<256，扫描序列中的各个元素 mi 满足 −256<mi<256。

提示

在 C/C++ 语言中，可以通过包含 math.h（C 语言）或 cmath（C++ 语言）来使用数学函数。 π 的值可以通过表达式 acos(-1) 获得。

在 Python 语言中，可以通过 from math import pi 引入 π。

在 Java 语言中，可以使用 Math.PI 来获取 π 的值.

真题来源：JPEG 解码

感兴趣的同学可以如此编码进去进行练习提交

python题解：

c++满分题解：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 8;

int n, T;

int a[N][N], M[N][N], M1[N][N];
double M2[N][N];
int q[64];

double trans(double i, double j)
{
    double res = 0;
    for (int u = 0; u <= 7; u ++ )
        for (int v = 0; v <= 7; v ++ )
            if (u == 0 && v == 0)
                res += (double)M1[u][v] * cos(0) * cos(0) / 2.0;
            else if (u == 0)
                res += (double)M1[u][v] * sqrt(0.5) * cos(acos(-1) * (i + 0.5) * double(u) / 8.0) * cos(acos(-1) * (j + 0.5) * v / 8.0);
            else if (v == 0)
                res += (double)M1[u][v] * sqrt(0.5) * cos(acos(-1) * (i + 0.5) * double(u) / 8.0) * cos(acos(-1) * (j + 0.5) * v / 8.0);
            else
                res += (double)M1[u][v] * cos(acos(-1) * (i + 0.5) * double(u) / 8) * cos(acos(-1) * (j + 0.5) * double(v) / 8.0);

    return (double)res / 4.0;    
}

int main()
{
    for (int i = 0; i < 8; i ++ )
        for (int j = 0; j < 8; j ++ )
            cin >> a[i][j];
    
    cin >> n >> T;
    
    for (int i = 0; i < n; i ++ )
        cin >> q[i];
    
    // T1.
    int k = 0; 
    for (int i = 0; i < 8; i ++ )
        if (i % 2 == 0)
        {
            for (int j = 0; j <= i; j ++ )
                M[i - j][j] = q[k ++ ];
        }
        else
            for (int j = 0; j <= i; j ++ )
                M[j][i - j] = q[k ++ ];
        
    for (int i = 8; i < 15; i ++ )
        if (i % 2 == 0)
            for (int j = i - 7; j <= 7; j ++ )
                M[i - j][j] = q[k ++ ];
        else
            for (int j = i - 7; j <= 7; j ++ )
                M[j][i - j] = q[k ++ ];
    
    
    // T2.
    for (int i = 0; i < 8; i ++ )
        for (int j = 0; j < 8; j ++ )
            M1[i][j] = M[i][j] * a[i][j];
        
    // T3.    
    for (int i = 0; i < 8; i ++ )
        for (int j = 0; j < 8; j ++ )
        {
            M2[i][j] = round(trans(i, j) + 128);
            if (M2[i][j] > 255) M2[i][j] = 255;
            if (M2[i][j] < 0) M2[i][j] = 0;
        }
            
    // 输出    
    if (T == 0)
        for (int i = 0; i < 8; i ++ )
        {
            for (int j = 0; j < 8; j ++ )
                cout << M[i][j] << " ";
            cout << endl;
        }
    
    if (T == 1)
        for (int i = 0; i < 8; i ++ )
        {
            for (int j = 0; j < 8; j ++ )
                cout << M1[i][j] << " ";
            cout << endl;
        }
    
    if (T == 2)
        for (int i = 0; i < 8; i ++ )
        {
            for (int j = 0; j < 8; j ++ )
                cout <<  M2[i][j] << " ";
            cout << endl;
        }
    return 0;
}

运行结果： 

借鉴： ShowerSong

c++题解xffxff0cxff0python算法

有关CCF-CSP真题《202212-3 JPEG 解码》思路+python，c++满分题解的更多相关文章

  1. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  2. Python 相当于 Perl/Ruby ||= - 2

    这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Pythonconditionalassignmentoperator对于这样一个简单的问题表示歉意，但是谷歌搜索||=并不是很有帮助；)Python中是否有与Ruby和Perl中的||=语句等效的语句？例如:foo="hey"foo||="what"#assignfooifit'sundefined#fooisstill"hey"bar||="yeah"#baris"yeah"另外，类似这样的东西的通用术语是什么？条件分配是我的第一个猜测，但Wikipediapage跟我想的不太一样。

  3. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  4. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  5. python - 如何读取 MIDI 文件、更改其乐器并将其写回？ - 2

    我想解析一个已经存在的.mid文件，改变它的乐器，例如从“acousticgrandpiano”到“violin”，然后将它保存回去或作为另一个.mid文件。根据我在文档中看到的内容，该乐器通过program_change或patch_change指令进行了更改，但我找不到任何在已经存在的MIDI文件中执行此操作的库.他们似乎都只支持从头开始创建的MIDI文件。 最佳答案 MIDIpackage会为您完成此操作，但具体方法取决于midi文件的原始内容。一个MIDI文件由一个或多个音轨组成，每个音轨是十六个channel中任何一个上的

  6. 「Python｜Selenium｜场景案例」如何定位iframe中的元素？ - 2

    本文主要介绍在使用Selenium进行自动化测试或者任务时，对于使用了iframe的页面，如何定位iframe中的元素文章目录场景描述解决方案具体代码场景描述当我们在使用Selenium进行自动化测试的时候，可能会遇到一些界面或者窗体是使用HTML的iframe标签进行承载的。对于iframe中的标签，如果直接查找是无法找到的，会抛出没有找到元素的异常。比如近在咫尺的例子就是，CSDN的登录窗体就是使用的iframe，大家可以尝试通过F12开发者模式查看到的tag_name,class_name,id或者xpath来定位中的页面元素，会抛出NoSuchElementException异常。解决

  7. python ffmpeg 使用 pyav 转换 一组图像 到 视频 - 2

    2022/8/4更新支持加入水印水印必须包含透明图像，并且水印图像大小要等于原图像的大小pythonconvert_image_to_video.py-f30-mwatermark.pngim_dirout.mkv2022/6/21更新让命令行参数更加易用新的命令行使用方法pythonconvert_image_to_video.py-f30im_dirout.mkvFFMPEG命令行转换一组JPG图像到视频时，是将这组图像视为MJPG流。我需要转换一组PNG图像到视频，FFMPEG就不认了。pyav内置了ffmpeg库，不需要系统带有ffmpeg工具因此我使用ffmpeg的python包装p

  8. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  9. python - 是否可以使用 Ruby 或 Python 禁用 anchor /引用来发出有效的 YAML？ - 2

    是否可以在PyYAML或Ruby的Psych引擎中禁用创建anchor和引用(并有效地显式列出冗余数据)？也许我在网上搜索时遗漏了一些东西，但在Psych中似乎没有太多可用的选项，而且我也无法确定PyYAML是否允许这样做.基本原理是我必须序列化一些数据并将其以可读的形式传递给一个不是真正的技术同事进行手动验证。有些数据是多余的，但我需要以最明确的方式列出它们以提高可读性(anchor和引用是提高效率的好概念，但不是人类可读性)。Ruby和Python是我选择的工具，但如果有其他一些相当简单的方法来“展开”YAML文档，它可能就可以了。 最佳答案

  10. .net - .NET 将如何影响 Python 和 Ruby 应用程序？ - 2

    我很好奇.NET将如何影响Python和Ruby应用程序。用IronPython/IronRuby编写的应用程序是否会非常特定于.NET环境，以至于它们实际上将变得特定于平台？如果他们不使用任何.NET功能，那么IronPython/IronRuby相对于非.NET同类产品的优势是什么？ 最佳答案 我不能说任何关于IronRuby的东西，但是大多数Python实现(如IronPython、Jython和PyPy)都试图尽可能忠实于CPython实现。不过，IronPython正在迅速成为这方面的佼佼者之一，并且在PlanetPyth

随机推荐