「小学期出题」Z字型扫描(Easy)

Z字型扫描

光栅扫描和Z字型扫描是两种常见的图像编码方式。

光栅扫描是指从左往右,由上往下,先扫描完一行,再移至下一行起始位置继续扫描。

光栅扫描

在视频压缩标准HEVC中客户端单元采用的是递归划分的方式,Z字形扫描顺序保证了对于不同分割都能按照相同的遍历顺序进行寻址,有利于程序中的递归实现。

Z字型扫描8X8

Z型扫描的扫描顺序如下:

Z字形扫描顺序

Z字型的扫描顺序为:在一个田字格中,依次扫描左上、右上、左下、右下。初始时以1X1为扫描单元,扫描完一个Z字后,以得到的2X2的Z字作为扫描单元,继续扫描,得到一个4X4的Z字······

现在给出T个询问,每次询问输入一个整数N,请输出N在Z型扫描图中的坐标。

Input:

第一行包含一个整数T(1 ≤ T ≤ 1e5),代表有T次询问。
接下来的T行中,每行包含一个整数N(1 ≤ N ≤ 1e9).

Output

共输出T行,每行包含两个整数X和Y,中间用空格分隔,代表N在Z型扫描图中的行数和列数。

Sample Input:

4
1
2
3
4

4
38
39
40
41

Sample Output

1 1
1 2
2 1
2 2

5 4
6 3
6 4
7 1

Hint

None.


Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int N = 20;
int t, f[N], a[N];
void init(){
    f[1] = 1, a[1] = 1;
    for(int i = 2; i <= 15; ++i){
        f[i] = f[i-1] * 4;
        a[i] = a[i-1] * 2;
    }
}

int n, k;
void check(){
    scanf("%d", &n);
    for(int i = 15; i >= 1; --i){
        if(n >= f[i]){
            k = i;
            break;
        }
    }
    int s = n, m, x = 0, y = 0;
    while(k){
        m = s % f[k];
        s = ceil(s * 1.0 / f[k]);
        if(s % 2 == 0)
            y += a[k];
        if(s > 2)
            x += a[k];
        if(m == 0){
            x += a[k];
            y += a[k];
            break;
        }
        s = m;
        --k;
    }
    printf("%d %d\n", x, y);
}

int main(){
    init();
    scanf("%d", &t);
    while(t--){
        check();
    }
} 
添加新评论