解題區/解題區 - Zerojudge

b454. 困難版 輸出 RGB 數值

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. 產生器
    2. 4.2. base64
    3. 4.3. base64 短碼

Problem

給一張 $45 \times 45$ 的經典 Lena 彩色影像，共有 $2025$ 個像素，程式碼長度上限 10K，避開打表的長度限制，輸出一模一樣的圖形。

Sample Input

1
NO INPUT

Sample Output

1
2
45 45
225 134 119 223 130 108 220 126 105 (後面省略)

Solution

由 Zerojudge b454. 請輸出這張圖片的 RGB 數值 改編，強迫使用 base64 的方案，使用一般的 16 進制輸出編碼會超過限制。16 進制下，共計需要 $6075$ 個 0 - 255 的整數，共計需要用 $12150$ 個可視字元。

根據前一題的實驗，雖然霍夫曼編碼會比較短，但是還要附加解壓縮的代碼一起上傳，除非寫短碼否則很容易虧本。而 lz77 是不錯的壓縮方案，但用在影像中很容易虧本，因為重複的片段並不高。因此最後選擇直接使用 base64，則可視字元數量可以降到 10K 以下，接下來就比誰的短碼能力好。

base64 只用到 0-9a-zA-Z+/= 這 64 個字元，為了在一般 C/C++ 的字串宣告語法，跳逸字元如 \\、\t、\n … 等必須用兩個字元表示，通常都是在 ASCII [0, 31] 為跳逸字元。蔡神 asas 直接用連續片段，因此會有一些跳逸字元，儘管跳逸字元占用兩個以上的字符，會多好幾個字元，但就不必編寫解碼程序，不用去寫繁複的映射，代碼居然比較短。

