1011.8-bit Zoom

不那么签到的签到题、模拟题

题意

给定一个 $n\times n$ 大小的字符矩阵表示一张图片，每种字符代表一种颜色；并给定 $Z$ 代表缩放倍率
满足以下条件即可缩放：

  1. 缩放后的边长 $\dfrac{nZ}{100}$ 是一个整数
  2. 每个像素可以被唯一确定（如果缩放后的像素被从超过两种颜色覆盖，则无法确定颜色）

如果可以进行缩放，则输出缩放后的图片，否则输出“error”

解题思路

模拟缩放过程

如果不满足上述条件 $1$ 则一定无法缩放

条件 $2$ 需要根据图片实际情况判断是否满足
记这张图片被放大了 $x=\dfrac{a}{b}$ 倍，假设此处 $a,b$ 互质，则等同于先将图片缩小 $b$ 倍，再放大 $a$ 倍
如果缩小的过程不会有像素无法被确定，则缩小后一定是可以放大整数倍的
因此只需检查每个边长为 $b$ 的像素区块（它们将被缩小至 $1$ 像素），如果有任意一块混色，则无法压缩
压缩成功后，边长放大至 $a$ 倍即可

根据题意，记缩放后的图片尺寸为 $sz$
易得此处 $a=sz/gcd(n,sz)$ ， $b=n/gcd(n,sz)$

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
void solve()
{
    ll n,Z,t;
    cin >> n >> Z;
    string s[55];
    for(ll i=1;i<=n;i++) cin >> s[i];
    if((n*Z)%100) {cout << "error" << endl;return;}
    ll sz=(n*Z)/100;//缩放后的图片边长
    char re[55][55]={0};
    t=gcd(sz,n);
    if(n==t){
        for(ll i=1;i<=n;i++){
            for(ll a=1;a<=sz/t;a++){
                for(ll j=0;j<=n-1;j++){
                    for(ll b=1;b<=sz/t;b++){
                        cout << s[i][j];
                    }
                }
                cout << endl;
            }
        }return;
    }
    for(ll i=1;i<=t;i++){
        for(ll j=0;j<t;j++){
            char ch=s[(i-1)*(n/t)+1][j*(n/t)];
            for(ll a=0;a<=n/t-1;a++){
                for(ll b=0;b<=n/t-1;b++){
                    if(s[(i-1)*(n/t)+1+a][j*(n/t)+b]!=ch){
                        cout << "error" << endl;
                        return ;
                    }
                }
            }
            re[i-1][j]=ch;
        }
    }
    for(ll i=0;i<=t-1;i++){
        for(ll a=1;a<=sz/t;a++){
            for(ll j=0;j<=t-1;j++){
                for(ll b=1;b<=sz/t;b++) cout << re[i][j];
            }
            cout << endl;
        }
    }
}