压缩技术

题意

输入压缩码。第一个数是矩阵大小 n，后面的数依次表示连续 0、连续 1、连续 0……的长度。要求还原 n * n 的 01 矩阵。

思路

压缩码本质是游程编码。先从字符 "0" 开始，遇到一个长度 length，就把当前字符重复 length 次加入一维列表 cells，然后把当前字符在 "0" 和 "1" 之间切换。

展开完成后，cells 长度正好是 n*n。第 row 行对应：

text

1cells[row*n : row*n+n]

把这一段拼接成字符串输出即可。

这题是字符串展开和切片练习，不创建 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：用 sys.stdin.read().split() 读取所有整数，输入换行方式不影响解析。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：切片 cells[left:right] 适合取出一行。
cells.extend(value for _ in range(length)) 批量追加重复字符。
"".join(...) 把字符列表拼成一行。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18import sys


data = list(map(int, sys.stdin.read().split()))
n = data[0]
runs = data[1:]

cells = []
value = "0"

for length in runs:
    cells.extend(value for _ in range(length))
    value = "1" if value == "0" else "0"

for row in range(n):
    left = row * n
    right = left + n
    print("".join(cells[left:right]))

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

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

char grid[205][205]; // 还原后的 01 矩阵
int n;

int main() {
    cin >> n;
    int len;          // 游程长度
    char cur = '0';   // 当前要填充的字符，从 0 开始
    int x = 1, y = 1; // 当前填充位置

    while (cin >> len) {
        // 将 cur 重复 len 次填入矩阵
        for (int k = 1; k <= len; k++) {
            grid[x][y] = cur;
            y++;
            if (y > n) { // 换行
                y = 1;
                x++;
            }
        }
        // 切换填充字符（0 <-> 1）
        cur = (cur == '0') ? '1' : '0';
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << grid[i][j];
        cout << "\n";
    }
    return 0;
}

Pythonic 写法

用 cycle("01") 与 repeat / chain 展开游程，再按行切片输出：

python

1
2
3
4
5
6
7
8import sys
from itertools import chain, cycle, islice, repeat

data = list(map(int, sys.stdin.read().split()))
n, runs = data[0], data[1:]
cells = list(chain.from_iterable(repeat(bit, length) for bit, length in zip(cycle("01"), runs)))
for row in range(n):
    print("".join(cells[row * n : (row + 1) * n]))

复杂度

展开和输出都处理 n^2 个字符，时间复杂度是 $O(n^2)$ ，空间复杂度是 $O(n^2)$ 。

总结

解压题先按长度展开成一维序列，再按行切开。这样可以避免边展开边处理换行的混乱。

目录

题意

思路

Python 知识

代码

Pythonic 写法

复杂度

总结