產生器

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <vector>
#include <set>
using namespace std;
void lz77_encode(unsigned char *in, int n, unsigned char *out, int &m)  {
    m = 0;
    if (n <= 16) {
        for (int i = 0; i < n; i++)
            out[m++] = in[i];
        return ;
    }
    memcpy(out, in, 16);
    m += 16;
    while (n > 16) {
        int mx = 0, offset, i, j;
        for (i = 0; i < 16; i++) {
            for (j = 0; i+j < 16 && j+16 < n && in[i+j] == in[j+16]; j++);
            if (j > mx)
                mx = j, offset = i;
        }
        if (mx <= 1) {
            out[m++] = 0;
            out[m++] = in[16];
            in++, n--;
        } else {
            out[m++] = (offset<<4)|(mx-1);
            in += mx, n -= mx;
        }
    }
}
void lz77_decode(unsigned char *in, int n, unsigned char *out, int &m)  {
    m = 0;
    if (n <= 16) {
        for (int i = 0; i < n; i++)
            out[m++] = in[i];
        return ;
    }
    memcpy(out, in, 16);
    in += 16, n -= 16, m += 16;
    int offset, mx;
    while (n > 0) {
        if (*in) {
            offset = (*in)>>4, mx = ((*in)&0xf)+1;
            memcpy(out + m, out + m - 16 + offset, mx);
            m += mx;
            in++, n -= 1;
        } else {
            out[m++] = in[1];
            in += 2, n -= 2;
        }
    }
}
void base64_encode(unsigned char *in, int n, unsigned char *out, int &m)  {
static char encode_table[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
                    'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P',
                    'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
                    'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f',
                    'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
                    'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
                    'w', 'x', 'y', 'z', '0', '1', '2', '3',
                    '4', '5', '6', '7', '8', '9', '+', '/'};
static int mod_table[] = {0, 2, 1};
    m = 4 * ((n + 2) / 3);
    for (int i = 0, j = 0; i < n; ) {
        unsigned int a, b, c, d;
        a = i < n ? in[i++] : 0;
        b = i < n ? in[i++] : 0;
        c = i < n ? in[i++] : 0;
        d = (a<<16)|(b<<8)|c;
        out[j++] = encode_table[(d>>18)&0x3f];
        out[j++] = encode_table[(d>>12)&0x3f];
        out[j++] = encode_table[(d>>6)&0x3f];
        out[j++] = encode_table[d&0x3f];
    }
    for (int i = 0; i < mod_table[n%3]; i++)
        out[m - 1 - i] = '=';
}
void base64_decode(unsigned char *in, int n, unsigned char *out, int &m)  {
static int decode_table[256];
    for (int i = 'A'; i <= 'Z'; i++)	decode_table[i] = i - 'A';
    for (int i = 'a'; i <= 'z'; i++)	decode_table[i] = i - 'a' + 26;
    for (int i = '0'; i <= '9'; i++)	decode_table[i] = i - '0' + 52;
    decode_table['+'] = 62, decode_table['/'] = 63;
    m = n/4*3;
    if (in[n-1] == '=')	m--;
    if (in[n-2] == '=')	m--;
    for (int i = 0, j = 0; i < n; ) {
        unsigned int a, val = 0;
        for (int k = 3; k >= 0; i++, k--) {
            a = in[i] == '=' ? 0 : decode_table[in[i]];
            val |= a<<(k*6);
        }
        if (j < m)	out[j++] = (val>>16)&0xff;
        if (j < m)	out[j++] = (val>>8)&0xff;
        if (j < m)	out[j++] = (val>>0)&0xff;
    }
}
void huffman_encode(unsigned char *in, int n, unsigned char *out, int &m)  {
    m = 0;
    struct Table {
        int f, bit, bn;
    } tables[512];
    struct Node {
        int f, tid;
        Node *l, *r;
        Node(int a = 0, int b = 0, Node *ls = NULL, Node *rs = NULL):
            f(a), tid(b), l(ls), r(rs) {}
        bool operator<(const Node &x)  const {
            return f < x.f;
        }
    } nodes[512];
    struct Stack {
        Node *node;
        int bit, bn;
        Stack(Node *a = NULL, int b = 0, int c = 0):
            node(a), bit(b), bn(c) {}
    } stacks[1024];
    int size = 0, leaf;
    multiset< pair<int, Node*> > S;
    memset(tables, 0, sizeof(tables));
    for (int i = 0; i < n; i++)
        tables[in[i]].f++;
    for (int i = 0; i < 256; i++) {
        if (tables[i].f) {
            nodes[size] = Node(tables[i].f, i);
            S.insert({nodes[size].f, &nodes[size]});
            size++;
        }
    }
    leaf = size;
    while (S.size() >= 2) {
        pair<int, Node*> u, v;
        u = *S.begin(), S.erase(S.begin());
        v = *S.begin(), S.erase(S.begin());
        int f = u.second->f + v.second->f; 
        nodes[size] = Node(f, -1, u.second, v.second);
        S.insert({nodes[size].f, &nodes[size]});
        size++;
        
    }
    int stkIdx = 0;
    stacks[stkIdx++] = Stack(&nodes[size-1], 0, 0);
    while (stkIdx) {
        Stack u = stacks[--stkIdx], v;
        if (u.bn >= 31) {
            fprintf(stderr, "huffman error: bit length exceeded\n");
            exit(0);
        }
        if (u.node->l == NULL) {
            tables[u.node->tid].bit = u.bit;
            tables[u.node->tid].bn = u.bn;
        } else {
            v = Stack(u.node->l, u.bit | (1<<u.bn), u.bn+1);
            u.node = u.node->r, u.bn++;
            stacks[stkIdx++] = u;
            stacks[stkIdx++] = v;
        }
    }
    int bits_cnt = 0;
    for (int i = 0; i < 256; i++)
        bits_cnt += tables[i].f * tables[i].bn;
    fprintf(stderr, "huffman: %d bit length\n", bits_cnt);
    
    memcpy(out+m, &bits_cnt, 4), m += 4;
    memcpy(out+m, &leaf, 1), m += 1;
    for (int i = 0; i < leaf; i++) {
        Table t = tables[nodes[i].tid];
        memcpy(out+m, &nodes[i].tid, 1), m += 1;
        memcpy(out+m, &t.bn, 1), m += 1;
        memcpy(out+m, &t.bit, (t.bn + 7)/8), m += (t.bn + 7)/8;
    }
    
    int cnt = 0, mask = 0;
    for (int i = 0; i < n; i++) {
        int bit = tables[in[i]].bit;
        int bn = tables[in[i]].bn;
        while (bn) {	// LBS
            int j = min(bn, 8 - cnt);
            mask |= (bit&((1<<j)-1))<<cnt;
            cnt += j, bn -= j, bit >>= j;
            if (cnt == 8) {
                memcpy(out+m, &mask, 1), m += 1;
                cnt = 0, mask = 0;
            }
        }
    }
    if (cnt)
        memcpy(out+m, &mask, 1), m += 1;
    fprintf(stderr, "huffman encode length %d\n", m);
}
void huffman_decode(unsigned char *in, int n, unsigned char *out, int &m)  {
    m = 0;
    map<int, int> R[64];
    int bits_cnt = 0, leaf = 0;
    memcpy(&bits_cnt, in, 4), in += 4, n -= 4;
    memcpy(&leaf, in, 1), in += 1, n -= 1;
    fprintf(stderr, "huffman: %d bit length\n", bits_cnt);
    fprintf(stderr, "huffman: %d leaves\n", leaf);
    for (int i = 0; i < leaf; i++) {
        int tid = 0, bn = 0, bit = 0;
        memcpy(&tid, in, 1), in += 1, n -= 1;
        memcpy(&bn, in, 1), in += 1, n -= 1;
        memcpy(&bit, in, (bn+7)/8), in += (bn+7)/8, n -= (bn+7)/8;
        R[bn][bit] = tid;
    }
    int mask = 0, cnt = 0;
    for (int i = 0; i < bits_cnt; i++) {
        mask |= ((in[(i>>3)]>>(i&7))&1)<<cnt;
        cnt++;
        if (R[cnt].count(mask)) {
            out[m++] = R[cnt][mask];
            cnt = 0, mask = 0;
        }
    }
}
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        unsigned char in[32767], in2[32767], *pin;
        pin = in;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int r, g, b;
                scanf("%d %d %d", &r, &g, &b);
                *pin = r, pin++;
                *pin = g, pin++;
                *pin = b, pin++;
            }
        }
        int lz77n, b64n, elz77n, tn, hufn, ehufn;
        unsigned char buf[4][32767] = {}, test[32767] = {};
        // Case 1
