3444:Wavelet Compression

PKU

keyword

C++

概要

長さn(<=256, 2のべき)の数列が与えられる。f({a_n})をb_i = a_{2*i-1} + a_{2*i}, c_i = a_{2*i} - a_{2*i-1}としてf({b_i}):{c_i}として再帰的に変換する。変換された後の列が与えられるので元の数列を復元する問題。
前から順に復元すれば良い。

int main(){
    int n;

    while( n = readint(), n ){
        int i, j, logs=1, p=0;
        REP(i,n) sigs[i] = readint();
        while(logs <= n){
            p = 0;
            REP(i,logs){
                ans[2*i] = (sigs[i]+sigs[(logs>>1)+i])>>1;
                ans[2*i+1] = (sigs[i]-sigs[(logs>>1)+i])>>1;
            }
            REP(i,logs){
                sigs[i] = ans[i];
            }
            logs <<= 1;
        }
        REP(i,n){
            printf("%d%c",sigs[i],(i==n-1)?'\n':' ');
        }
    }

    return 0;
}