题解：P13899 [CSPro 28] JPEG 解码

· · 题解

题解：P13899 [CSPro 28] JPEG 解码

一道很吓人的大模拟。

思路

First：Z字形填充

·初始化 8 \times 8 的矩阵 M ，初始化为 0，即M_{i,j} = 0；

·按照题目的那张表，填入数据。

const int cheat[64][2]={
    {0,0},
    {0,1},{1,0},
    {2,0},{1,1},{0,2},
    {0,3},{1,2},{2,1},{3,0},
    {4,0},{3,1},{2,2},{1,3},{0,4},
    {0,5},{1,4},{2,3},{3,2},{4,1},{5,0},
    {6,0},{5,1},{4,2},{3,3},{2,4},{1,5},{0,6},
    {0,7},{1,6},{2,5},{3,4},{4,3},{5,2},{6,1},{7,0},
    {7,1},{6,2},{5,3},{4,4},{3,5},{2,6},{1,7},
    {2,7},{3,6},{4,5},{5,4},{6,3},{7,2},
    {7,3},{6,4},{5,5},{4,6},{3,7},
    {4,7},{5,6},{6,5},{7,4},
    {7,5},{6,6},{5,7},
    {6,7},{7,6},
    {7,7}
};

Second：量化

·将矩阵的对应位置相乘，即 M_{i,j} \times Q_{i,j}；

for(int i=0;i<8;i++){
    for(int j=0;j<8;j++){
        arr[i][j]*=q[i][j];
    }
}

Third：离散余弦逆变换

·根据题目那个很吓人的公式：

M'_{i,j} = \frac{1}{4} \sum_{u=0}^{7} \sum_{v=0}^{7} \alpha(u) \alpha(v) M_{u,v} \cos\left(\frac{\pi}{8}(i + \frac{1}{2})u\right) \cos\left(\frac{\pi}{8}(j + \frac{1}{2})v\right)

其中 \alpha(u) = \begin{cases} \sqrt{\frac{1}{2}} & u = 0 \\ 1 & u \neq 0 \end{cases}

直接模拟就行：

double alaph(int x){
    if(x==0)  return sqrt(0.5);
    else  return 1.0;
}

double calc(int i,int j){
    double res=0;
    for(int u=0;u<8;u++){
        for(int v=0;v<8;v++){
            res+=alaph(u)*alaph(v)*arr[u][v]*cos((pi/8)*(i+0.5)*u)*cos((pi/8)*(j+0.5)*v);
        }
    }
    return res/4;
}

Fourth 取整

·变换完后每个数加 128，然后四舍五入；

·最后限制在 0∼255 范围内：

int change(double x){
    int res=x+128.0+0.5;
    if(res>255)  return 255;
    if(res<0)  return 0;
    return res;
}

Lastly：警示后人

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

AC code

#include<bits/stdc++.h>
using namespace std;

const double pi=acos(-1);
const int len=12;
const int cheat[64][2]={
    {0,0},
    {0,1},{1,0},
    {2,0},{1,1},{0,2},
    {0,3},{1,2},{2,1},{3,0},
    {4,0},{3,1},{2,2},{1,3},{0,4},
    {0,5},{1,4},{2,3},{3,2},{4,1},{5,0},
    {6,0},{5,1},{4,2},{3,3},{2,4},{1,5},{0,6},
    {0,7},{1,6},{2,5},{3,4},{4,3},{5,2},{6,1},{7,0},
    {7,1},{6,2},{5,3},{4,4},{3,5},{2,6},{1,7},
    {2,7},{3,6},{4,5},{5,4},{6,3},{7,2},
    {7,3},{6,4},{5,5},{4,6},{3,7},
    {4,7},{5,6},{6,5},{7,4},
    {7,5},{6,6},{5,7},
    {6,7},{7,6},
    {7,7}
};
int q[len][len],arr[len][len];
int a[len<<4];
double ans[len][len];
int n,t;

double alaph(int x){
    if(x==0)  return sqrt(0.5);
    else  return 1.0;
}

double calc(int i,int j){
    double res=0;
    for(int u=0;u<8;u++){
        for(int v=0;v<8;v++){
            res+=alaph(u)*alaph(v)*arr[u][v]*cos((pi/8)*(i+0.5)*u)*cos((pi/8)*(j+0.5)*v);
        }
    }
    return res/4;
}

int change(double x){
    int res=x+128.0+0.5;
    if(res>255)  return 255;
    if(res<0)  return 0;
    return res;
}

signed main(){
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            cin>>q[i][j];
        }
    }
    cin>>n>>t;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }

    for(int i=0;i<min(64,n);i++){
        arr[cheat[i][0]][cheat[i][1]]=a[i];
    }

    if(t==0){
        for(int i=0;i<8;i++){
            for(int j=0;j<8;j++){
                cout<<arr[i][j]<<" ";
            }
            cout<<endl;
        }
        return 0;
    }

    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            arr[i][j]*=q[i][j];
        }
    }

    if(t==1){
        for(int i=0;i<8;i++){
            for(int j=0;j<8;j++){
                cout<<arr[i][j]<<" ";
            }
            cout<<endl;
        }
        return 0;
    }

    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            ans[i][j]=calc(i,j);
        }
    }

    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            cout<<change(ans[i][j])<<" ";
        }
        cout<<endl;
    }
    return 0;
}

题解来之不易，点个赞再走吧……