题解：Wavelet Compression（小波压缩）

题目分析

本题要求对经过简单小波变换压缩的一维信号进行解压缩。简单小波变换是通过计算每对连续样本的和与差，并递归处理和的部分，直到信号长度为$1$来实现压缩。解压缩则是反向操作，根据和与差逐步还原原始信号。

复杂度分析

1. 时间复杂度：
   • 输入数据的时间复杂度为$O(n)$，其中$n$是样本数量。
   • 解压缩过程中，外层$while$循环最多执行$O(log n)$次（因为每次$m$翻倍），内层两个$for$循环每次的时间复杂度为$O(m)$，综合起来解压缩过程的时间复杂度为$O(n)$。
   • 输出数据的时间复杂度为$O(n)$。
   • 总体时间复杂度为$O(n)$。
2. 空间复杂度：使用了两个大小为$maxN$的数组$a$和$b$，空间复杂度为$O(maxN)$，在本题中$maxN$为$260$，空间占用相对固定。

代码实现分析

#include <iostream>
#include <cstdio>  
using namespace std;

const int maxN = 260;
int a[maxN], b[maxN];

int main() {
    int i, n, m;
    while (scanf("%d", &n) == 1 && n) {  
        for (i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        
        m = 1;
        while (m <= n / 2) {
            for (i = 1; i <= m; ++i) {
                b[2 * i - 1] = (a[i] + a[i + m]) / 2;
                b[2 * i] = (a[i] - a[i + m]) / 2;
            }
            for (i = 1; i <= 2 * m; ++i)
                a[i] = b[i];  
            m *= 2;  
        }
        
        for (i = 1; i <= n; ++i)
            printf("%d ", a[i]);  
        printf("\n");
    }
    return 0;
}

该代码通过合理的循环结构和反向计算逻辑，正确实现了对小波压缩信号的解压缩，满足题目要求。