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

49愛的鼓勵 6訂閱站台

Background
PTC 噩夢啊, 比賽過一個小時後, 我才從通識回來 ... 最終結果 4 題, 好不容易看懂 pD 的繁瑣英文, 我悲摧的來不及寫完, 還在 compile, 時間已經抵達終點 ! 神啊, 請再給我一個小時

---

Problem A
題意很簡單, 先給定平面 n 個點 (POI),然後對每個詢問集輸出, 有多少"次"的 POI 在詢問集的半徑內, 首先先看 n ≦ 100,0000, 直覺告訴我們 O(n*m) 是不可能通過的, 聽 inker 賽後說道這題應該是有一篇論文(range query)的寫法, 當然比賽的時候不可能會想那麼多, 猶豫就輸了。還是 O(n*m) 下吧

#include <stdio.h>
using namespace std;
typedef struct {
    long long x, y;
} Pt;
Pt P[1000005], Q[1000005];
int main() {
    int n, i, j, m;
    long long d;
    while(scanf("%d", &n) == 1) {
        int tn = 0;
        for(i = 0; i < n; i++) {
            scanf("%lld %lld", &P[i].x, &P[i].y);
        }
        while(scanf("%d %lld", &m, &d) == 2) {
            if(m == 0 && d == 0)    break;
            for(i = 0; i < m; i++)
                scanf("%lld %lld", &Q[i].x, &Q[i].y);
            int ans = 0;
            for(i = 0; i < n; i++) {
                for(j = 0; j < m; j++) {
                    if((P[i].x-Q[j].x)*(P[i].x-Q[j].x)
                       + (P[i].y-Q[j].y)*(P[i].y-Q[j].y)
                       <= d*d) {
                       ans++;
                    }
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

---

Problem B
簡單的去重問題, 求真正存在的使用者個數

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

int main() {
    int t;
    char in[50];
    scanf("%d", &t);
    gets(in);
    while(t--) {
        set<string> Q;
        while(gets(in)) {
            if(in[0] == '-')    break;
            Q.insert(in);
        }
        printf("%d\n", Q.size());
    }
    return 0;
}

---

Problem C
這題會給定一個遞增的序列, 然後挑兩項當做費式數列的首兩項, 然後看最多能再這個序列裡面湊到最多的費式數列, 有人會想說用動態規劃 DP, 直觀想是 O(n*n), 有點類似 LIS 的建法, 那當然也可以, 不過窮舉也是差不多的速度, 差不多是 O(n*n*k), 但是 k 肯定是很小的, 因為以最小的費式數列, k 也頂多 25, 而且窮舉可以剪枝, 說不定比 DP 還快。

#include <stdio.h>
int main() {
    int t;
    int i, j, n, x, f0, f1;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        int f[100000] = {};
        int a[50005];
        for(i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            f[a[i]] = 1;
        }
        int ans = 2;
        for(i = 0; i < n; i++) {
            for(j = i+1; j < n; j++) {
                if(n-j+1 <= ans)
                    break;
                f0 = a[i], f1 = a[j];
                int cnt = 2;
                while(1) {
                    x = f0+f1;
                    f0 = f1;
                    f1 = x;
                    if(x > a[n-1] || f[x] == 0)
                        break;
                    cnt++;
                }
                if(cnt > ans)   ans = cnt;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

---

Problem E
給一個條件的遞歸圖形, 專有名稱應該是「碎形」, 然後問一個點在幾個長方形中, 那麼直觀的遞迴找出所有長方形, 然後去判斷是否在裡面就好了, 有一題很像的在 UVa, 如果我沒記錯題目應該是「All Square」

#include <stdio.h>

int k, n, m, ans;
void dfs(int x, int y, int k) {
    if(k == 0)
        return ;
    if(x-2*k <= n && x+2*k >= n && y-k <= m && y+k >= m)
        ans++;
    dfs(x+2*k, y+k, k/2);
    dfs(x+2*k, y-k, k/2);
    dfs(x-2*k, y+k, k/2);
    dfs(x-2*k, y-k, k/2);
}
int main() {
    while(scanf("%d %d %d", &k, &n, &m) == 3) {
        if(k == 0 && n == 0 && m == 0)
            break;
        ans = 0;
        dfs(1024, 1024, k);
        printf("%d\n", ans);
    }
    return 0;
}

---

總結 :
這次題目難的可以很難, 不過我想出題教授應該沒有考慮的測試機器的效率, 導致濫做法可以通過, 晚了一個小時, 因此沒解出 pD, 時間上看完題目就耗費了我 30 分鐘, 英文很菜的, 很多題目看不是很懂, 單字量也不夠, 都是拿之前的解題感覺猜測題目想要求我們做些什麼。

一次 PTC 大概有一題是難題, 然而其他題猶豫就輸了, 不仿拿出不合理的複雜度去嘗試吧