Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

1:最近餐馆

描述

每到饭点，就又到了一日几度的小L纠结去哪吃饭的时候了。因为有太多太多好吃的地方可以去吃，而小L又比较懒不想走太远，所以小L会先找到距离他最近的M家餐馆然后再做筛选。

小L现在所在的位置和每家餐馆的位置用同一笛卡尔坐标系中的点表示，而点与点之间的距离为欧几里得距离，对于点p = (p1, p2,..., pn)和点q = (q1,q2,..., qn)，两者的距离定义如下

现给出在K维空间中小L所处的位置的坐标以及n个餐馆的位置，请帮助小L完成他的需求。

输入

第1行包含两个整数n和K，1≤n≤5000，1≤K≤5。
接下来n行，每行包含K个数，表示每个餐馆的坐标。
接下来1行，包含一个数t，1≤t≤10000，表示小L询问的数目。
每次询问包括两行。第1行包含K个数，表示小L所在的坐标。第2行包含一个数M，1≤M≤10。
所有坐标值不会超过10000。
输入数据包含多组数据，请逐个处理直到文件结束。

输出

对于每一个询问，输出m+1行：
第1行输出：”the closest M points are:”，其中M在输入中给出。
接下来M行输出距离最近的M家餐馆的坐标，按照由近及远的顺序输出。
输出数据保证答案唯一。保证从小L的位置到最近的M+1家餐馆位置各不相同，这说明如下输入数据：
2 2
1 1
3 3
1
2 2
1
不会存在。

样例输入

3 2
1 1
1 3
3 4
2
2 3
2
2 3
1

样例输出

the closest 2 points are:
1 3
3 4
the closest 1 points are:
1 3

---

對 x 取中點切割、分成兩個空間。
對 y 取中點切割、再分兩個空間。
.
.
.
對 x 取中點切割、分成兩個空間。
對 y 取中點切割、再分兩個空間。
...
搜尋最鄰近的 M 對時，努力地估價吧！
由於每次劃分的維度不同，要保留前幾次在某維度的估價情況。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct Node {
    Node *l, *r;
    int idx;
};
Node buf[5005];
int bufsize;
int pt[5005][5];
int L[5];
int n, t, K, M;
int i, j, k;
int A[5005];
int sortIdx;
bool cmp(int a, int b) {
    return pt[a][sortIdx] < pt[b][sortIdx];
}
Node* build(int k, int l, int r) {
    if(l > r)
        return NULL;
    sortIdx = k;
    sort(A+l, A+r+1, cmp);
    int m = (l + r)/2;
    Node *ret = &buf[bufsize++];
    ret->idx = A[m]; // point index
    if(l != r) {
        ret->l = build((k+1)%K, l, m-1);
        ret->r = build((k+1)%K, m+1, r);
    } else {
        ret->l = ret->r = NULL;
    }
    return ret;
}
int max_dist = 0xfffffff;
int dist(int idx) {
    int ret = 0;
    for(int i = 0; i < K; i++)
        ret += (pt[idx][i]-L[i])*(pt[idx][i]-L[i]);
    return ret;
}
int toth(int h[]) {
    int ret = 0;
    for(int i = 0; i < K; i++)
        ret += h[i];
    return ret;
}
struct pQcmp {
    bool operator() (int a, int b) {
        return dist(a) < dist(b);
    }
};
priority_queue<int, vector<int>, pQcmp> pQ;
void DC(Node *nd, int k, int h[]) {
    if(nd == NULL || toth(h) >= max_dist)
        return;
    int d = dist(nd->idx);
    if(d < max_dist) {
        pQ.push(nd->idx);
        if(pQ.size() == M+1) {
            max_dist = dist(pQ.top());
            pQ.pop();
        }
    }
    int hk = h[k];
    if(L[k] < pt[nd->idx][k]) {
        if(nd->l != NULL)
            DC(nd->l, (k+1)%K, h);    
        if(nd->r != NULL) {
            h[k] = (pt[nd->idx][k] - L[k])*(pt[nd->idx][k] - L[k]);
            DC(nd->r, (k+1)%K, h);
            h[k] = hk;
        }
    } else {
        if(nd->l != NULL) {
            h[k] = (pt[nd->idx][k] - L[k])*(pt[nd->idx][k] - L[k]);
            DC(nd->l, (k+1)%K, h);
            h[k] = hk;
        }
        if(nd->r != NULL)
            DC(nd->r, (k+1)%K, h);
    }
}
void brute_force(int c[]) {
    int d[5005];
    for(i = 0; i < n; i++) {
        d[i] = dist(i);
    }
    sort(d, d+n);
    for(i = 0; i < M; i++) {
        if(d[i] != dist(c[M-i-1]))
            printf("[b] %d [m] %d\n", d[i], dist(c[M-i-1]));
    }
}
int main() {
    while(scanf("%d %d", &n, &K) == 2) {
        for(i = 0; i < n; i++) {
            for(j = 0; j < K; j++) {
                scanf("%d", &pt[i][j]);
                if(pt[i][j] < 0)
                    puts("wa");
            }
            A[i] = i;
        }
        bufsize = 0;
        Node *root = build(0, 0, n-1);
        scanf("%d", &t);
        while(t--) {
            for(i = 0; i < K; i++)
                scanf("%d", &L[i]);
            scanf("%d", &M);
            max_dist = 2147483647;
            int h[5] = {};
            DC(root, 0, h);
            printf("the closest %d points are:\n", M);
            int buf[30], bidx = 0;
            while(!pQ.empty()) {
                int idx = pQ.top();
                buf[bidx++] = idx;
                pQ.pop();
            }
            //brute_force(buf);
            for(i = bidx-1; i >= 0; i--) {
                for(j = 0; j < K; j++) {
                    if(j)    putchar(' ');
                    printf("%d", pt[buf[i]][j]);
                }
                puts("");
            }
        }
    }
    return 0;
}

