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

旧城等待， 2023-09-27 15:55 28阅读 0赞

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

<table> 
 <tbody> 
  <tr> 
   <td style="width:121px;">试题编号：</td> 
   <td>202212-3</td> 
  </tr> 
  <tr> 
   <td style="width:121px;">试题名称：</td> 
   <td>JPEG 解码</td> 
  </tr> 
  <tr> 
   <td style="width:121px;">时间限制：</td> 
   <td>1.0s</td> 
  </tr> 
  <tr> 
   <td style="width:121px;">内存限制：</td> 
   <td>512.0MB</td> 
  </tr> 
  <tr> 
   <td style="width:121px;">问题描述：</td> 
   <td> <h3>问题背景</h3> <p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;四年一度的世界杯即将画上尾声。在本次的世界杯比赛中，视频助理裁判（Video Assistant Referee, VAR）的应用可谓是大放异彩。VAR 使用视频回放技术帮助主裁判作出正确判罚决定。西西艾弗岛足球联赛的赛场上也引入了一套 VAR 设备。作为技术供应商的技术主管小C，需要存储和编码 VAR 产生的图像数据。小 C 分析比较发现，JPEG 编码算法可以达到较好的压缩效果，并且质量损失是可以接受的。因此，小 C 决定使用 JPEG 编码算法来存储和传输图像数据。JPEG 是一种常用的图片有损压缩算法，它的压缩率高，但是压缩后的图片质量下降较多。JPEG 图片的压缩率一般在 10:1 到 20:1 之间，一般用于存储照片等图片质量要求不高的场景。</p> <p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;为了简化问题，我们以灰度图片为例，介绍 JPEG 编码算法的过程。一张灰度图片，可以被视为由多个像素点组成。每个像素点对应一个 0 到 255 之间的数值，用于表示像素点的亮度。JPEG 编码算法将图片分割为&nbsp;8×8&nbsp;的小块，每个小块被称作一个最小编码单元。对每个小块进行如下的计算：</p> 
    <ol> 
     <li>将每个像素点的数值减去 128，使得每个像素点的数值都在 -128 到 127 之间。</li> 
     <li>将每个小块的像素点排成一个&nbsp;8×8&nbsp;的矩阵，并对矩阵进行离散余弦变换（DCT）。进行离散余弦变换后，仍然得到一个&nbsp;8×8&nbsp;的矩阵，矩阵中的每个元素都是实数，并且所得矩阵的左上方的数字的绝对值较大，右下方的数字的绝对值较小，甚至接近 0。</li> 
     <li>对矩阵进行量化操作。量化操作是指将矩阵中的每个元素都除以一个数字，并取整数。量化操作的目的是为了减少矩阵中的数据，从而减少编码后的文件大小。量化操作的数字越大，矩阵中的数据就越少，但是压缩后的图片质量也会越差。</li> 
     <li>对矩阵进行 Z 字形扫描。Z 字形扫描是指从左上角开始，沿着 Z 字形的路径扫描矩阵中的元素，将扫描到的元素依次排成一个数组，由于 Z 字形扫描的路径是从左上角到右下角，数组结尾处可能存在着连续的 0，为了节省空间，可以不存储这些连续的 0。得到的数据被称为扫描数据。</li> 
    </ol><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;最后，将得到的各个小块的扫描数据采用哈夫曼编码进行压缩，并置于必要的数据结构中，就能得到一张 JPEG 图片了。</p> <h3>问题描述</h3> <p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;在本题中，你需要实现一个能够解码 JPEG 图片的一个最小编码单元的程序。解码的步骤与上述编码的步骤相反，具体的步骤是：</p> 
    <ol> 
     <li> <p>读入量化矩阵&nbsp;Qi,j，其中&nbsp;i,j&nbsp;的取值范围为&nbsp;0∼7。</p> </li> 
     <li> <p>初始化一个&nbsp;8×8&nbsp;的矩阵&nbsp;M，令&nbsp;Mi,j=0。</p> </li> 
     <li> <p>读入扫描数据，将扫描数据按照这样的顺序写入矩阵&nbsp;M：从左上角&nbsp;M0,0&nbsp;开始，接下来填充它的右侧相邻的元素&nbsp;M0,1，然后依次向左下方填充直至&nbsp;M1,0，接下来从它下侧相邻的元素&nbsp;M2,0&nbsp;开始，依次向右上方填充直至&nbsp;M0,2，依次类推，循环往复，直至填充满整个矩阵或用尽所有扫描数据，如图所示。</p>  <img alt="" height="409" src="https://img-blog.csdnimg.cn/7da5b7a789d54898a1eb3eea9891941b.png" width="680">  填充顺序  </li> 
     <li> <p>将矩阵&nbsp;M&nbsp;中的每个元素都乘以量化矩阵&nbsp;Q&nbsp;中的对应元素。</p> </li> 
     <li> <p>对矩阵&nbsp;M&nbsp;进行离散余弦逆变换，得到一个&nbsp;8×8&nbsp;的矩阵&nbsp;M′。其中，逆变换的公式如下：<img alt="" height="141" src="https://img-blog.csdnimg.cn/210e0894a124496da0b3c6f40eede171.png" width="924"></p> </li> 
     <li> <p>将矩阵&nbsp;M′&nbsp;中的每个元素都加上&nbsp;128，并取最接近的整数（四舍五入）。如果得到的整数大于&nbsp;255，则取&nbsp;255；如果得到的整数小于&nbsp;0，则取&nbsp;0。得到的矩阵即为解码后的图片。例如，假设给定的量化矩阵是：</p> <p><img alt="" height="239" src="https://img-blog.csdnimg.cn/67bd479ef37f4274a1cdd68d2caabf58.png" width="420"></p> <p>给出的扫描数据是：-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，那么填充后的矩阵&nbsp;M&nbsp;是：</p> <p><img alt="" height="237" src="https://img-blog.csdnimg.cn/db1e38cabfa4482790fb64170afb6b38.png" width="387"></p> <p>&nbsp;与量化矩阵逐项相乘后的矩阵是：</p> <p><img alt="" height="246" src="https://img-blog.csdnimg.cn/ea59073ec4a1482bbacd8a36f3ff1808.png" width="460"></p> <p>&nbsp;经过离散余弦逆变换后的矩阵&nbsp;M′&nbsp;是：<img alt="" height="235" src="https://img-blog.csdnimg.cn/31c27dd612e74ab4bb09bb514db70395.png" width="690"></p> <p>经过加&nbsp;128&nbsp;后并取整的矩阵是：</p> <p><img alt="" height="234" src="https://img-blog.csdnimg.cn/2e042de7836a46a58775517bda93c9f4.png" width="377"></p> </li> 
    </ol><h3>输入格式</h3> <p>从标准输入读入数据。</p> <p>输入的前 8 行，每行有空格分隔 8 个正整数，是量化矩阵。</p> <p>接下来的 1 行是 1 个正整数&nbsp;n，表示扫描数据的个数。</p> <p>接下来的 1 行是 1 个数字&nbsp;T，取值为 0、1 或 2，表示要进行的任务。</p> <p>接下来的 1 行，有空格分隔的&nbsp;n&nbsp;个整数，是扫描数据。</p> <h3>输出格式</h3> <p>输出到标准输出中。</p> <p>输出共 8 行，每行有 8 个空格分隔的整数，表示一个图像矩阵。</p> <p>当&nbsp;T&nbsp;取 0 时，输出填充（步骤 3）后的图像矩阵；当&nbsp;T&nbsp;取 1 时，输出量化（步骤 4）后的图像矩阵；当&nbsp;T&nbsp;取 2 时，输出最终的解码结果。</p> <h3>样例输入</h3> 
    <blockquote>
      16 11 10 16 24 40 51 61 
     <br> 12 12 14 19 26 58 60 55 
     <br> 14 13 16 24 40 57 69 56 
     <br> 14 17 22 29 51 87 80 62 
     <br> 18 22 37 56 68 109 103 77 
     <br> 24 35 55 64 81 104 113 92 
     <br> 49 64 78 87 103 121 120 101 
     <br> 72 92 95 98 112 100 103 99 
     <br> 26 
     <br> 2 
     <br> -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 
    </blockquote> <h3>样例输出</h3> 
    <blockquote>
      62 65 57 60 72 63 60 82 
     <br> 57 55 56 82 108 87 62 71 
     <br> 58 50 60 111 148 114 67 65 
     <br> 65 55 66 120 155 114 68 70 
     <br> 70 63 67 101 122 88 60 78 
     <br> 71 71 64 70 80 62 56 81 
     <br> 75 82 67 54 63 65 66 83 
     <br> 81 94 75 54 68 81 81 87 
    </blockquote> <h3>样例说明</h3> 
    <blockquote> 
     <p>本组样例即为题目描述中的样例。</p> 
    </blockquote> <h3>子任务</h3> <p>对于 20% 的数据，有&nbsp;T=0；</p> <p>对于 40% 的数据，有&nbsp;T=0&nbsp;或&nbsp;1；</p> <p>对于 100% 的数据，有&nbsp;T∈{0,1,2}，且&nbsp;n∈[0,64]，并且量化矩阵中的各个元素&nbsp;qi,j&nbsp;满足&nbsp;0&lt;qi,j&lt;256，扫描序列中的各个元素&nbsp;mi&nbsp;满足&nbsp;−256&lt;mi&lt;256。</p> <h3>提示</h3> <p>在 C/C++ 语言中，可以通过包含&nbsp;<code>math.h</code>（C 语言）或&nbsp;<code>cmath</code>（C++ 语言）来使用数学函数。&nbsp;π&nbsp;的值可以通过表达式&nbsp;<code>acos(-1)</code>&nbsp;获得。</p> <p>在 Python 语言中，可以通过&nbsp;<code>from math import pi</code>&nbsp;引入&nbsp;π。</p> <p>在 Java 语言中，可以使用&nbsp;<code>Math.PI</code>&nbsp;来获取&nbsp;π&nbsp;的值.</p> </td> 
  </tr> 
 </tbody> 
</table>

**真题来源：**[JPEG 解码][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;
    }

**运行结果：** ![651e6effaafc421d924eef242d03e37d.png][]

--------------------

借鉴： [ShowerSong][]

[CCF-CSP]: https://blog.csdn.net/weixin_53919192/article/details/124893395?spm=1001.2014.3001.5502
[JPEG]: http://118.190.20.162/view.page?gpid=T158
[651e6effaafc421d924eef242d03e37d.png]: https://img-blog.csdnimg.cn/651e6effaafc421d924eef242d03e37d.png
[ShowerSong]: https://blog.csdn.net/qq_51879318/article/details/129264026?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167872365816782427415568%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=167872365816782427415568&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-3-129264026-null-null.142%5Ev73%5Epc_search_v2,201%5Ev4%5Eadd_ask,239%5Ev2%5Einsert_chatgpt&utm_term=202212-&spm=1018.2226.3001.4187