题解：P13899 [CSPro 28] JPEG 解码

Cpp__5417__ · 2026-04-23 20:00:00 · 题解

P13899 [CSPro 28] JPEG 解码题解

一道很麻烦的大模拟。

Solution

按照题目中写的，依序模拟即可。

过程如下：

• Z 字形填充矩阵。
  • 模拟填充过程即可（就是细节有亿点点多）。
• 量化矩阵。
  • m[i][j]*=q[i][j]，没啥好讲的。
• 离散余弦逆变换 idct。
  • 注意：idct 是对整个矩阵进行操作的，因此需要了一个数组 r 以存储转换后的结果，之后再赋值回 m 数组。
• 增加 128 并取整，限制范围于 [0,128]。
  • 我用的是 C++ 或 Python 中的 round() 函数，能更方便地进行四舍五入。

Code

:::success[AC of C++]

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define BINF 0x7f
#define int __long_long
#define db double
#define i64 __int128
#define cauto const auto
#define Int signed
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b/gcd(a,b))
#define lowbit(x) ((x)&-(x))
#define alpha(u) ((u)?1.0:sqrt(0.5))// Alpha 函数
using namespace std;
typedef long long __long_long;
typedef pair<int,int> pii;
int n,r;
int q[38][38];
double m[38][38];
double r[38][38];
int a[120];
const auto PI=acos(-1);
// 打表，分别表示右，左下，下，右上
const int X[]={0,1,1,-1};
const int Y[]={1,-1,0,1};
double idct(int i,int j){// 离散余弦逆变换函数
    double r=0;
    for(int u=0;u<8;u++){
        for(int v=0;v<8;v++){
            r+=alpha(u)*alpha(v)*m[u][v]*cos(PI/8*(i+0.5)*u)*cos(PI/8*(j+0.5)*v);
        }
    }
    return r/4.0;
}
void out(){
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++)
            printf("%lld ",(int)m[i][j]);
        printf("\n");
    }
}
void Cpp(){
    for(int i=0;i<8;i++)
        for(int j=0;j<8;j++)
            cin>>q[i][j];
    cin>>n>>r;
    for(int i=0;i<n;i++)cin>>a[i];
    int d=0,i=0,j=0;bool f=true;// d:当前方向,x,y:M矩阵的坐标,f:是否在左上部分
    m[0][0]=a[0];
    for(int k=1;k<min(64ll,n);k++){
        i+=X[d],j+=Y[d],m[i][j]=a[k];
        if(i==7 and j==0)f=false;// 到了左下角
        // 最麻烦的地方
        if(d==0 and f)d=1;// 向右且在左上部分
        else if(d==0 and !f)d=3;// 向右且不在左上部分
        else if(d==1 and j==0 and f)d=2;// 向左下且在左上部分
        else if(d==1 and i==7 and !f)d=0;// 向左下且不在左上部分
        else if(d==2 and f)d=3;// 向下且在左上部分
        else if(d==2 and !f)d=1;// 向下且不在左上部分
        else if(d==3 and i==0 and f)d=0;// 向右上且不在左上部分
        else if(d==3 and j==7 and !f)d=2;// 向右上且不在左上部分
    }// 我的好朋友@Code_to_Win竟然用打表，太可恶了^_^
    if(r==0){out();return;}// T=0时，只需输出填充后的矩阵
    for(int i=0;i<8;i++)// 量化该矩阵
        for(int j=0;j<8;j++)
            m[i][j]*=q[i][j];
    if(r==1){out();return;}// T=1时，只需输出量化后的矩阵
    for(int i=0;i<8;i++)// 离散余弦逆变换
        for(int j=0;j<8;j++)
            r[i][j]=idct(i,j);
    for(int i=0;i<8;i++){// 对该矩阵进行最终的处理
        for(int j=0;j<8;j++){
            m[i][j]=max(min(round(r[i][j]+128),255.0),0.0);// 限制范围
    out();
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int q=1;
//  cin>>q;
    while(q--){Cpp();}
    return 38&17;
}

::: :::success[AC of Python]

from math import pi,sqrt,cos
def alpha(u):# Alpha 函数
    return (1 if u else sqrt(0.5))
q=[[] for i in range(8)]
for i in range(8):
    q[i]=list(map(int,input().split()))
n=int(input())
t=int(input())
a=list(map(int,input().split()))
m=[[0 for j in range(8)] for i in range(8)]
r=[[0 for j in range(8)] for i in range(8)]
# 打表，分别表示右，左下，下，右上
X=[0,1,1,-1]
Y=[1,-1,0,1]
def idct(i,j):# 离散余弦逆变换函数
    r=0.0
    for u in range(8):
        for v in range(8):
            r+=alpha(u)*alpha(v)*m[u][v]*cos(pi/8*(i+0.5)*u)*cos(pi/8*(j+0.5)*v)
    return r/4
def out():
    for i in range(8):
        m[i]=list(map(round,m[i]))
        print(*m[i])
d=0
i=0
j=0
f=True# d:当前方向,x,y:M矩阵的坐标,f:是否在左上部分
m[0][0]=a[0]
for k in range(1,min(64,n)):
    i+=X[d]
    j+=Y[d]
    m[i][j]=a[k]
    if i==7 and j==0:f=False# 到了左下角
    # 最麻烦的地方
    if d==0 and f:d=1# 向右且在左上部分
    elif d==0 and not f:d=3# 向右且不在左上部分
    elif d==1 and j==0 and f:d=2# 向左下且在左上部分
    elif d==1 and i==7 and not f:d=0# 向左下且不在左上部分
    elif d==2 and f:d=3# 向下且在左上部分
    elif d==2 and not f:d=1# 向下且不在左上部分
    elif d==3 and i==0 and f:d=0# 向右上且不在左上部分
    elif d==3 and j==7 and not f:d=2# 向右上且不在左上部分
# 我的好朋友@Code_to_Win竟然用打表，太可恶了^_^
if t==0:out();exit(0)# T=0时，只需输出填充后的矩阵
for i in range(8):# 量化该矩阵
    for j in range(8):
        m[i][j]*=q[i][j]
if t==1:out();exit(0)# T=1时，只需输出量化后的矩阵
for i in range(8):# 离散余弦逆变换
    for j in range(8):
        r[i][j]=idct(i,j)
for i in range(8):# 对该矩阵进行最终的处理
    for j in range(8):
        m[i][j]=round(r[i][j]+128)
        m[i][j]=max(min(m[i][j],255.0),0.0)# 限制范围
out()

::: 我懒了，这里没有 Java。

最后，这是本蒟蒻的第 2 篇题解，所以——点个赞呗。