//		base64_encode(in, n*m*3, buf[1], b64n);
        // Case 2
//		huffman_encode(in, n*m, buf[0], hufn);
//		base64_encode(buf[0], hufn, buf[1], b64n);
//		base64_decode(buf[1], b64n, buf[2], ehufn);
//		huffman_decode(buf[2], ehufn, test, tn);
        // Case 3
//		lz77_encode(in, n*m, buf[0], lz77n);
//		base64_encode(buf[0], lz77n, buf[1], b64n);
//		base64_decode(buf[1], b64n, buf[2], elz77n);
//		lz77_decode(buf[2], elz77n, test, tn);
        // Case 4
//		huffman_encode(in, n*m, buf[0], hufn);
//		lz77_encode(buf[0], hufn, buf[2], lz77n);
//		base64_encode(buf[2], lz77n, buf[1], b64n);
        // Case 5
//		lz77_encode(in, n*m, buf[0], lz77n);
//		huffman_encode(buf[0], hufn, buf[2], hufn);
//		base64_encode(buf[2], lz77n, buf[1], b64n);
        // Case 6
        for (int i = 0; i < n*m*3; i += 3) {
            in2[i] = in[i] - (i >= 3 ? in[i-3] : 0);
            in2[i+1] = in[i+1] - (i >= 4 ? in[i-4] : 0);
            in2[i+2] = in[i+2] - (i >= 5 ? in[i-5] : 0);
        }
        huffman_encode(in2, n*m*3, buf[0], hufn);
        base64_encode(buf[0], hufn, buf[1], b64n);
        for (int i = 0; i < b64n; i++)
            printf("%c", buf[1][i]);
        puts("");
    }
    return 0;
}

base64

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
#include <bits/stdc++.h>
using namespace std;
unsigned char data[] = "4YZ334Js3H5p5o1z8JZ0t01cpEBWsklUsE ... ignore";
void base64_decode(unsigned char *in, int n, unsigned char *out, int &m)  {
static int R[256];
    for (int i = 'A'; i <= 'Z'; i++)	R[i] = i - 'A';
    for (int i = 'a'; i <= 'z'; i++)	R[i] = i - 'a' + 26;
    for (int i = '0'; i <= '9'; i++)	R[i] = i - '0' + 52;
    R['+'] = 62, R['/'] = 63;
    m = n/4*3;
    if (in[n-1] == '=')	m--;
    if (in[n-2] == '=')	m--;
    for (int i = 0, j = 0; i < n; ) {
        unsigned int a, val = 0;
        for (int k = 3; k >= 0; i++, k--) {
            a = in[i] == '=' ? 0 : R[in[i]];
            val |= a<<(k*6);
        }
        if (j < m)	out[j++] = (val>>16)&0xff;
        if (j < m)	out[j++] = (val>>8)&0xff;
        if (j < m)	out[j++] = (val>>0)&0xff;
    }
}
int main() {
    unsigned char d[32767] = {};
    int n;
    base64_decode(data, sizeof(data), d, n);
    printf("%d %d\n", 45, 45);
    for (int i = 0; i < 45; i++) {
        for (int j = 0; j < 45; j++) {
            int v = (i*45+j)*3;
            printf("%d %d %d%c", d[v], d[v+1], d[v+2], " \n"[j == 44]);
        }
    }
    return 0;
}

base64 短碼

利用巨集展開重複的指令

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
#include <bits/stdc++.h>
typedef unsigned char UINT8;
UINT8 data[] = "4YZ334Js3H5p5o1z8JZ0t01cpEBWsklUsE ... ignore";
UINT8 d[32767] = {};
void base64_decode(UINT8 *in, int n, UINT8 *out, int &m)  {
#define MK(st, ed, b) for (int i = st; i <= ed; i++) R[i] = i-st+b;
#define MG(k) b |= (in[i] == '=' ? 0 : R[in[i]])<<(k*6), i++;
#define MP(k) if (j < m)	out[j++] = (b>>(k*8))&0xff;
    int R[256];
    MK('A', 'Z', 0); MK('a', 'z', 26); MK('0', '9', 52);
    R['+'] = 62, R['/'] = 63;
    m = n/4*3;
    if (in[n-1] == '=')	m--;
    if (in[n-2] == '=')	m--;
    for (int i = 0, j = 0; i < n; ) {
        int b = 0;
        MG(3); MG(2); MG(1); MG(0);
        MP(2); MP(1); MP(0);
    }
}
int main() {
    int n, v;
    base64_decode(data, sizeof(data), d, n);
    printf("%d %d\n", 45, 45);
    for (int i = 0; i < 45; i++) {
        for (int j = 0; j < 45; j++) {
            v = (i*45+j)*3;
            printf("%d %d %d%c", d[v], d[v+1], d[v+2], " \n"[j == 44]);
        }
    }
    return 0;
}