luogu-P1319 压缩技术

GESP C++三级练习，字符串/位运算，难度★★☆☆☆。

luogu-P1319 压缩技术

题目要求

题目描述

设某汉字由 $N \times N$ 的 $\texttt 0$ 和 $\texttt 1$ 的点阵图案组成。

我们依照以下规则生成压缩码。连续一组数值：从汉字点阵图案的第一行第一个符号开始计算，按书写顺序从左到右，由上至下。第一个数表示连续有几个 $\texttt 0$，第二个数表示接下来连续有几个 $\texttt 1$，第三个数再接下来连续有几个 $\texttt 0$，第四个数接着连续几个 $\texttt 1$，以此类推……

例如: 以下汉字点阵图案：

0001000
0001000
0001111
0001000
0001000
0001000
1111111

对应的压缩码是： $\texttt {7 3 1 6 1 6 4 3 1 6 1 6 1 3 7}$ （第一个数是 $N$ ,其余各位表示交替表示0和1 的个数，压缩码保证 $N \times N=$ 交替的各位数之和）

输入格式

数据输入一行，由空格隔开的若干个整数，表示压缩码。

其中，压缩码的第一个数字就是 $N$，表示这个点阵应当是 $N\times N$ 的大小。

接下来的若干个数字，含义如题目描述所述。

输出格式

输出一个 $N\times N$ 的 01 矩阵，表示最后的汉字点阵图（点阵符号之间不留空格）。

输入输出样例 #1

输入 #1

7 3 1 6 1 6 4 3 1 6 1 6 1 3 7

输出 #1

0001000
0001000
0001111
0001000
0001000
0001000
1111111

说明/提示

样例解释

数据范围

数据保证，$3\leq N\leq 200$。

题目分析

解题思路

本题的解题思路如下：

1. 问题本质：

   • 输入一串数字，第一个数字 $N$ 表示要生成的点阵大小
   • 后续数字交替表示连续的 0 和 1 的个数
   • 需要按照这些数字生成一个 $N \times N$ 的二维点阵图案

2. 解题关键：

   • 核心思路 - 线性输出：
     1. 读取输入数据：
        • 首先读取矩阵大小 $N$
        • 后续依次读取表示连续 0 和 1 个数的数字
     2. 按规则输出：
        • 维护当前应输出的数字（0或1）
        • 每读取一个数字，就输出相应个数的当前数字
        • 每输出 $N$ 个字符就换行
        • 每次输出完后切换当前数字（0变1，1变0）
     3. 使用位运算优化数字切换：
        • 可以用异或运算 ^= 1 来实现 0/1 切换

3. 复杂度分析：

   • 时间复杂度：$O(N^2)$，需要输出 $N \times N$ 个字符
   • 空间复杂度：$O(1)$，只需要少量变量即可完成

{% include custom/custom-post-content-inner.html %}

示例代码

#include <iostream>

int main() {
    // 读取矩阵大小 N
    int n;
    std::cin >> n;
    
    // 当前需要输出的数字(0或1)
    int cur_count;
    // 当前正在处理的数字(初始为0)
    int cur_num = 0;
    // 当前行已输出的字符数
    int line_count = 0;
    
    // 持续读取压缩码中的数字
    while(std::cin >> cur_count) {
        // 根据当前数字(cur_count)重复输出cur_num指定次数
        for (int i = 0; i < cur_count; i++) {
            // 输出当前数字
            std::cout << cur_num;
            line_count++;
            
            // 如果已经输出了n个字符，换行并重置行计数
            if (line_count == n) {
                std::cout << "\n";
                line_count = 0;
            }
        }
        // 切换当前数字(0变1，1变0)
        cur_num ^= 1;
    }
    return 0;
}            

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号