题解：P13899 [CSPro 28] JPEG 解码

· · 题解

题目意思

要写一个很高级的JPEG解码器。
有三个步骤：

  1. 先斜着填充矩阵。
  2. 量化（其实就是把所有的数都乘上一个相对应的数值）。
  3. 进行离散余弦逆变换。
  4. 将矩阵中的每个元素都加上 128，并取最接近的整数（四舍五入）。如果得到的整数大于 255，则取 255；如果得到的整数小于 0，则取 0。

先输入量化矩阵（就是填充完了要乘的）那个矩阵。
然后输入操作类型，0 的话就只要填充矩阵，1 还要量化，2 就要做完整个流程。

这个离散余弦逆变换怎么做呢？我们看题：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}

这个就是个大模拟，看起来挺吓唬人的，但是其实就是这样的代码：

// Mi 数组是 M 矩阵, Mp 是 M' 矩阵
    const ld PI = acosl(-1.0L);
    alpha[0] = sqrtl(0.5L);
    for(int u = 1;u < 8;u++){
        alpha[u] = 1.0L;
    }
    for(int i = 0;i < 8;i++){
        for(int j = 0;j < 8;j++){
            for(int u = 0;u < 8;u++){
                for(int v = 0;v < 8;v++){
                    Mp[i][j] += 0.25 * alpha[u] * alpha[v] * Mi[u][v] * cosl(PI / 8 * (i + 0.5) * u) * cosl(PI / 8 * (j + 0.5) * v);
                }
            }
        }
    }

然后只要别忘了加上 128 就可以了。 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
int Q[8][8], Mi[8][8];
ld M[8][8], Mp[8][8], alpha[8];
int res[8][8], posx[64], posy[64], shuru[64];
int main(){
    for(int i = 0;i < 8;i++){
        for(int j = 0;j < 8;j++){
            cin >> Q[i][j];
        }
    }
    int n;
    cin >> n;
    int T;
    cin >> T;
    for(int i = 0;i < n;i++){
        cin >> shuru[i];
    }
    int cnt = 0;
    for(int s = 0;s <= 14;s++){
        if(s % 2 == 0){
            for(int i = s;i >= 0;i--){
                int j = s - i;
                if(0 <= i && i < 8 && 0 <= j && j < 8){
                    posx[cnt] = i;
                    posy[cnt] = j;
                    cnt++;
                }
            }
        }else{
            for(int i = 0;i <= s;i++){
                int j = s - i;
                if(0 <= i && i < 8 && 0 <= j && j < 8){
                    posx[cnt] = i;
                    posy[cnt] = j;
                    cnt++;
                }
            }
        }
    }
    for(int k = 0;k < n;k++){
        int x = posx[k];
        int y = posy[k];
        Mi[x][y] = shuru[k];
    }
    if(T == 0){
        for(int i = 0;i < 8;i++){
            for(int j = 0;j < 8;j++){
                if(j) cout << ' ';
                cout << Mi[i][j];
            }
            cout << endl;
        }
        return 0;
    }
    for(int i = 0;i < 8;i++){
        for(int j = 0;j < 8;j++){
            Mi[i][j] *= Q[i][j];
        }
    }
    if(T == 1){
        for(int i = 0;i < 8;i++){
            for(int j = 0;j < 8;j++){
                if(j) cout << ' ';
                cout << Mi[i][j];
            }
            cout << endl;
        }
        return 0;
    }
    for(int i = 0;i < 8;i++){
        for(int j = 0;j < 8;j++){
            M[i][j] = Mi[i][j];
        }
    }
    const ld PI = acosl(-1.0L);
    alpha[0] = sqrtl(0.5L);
    for(int u = 1;u < 8;u++){
        alpha[u] = 1.0L;
    }
    for(int i = 0;i < 8;i++){
        for(int j = 0;j < 8;j++){
            for(int u = 0;u < 8;u++){
                for(int v = 0;v < 8;v++){
                    Mp[i][j] += 0.25 * alpha[u] * alpha[v] * Mi[u][v] * cosl(PI / 8 * (i + 0.5) * u) * cosl(PI / 8 * (j + 0.5) * v);
                }
            }
        }
    }
    for(int i = 0;i < 8;i++){
        for(int j = 0;j < 8;j++){
            ld x = Mp[i][j] + 128.0L;
            ll val = llroundl(x);
            if(val < 0) val = 0;
            if(val > 255) val = 255;
            res[i][j] = (int)val;
        }
    }
    for(int i = 0;i < 8;i++){
        for(int j = 0;j < 8;j++){
            if(j) cout << ' ';
            cout << res[i][j];
        }
        cout << endl;
    }
    return 0;
}