---

2:四分树

描述

一幅如图2(a)所示的二进制图片常常会用一个二进制矩阵来表示。所谓二进制矩阵是指矩阵中的每一个数不是0就是1。图2(b)展示图2(a)用二进制矩阵表示的情况。

图2：(a)二进制图片(b)图片的矩阵表示(c)四分树划分(d)四分树表示

 

为了保存图2(b)这样的矩阵，经常使用四分树来完成。对于一个N * N的矩阵，N <= 512且N = 2^i（i为正整数），如果这个矩阵中的数不全一样，那么我们会把这个矩阵分成4个N/2 * N/2的矩阵，如图2(c)所示。之后，我们再对这4个N/2 * N/2的矩阵划分，同样地，如果里面的数不全一样则划分成N/4 * N/4的矩阵。图2(c)里面右边的两个N/2 * N/2的矩阵就被这样再度划分了。如此可以持续进行划分，直到里面的数全一样。图2(c)展示了完全划分完毕的样子。

我们一般都将二进制图片存成图2(d)这样的四分树的形式，这棵树是通过图2(c)里面的划分得到的。图2(d)里面的每一个结点都代表图2(c)里面的矩阵，而树的根结点代表整个大的矩阵。如果树中一个结点的值为1，则代表这个结点对应的矩阵需要划分成4个小矩阵。否则，这个结点将包含两个数。第一个数为0，表示不用再划分，第二个数为0或者1，表示整个矩阵都是这个值。整棵树可以用它的宽度优先遍历得到的结果来表示，如图2(d)中的树可以表示成(1)(0,0)(1)(0,1)(1)(0,0)(0,1)(1)(0,0)(0,0)(0,0)(0,1)(0,1)(0,0)(0,1)(0,0)(0,1)。删掉括号和逗号，我们可以得到一个更简短的纯二进制编码100101100011000000010100010001来编码这张图片，它的16进制形式为258C0511。

现在请你编写一个程序，求出给定图片的16进制形式的编码。

 

输入

第1行包含一个数k，1 <= k <= 100，表示数据的组数。
对于每一组数据，第1行包含一个数N表示图片的大小为N * N，其中N <= 512且N = 2^i（i为正整数）。
接下来跟着一个N * N的矩阵代表一张二进制图片。每两个0和1之间至少有一个空格。

输出

每张图片通过四分树得到的16进制编码。

样例输入

3
2
0 0
0 0
4
0 0 1 1
0 0 1 1
1 1 0 0
1 1 0 0
8
0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 0
0 0 0 0 0 1 0 0
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

样例输出

0
114
258C0511

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int g[512][512];
int tree[1048576+5];
char code[1048576], *codeptr;
int dfs(int k, int lx, int rx, int ly, int ry) {
    if(lx > rx || ly > ry)    return 0;
    if(lx == rx && ly == ry) {
        tree[k] = g[lx][ly];
        return g[lx][ly];
    }
    int mx = (lx + rx)/2;
    int my = (ly + ry)/2;
    int s = 0;
    s += dfs((k<<2), lx, mx, ly, my);
    s += dfs((k<<2)+1, lx, mx, my+1, ry);
    s += dfs((k<<2)+2, mx+1, rx, ly, my);
    s += dfs((k<<2)+3, mx+1, rx, my+1, ry);
    tree[k] = s;
    return s;
}
void bfs(int k, int lx, int rx, int ly, int ry) {
    queue<int> K, W, H;
    K.push(k), W.push(rx-lx+1), H.push(ry-ly+1);
    int h, w;
    while(!K.empty()) {
        k = K.front(), K.pop();
        w = W.front(), W.pop();
        h = H.front(), H.pop();
        if(tree[k] == w*h || tree[k] == 0) {
            *codeptr++ = '0';
            *codeptr++ = (tree[k] != 0) + '0';
            continue;
        }
        *codeptr++ = '1';
        K.push(k<<2), W.push(w/2), H.push(h/2);
        K.push((k<<2)+1), W.push(w/2), H.push(h/2);
        K.push((k<<2)+2), W.push(w/2), H.push(h/2);
        K.push((k<<2)+3), W.push(w/2), H.push(h/2);
    }
}
int main() {
    int testcase;
    int n;
    int i, j, k;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                scanf("%d", &g[i][j]);
        int f = dfs(1, 0, n-1, 0, n-1);
        codeptr = code;
        bfs(1, 0, n-1, 0, n-1);
        *codeptr = '\0';
        int len = strlen(code), counter = len%4;
        int output = 0;
        if(counter == 0)    counter = 4;
        //printf("%s\n", code);
        for(i = 0; i < len; i++) {
            output = output<<1 | (code[i]-'0');
            if(--counter == 0) {
                printf("%X", output);
                output = 0;
                counter = 4;
            }
        }
        puts("");
    }
    return 0;
}