2014-10-06

UVa 12783 - Weak Links

Problem

是否存在 weak link，使得兩個 component 會因為 weak link 斷掉而無法連通。

Sample Input

Sample Output

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

Solution

找橋 bridge！利用 back edge 的深度進行判斷。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int visited[1024], depth[1024];
vector< pair<int, int> > bridge;
int findBridge(int u, int p, int dep) {
    visited[u] = 1, depth[u] = dep;
    int back = 0x3f3f3f3f;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(v == p)	continue;
        if(!visited[v]) {
            int b = findBridge(v, u, dep+1);
            if(b > dep)
                bridge.push_back(make_pair(u, v));
            back = min(back, b);
        } else {
            back = min(back, depth[v]);
        }
    }
    return back;
}
int main() {
    int n, m, q, x, y;
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        for(int i = 0; i < n; i++)
            g[i].clear();
        for(int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        
        bridge.clear();
        memset(visited, 0, sizeof(visited));
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                findBridge(i, -1, 0);
            }
        }
        for (int i = 0; i < bridge.size(); i++)
            if (bridge[i].first > bridge[i].second)
                swap(bridge[i].first, bridge[i].second);
        sort(bridge.begin(), bridge.end());
        printf("%d", bridge.size());
        for (int i = 0; i < bridge.size(); i++)
            printf(" %d %d", bridge[i].first, bridge[i].second);
        puts("");
    }
    return 0;
}

Read More +

2014-10-06

解題區/解題區 - UVa

UVa 12784 - Don't Care

Problem

問是否計算順序會影響結果，給一個有向圖，請問是否每一個操作都會 reduce 到同一個項目。

Sample Input

Sample Output

Solution

如果裡面有環肯定是不行的，因此需要偵測環是否存在。

在這之後，必須檢查是否會 reduce 到同一個項目，因此我們將每個 node reduce 的結果保存，之後取聯集，如果發現 reduce 項目超過一個則直接回傳失敗。

#include <stdio.h> 
#include <string.h>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
vector<int> g[1024];
set<int> A[1024];
int used[1024];
int instk[1024];
int dfs(int u) {
    used[u] = 1, instk[u] = 1;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (instk[v])
            return 1;
        if (!used[v]) {
            if(dfs(v))
                return 1;
            A[u].insert(A[v].begin(), A[v].end());
            if (A[u].size() > 1)
                return 1;
        }
    }
    if (g[u].size() == 0)
        A[u].insert(u);
    instk[u] = 0;
    return A[u].size() > 1;
}
int main() {
    int n, m, x, y;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        for (int i = 0; i < n; i++)
            g[i].clear(), used[i] = 0, A[i].clear(), instk[i] = 0;
        int indeg[1024] = {};
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            indeg[y]++;
        }
        
        int err = 0;
        for (int i = 0; i < n && !err; i++) {
            if (used[i] == 0 && indeg[i] == 0)
                err |= dfs(i);
        }
        for (int i = 0; i < n; i++) // cycle
            if (used[i] == 0)
                err = 1;
        printf("%d\n", !err);
    }
    return 0;
}
/*
3 2
0 1
1 2
2 2
0 1
0 1
2 2
0 1
1 0
3 2
0 1
0 2
0 0
*/

Read More +

2014-10-06

解題區/解題區 - Zerojudge

b317. 紅圓茵可的野望

內容：

紅圓茵可最近隱居在板擦山研究魔法師的夢想，傳說中的魔法－「召喚蘿莉」。
只要成功練就這個魔法，茵可就可以召喚出一堆蘿莉，然後跟一堆蘿莉一起……嘿嘿嘿…..
目前茵可已經研究出N種可能可以成功魔法陣，接下來就是要測試這些魔法陣能不能成功召喚蘿莉，因為數量實在太多了，所以他決定先測試其中K種。為了測試魔法陣，茵可需要先開一個異次元空間，並且在裡面做測試(因為召喚蘿莉是個極大的魔法，發動時可能會造成空間扭曲，不小心毀掉可茵城就不好了。)。魔法陣都是圓形的，半徑為r，發動一個魔法陣需要以魔法陣為底高度為h的圓柱體空間。而茵可只能開出長方體的異次元空間，一個異次元空間有其長、寬、高，而魔法陣只能放置在該空間的地板上(長 x 寬那一面)，所以要發動一個半徑為r，高度為h的魔法陣，茵可需要開一個長2r寬2r高h的異次元空間(體積2r x 2r x h)。現在茵可想要開一個異次元空間，而這個空間至少要能發動K個魔法陣(不必同時發動)，這個空間的體積至少是多少。

輸入說明：

第一行有兩個正整數 N,K(K<=N)
接下來N行每行有兩個正整數r,h代表一個魔法陣的半徑及發動需要高度(r,h<=100)

測資

N<=100
N<=100
N<=100
N<=100000
N<=100000

輸出說明：

輸出要發動其中K個魔法陣所需最小的異次元空間的體積是多少

範例輸入：

範例輸出：

提示：

範測所需體積為 224=16

可發動第1、2、5個魔法陣

Solution

這一題有兩種做法，直接窮舉 O(100 * 100) 的針對 [r, h] 找到 [0, r] x [0, h] 的數量是否大於 K，那麼可以在線性時間內完成。

而下面的做法，算是多此一步，原本想說能不能用 O(n log n) 時間內完成，但是會缺少部分調整資訊，也就是單純排序，以掃描線的基準會漏到資訊。

如果這一題的 r, h 很大的話，窮舉還是會耗費 O(n^2 log n)，套用當前最佳解剪枝應該快上很多。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
int BIT[256];
int query(int x) {
    int ret = 0;
    for (; x; x -= x&(-x))
        ret += BIT[x];
    return ret;
}
void modify(int x, int L) {
    for (; x <= L; x += x&(-x))
        BIT[x]++;
}
int main() {
    int N, K, r, h, w;
    while (scanf("%d %d", &N, &K) == 2) {
        vector<pair<int, int> > D;
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &r, &h);
            assert(r <= 100 && h <= 100 && r > 0 && h > 0);
            D.push_back(make_pair(r * 2, h));
        }
        int ret = 0x3f3f3f3f;
        sort(D.begin(), D.end());
        memset(BIT, 0, sizeof(BIT));
        for (int i = 0; i < N; i++) {
            modify(D[i].second, 255);
            for (int j = D[i].second; j <= 100; j++) {
                int q = query(j);
                w = D[i].first, h = j;
                if (q >= K)
                    ret = min(ret, w*w*h);
            }
        }
        if (K == 0)	ret = 0;
        printf("%d\n", ret);
    }
    return 0;
}

Read More +

2014-10-06

解題區/解題區 - Zerojudge

b316. 紅圓茵可的消失

內容：

「哇!我終於解出來啦!咦?茵可呢?」剛解完K大數字差的你，在茵可家到處尋找，卻始終不見紅圓茵可的身影。
四處打聽之下，得知茵可前往神秘之山－「板擦山」修練神秘的魔法去了。板擦山本身有天然的結界，只有法力高強的魔法師才有辦法進入山中。「這下子我該怎麼找到茵可呢?」你苦思著，「想找茵可嗎?我可以告訴你怎麼找到茵可!」似乎是剛好路過的長頸鹿這麼說道。
板擦山的山腳下有好幾間便利商店，這些便利商店剛好開在結界外，茵可每天都會到山下的其中一間購買民生用品，而且到哪家便利商店是可以預測的。板擦山上有N個點，每個點有各自的編號，越高的點編號越小，點跟點之間有道路連接，茵可所在的山頂為編號0的點，便利商店也是其中的一個點。茵可每天會由山頂出發，經過一些點後到山下的便利商店買東西。當茵可走到一個點x後，他會先走跟x有連接的點中，編號比x大(當然要往山下走阿)的點中，編號最小的那一個。而下一次又到x時就走第二小的，直到編號比x大的點都走過一次，就會回到最小的點繼續走。(假設 3號點連到 1,4,5，第一次到3時，茵可會走向4。下一次到3時，茵可會走向5。再下一次到3時，茵可會走向4。)若一個點沒有連到編號比它大的點，則該點為便利商店。
你從長頸鹿手中的到了板擦山的地圖，你就可以預測茵可在第K天時會走到哪一家便利商店了!

輸入說明：

第一行有兩個正整數N,M,K，表示有N個點(編號0~N-1)、M條邊(M<=N*(N-1)/2)及詢問第K天茵可會到哪個點。
接下來M行每行有兩個整數a,b表示a跟b間有一條邊(保證同樣兩個點間只會有一條邊)。

測資

N<=10,K<=100
N<=10,K<=100
N<=1000,K<=1000
N<=1000,K<=1000000000，整張圖為一棵樹
N<=1000,K<=1000000000

輸出說明：

輸出第K天時茵可會走到哪個點。

範例輸入：

範例輸出：

提示：

範例測資
第一天 0→1→2→3
第二天 0→2→3
第三天 0→4
第四天 0→1→4

Solution

一開始曲解題目了，不過沒關係。

首先讓我們來了解多久一循環，根據公式$cycle(u) = \sum cycle(v) | u \rightarrow v$，這個很容易理解的，事實上 cycle(0) 可能很大派不上用場。

如果試圖用週期 M 天，則期望用模擬迭代到 M 天是否與第一天相同，則很容易在 M + 1 天不會與第二天相同，因為路徑相同不代表狀態相同。

藉此我們利用動態規劃的概念，來找尋狀態的基底位置。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int main() {
    int N, M, K;
    int x, y;
    while (scanf("%d %d %d", &N, &M, &K) == 3) {
        for (int i = 0; i < N; i++)
            g[i].clear();
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &x, &y);
            if (x > y)	swap(x, y);
            g[x].push_back(y);
        }
        for (int i = 0; i < N; i++)
            sort(g[i].begin(), g[i].end());
        int pass[1024] = {};
        int now = 0, x, sum = 0;
        pass[0] = --K;
        for (int i = 0; i < N; i++) {
            if (g[i].size() == 0)	continue;
            int u = i, v, div = pass[u] % g[i].size();
            for (int j = 0; j < g[i].size(); j++) {
                v = g[i][j];
                pass[v] += pass[u] / g[i].size();
                if (j < div)
                    pass[v]++;
            } 
        }
        for (; g[now].size(); ) {
            x = pass[now]%g[now].size();
            now = g[now][x];
//			printf("-> %d\n", now);
        }
        printf("%d\n", now);
    }
    return 0;
}
/*
5 6 1
0 1
0 2
1 2
2 3
0 4
1 4
5 6 2
0 1
0 2
1 2
2 3
0 4
1 4
5 6 3
0 1
0 2
1 2
2 3
0 4
1 4
5 6 4
0 1
0 2
1 2
2 3
0 4
1 4
*/

Read More +

2014-10-06

解題區/解題區 - Zerojudge

b315. 紅圓茵可的考驗

內容：

身為魔法師的你，想讓自己變得更強大，於是前來膜拜紅圓茵可，同時想請教他學習魔法的秘訣。經過日復一日的嘗試，你終於通過了柏油路，並且來到茵可家。「看在你這麼努力的份上，我就稍微指導你一下吧。」茵可說道。「所謂魔法，跟程式設計很像，就是一堆指令的結合。將分子移動、放熱、發光等等基礎的小魔法結合在一起，就會變成強大的魔法(像是防護罩就是控制空氣分子的移動，並使其重新排列成為堅固的結構，達到防禦的效果。)。所以說，腦中運算的能力是很重要的。」語畢，茵可大大丟給你一個題目:

給你N個數字，挑出其中兩個數字可以得到一個數字差(非負)，而N個數字會有N*(N-1)/2個數字差，問第K大數字差是多少?
如範例輸入，數字差有6個，分別為9(10-1)、7(8-1)、5(10-5)、4(5-1)、3(8-5)、2(10-8)，其中第5大的是3。

「等你能在1秒內解完這個問題再來找我吧!」隨後茵可打開比較大的門走掉了。

輸入說明：

第一行有兩個正整數N,K
接下來有N個整數(0<=每個整數<=1,000,000,000)

測資

N<=10，K<=N*(N-1)/2
N<=1,000，K<=N*(N-1)/2
N<=10,000，K<=10,000
N<=100,000，K<=100,000
N<=100,000，K<=1,000,000,000

輸出說明：

輸出第K大數字差

範例輸入：

1 2	4 5 1 5 8 10

範例輸出：

Solution

使用二分搜索答案，通常是查找第 K 小的元素，這題是換成第 K 大元素，那麼就反過來找，中間調校的時候要特別小心。

代碼效率是 O(n log^2 n)，事實上可以壓成 O(n log n)，因為中間的索引值肯定是單調的，不過要考慮組合問題，特別要小心同一個元素自減的結果。由於懶得判斷，複雜度高了點還是過了。

#include <stdio.h>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
int kThDiff(int A[], int n, long long m) {
    int mx = A[0], mn = A[0];
    for (int i = 0; i < n; i++)
        mx = max(mx, A[i]), mn = min(mn, A[i]);
    int l = 0, r = mx - mn, mid, ret;
    m = (long long) n * (n-1)/2 - m + 1;
    long long cnt;
    sort(A, A+n);
    while (l <= r) {
        mid = (l + r)/2;
        cnt = 0;
        for (int i = 0; i < n; i++) {
            int pos = (int)(upper_bound(A+i, A+n, A[i] + mid) - A);
            cnt += pos - i - 1;
        }
        if (cnt >= m)
            r = mid - 1, ret = mid;
        else
            l = mid + 1;
    } 
    return ret;
}
int main() {
    int n, m, A[131072];
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        printf("%d\n", kThDiff(A, n, m));
    }
    return 0;
}
/*
9 4
4 6 3 7 7 5 0 8 9 
5 1
7 4 2 5 2 
10 3
4 6 9 8 7 1 1 4 2 0 
9 20
3 8 6 2 1 9 6 7 2 
2 1
2 6 
4 4
0 9 0 0 
5 7
4 0 9 1 8 
11 30
1 2 1 6 1 0 7 7 5 2 5 
4 3
4 7 5 8 
2 1
1 6 
10 40
7 5 5 0 2 9 4 9 6 2 
3 2
6 8 7 
10 28
3 5 0 8 1 1 7 9 2 1 
9 3
6 7 1 2 0 8 5 1 0 
8 22
0 3 1 9 1 8 4 7 
11 20
2 3 0 4 7 1 7 6 2 2 1 
3 1
7 3 9 
4 2
9 2 4 5 
10 39
6 5 2 3 6 1 1 8 1 9 
8 7
4 9 7 2 1 6 3 2 
*/

Read More +

2014-10-05

解題區/解題區 - Zerojudge

b314. 紅圓茵可的煩惱

內容：

相信大家都知道紅圓茵可是誰，就不多介紹了。最近他有一個煩惱，身為一位大魔法師，每天都有成千上萬的人來膜拜他<( )>。因為人數實在太多了，這麼多人跑到他家膜拜他，害他都無法好好練習魔法了。茵可家門前有一條柏油路，要到他家一定得經過這條柏油路，他決定把這條柏油路(長方形)切成N*M個格子，並且在其中某些格子設下陷阱，踩到陷阱的人會被傳送回柏油路的起點。「恩~這樣子就可以減少膜拜我的人了~」紅圓茵可心想。但是，為了讓jackyXX等人可以到達他家，也不能把柏油路封死，必須確保一定有條路徑可以走到茵可家。而你的任務是要提醒茵可大大<( )>，哪些點能放陷阱，而哪些點不能放陷阱(導致道路封死)。
柏油路的起點在左邊，而茵可家在柏油路的右邊。一個人在柏油路上只能往上下左右四個方向走，不能走斜對角。

一條3*10的柏油路

oooooooooo
oooooooooo
oooooooooo

一條被封死的柏油路

ooooxooooo
oooxoooooo
ooxooooooo

一條沒被封死的柏油路

xxxxxxoooo
oooooxoxxx
ooxxoooxoo

輸入說明：

第一行有3個正整數N、M、T，T為茵可接下來要放的陷阱數量(0<T<=N*M)。
接下來T行每行有2個非負整數x,y表示這個陷阱要放的位址。
縱軸為x軸，橫軸為y軸，左下角那格為(0,0)。
保證一個點只會被放最多一次。

測資

N,M<=10
N,M<=50
N,M<=100
N,M<=1000
N,M<=1000

輸出說明：

對每一個要放的陷阱，若該點可放，請輸出一行”<( )>”(不含雙引號)，並且把陷阱放上去。
若該點不可放(會導致道路封死)，請輸出”>_<”(不含雙引號)，並且不放該陷阱。

範例輸入：

範例輸出：

<(_ _)>
<(_ _)>
>_<
>_<
<(_ _)>

Solution

這一題相當活用并查集的概念，雖然題目問說是否能左右相連，但是反過來則是上下邊界是否會從不相連變成相連。

多設兩個虛點，我們假想所有上界點都與虛上點相連，下界點都與虛下點相連，每次一次加入一個障礙物時，檢查九宮格內是否會造成上下虛點相連，這裡必須先偷看并查集的結果，隨後在考慮是否將其相連。

#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int parent[1048576], weight[1048576];
int used[1024][1024];
const int dx[] = {1, 1, 1, -1, -1, -1, 0, 0};
const int dy[] = {0, 1, -1, 0, 1, -1, 1, -1};
int findp(int x) {
    return parent[x] == x ? parent[x] : parent[x] = findp(parent[x]);
}
int joint(int p, int q) {
    p = findp(p), q = findp(q);
    if (weight[p] > weight[q])
        weight[p] += weight[q], parent[q] = p;
    else
        weight[q] += weight[p], parent[p] = q;
    return 1;
}
int main() {
    int n, m, Q, cases = 0;
    int x, y, tx, ty;
    while (scanf("%d %d %d", &n, &m, &Q) == 3) {
        cases++;
        int N = n * m + 10, up = n * m + 1, down = n * m + 2;
        int p, q, A[8];
        for (int i = 0; i < N; i++)
            parent[i] = i, weight[i] = 1;
        for (int i = 0; i < Q; i++) {
            scanf("%d %d", &x, &y);
            p = x * m + y;
            up = findp(up), down = findp(down);
            int s = 0;
            for (int j = 0; j < 8; j++)	{
                tx = x + dx[j], ty = y + dy[j];
                if (ty < 0 || ty >= m)	{
                    A[j] = p;
                    continue;
                }
                if (tx < 0)			q = up;
                else if(tx >= n)	q = down;
                else {
                    if (used[tx][ty] != cases) {
                        A[j] = p;
                        continue;
                    }
                    q = tx * m + ty;
                }
                if (findp(q) == up)		s |= 1;
                if (findp(q) == down)	s |= 2;
                A[j] = q;
            }
            if (s != 3) {
                puts("<(_ _)>");
                for (int j = 0; j < 8; j++) {
                    joint(p, A[j]);
                }
                used[x][y] = cases;
            } else {
                puts(">_<");
            }
        }
    }
    return 0;
}

Read More +

2014-10-05

解題區/解題區 - UVa

UVa 225 - Golygons

Problem

每一步轉角九十度，並且第 i 次要走 i 長單位，回到原點且沿途不經過障礙物，同時轉角不可重複。

Sample Input

Sample Output

wsenenws
Found 1 golygon(s).
Found 0 golygon(s).

Solution

沿途經過障礙物，同時轉角不重複。一開始曲解了經過的轉角點，以為他也不能在隨後中經過，但實際上是可以的，因此拿了不少 WA。

#include <stdio.h> 
#include <stdlib.h>
#include <algorithm>
#include <set>
#include <vector>
#include <iostream>
#include <assert.h>
using namespace std;
int n, m, golygons;
set< pair<int, int> > ban;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const char sdir[] = "nsew";
char path[1024];
char g[2048][2048] = {}, g2[2048][2048];
vector<string> ways;
#define BASE 1024
void dfs(int x, int y, int dir, int step) {
    if (abs(x - 0) + abs(y - 0) > (step + n) * (n - step + 1)/2) {
        return;
    }
    if (step == n + 1) {
        if (x == 0 && y == 0) {
            path[step - 1] = '\0';
//			puts(path);
            ways.push_back(path);
            golygons++;
        }
        return ;
    }
    if (dir != 0) {
        for (int i = 0; i < 2; i++) {
            int tx = x, ty = y, ok = 1;
            for (int j = 0; j < step; j++) {
                tx = tx + dx[i], ty = ty + dy[i];
                assert(BASE + tx >= 0 && BASE + ty >= 0);
                assert(BASE + tx < 2048 && BASE + ty < 2048);
                if (g[BASE + tx][BASE + ty]) {
                    ok = 0;
                    break;
                }
            }
            if (ok && g2[BASE + tx][BASE + ty] == 0) {
                g2[BASE + tx][BASE + ty] = 1;
                path[step - 1] = sdir[i];
                dfs(tx, ty, 0, step + 1);
                g2[BASE + tx][BASE + ty] = 0;
            }
        }
    }
    if (dir != 1) {
        for (int i = 2; i < 4; i++) {
            int tx = x, ty = y, ok = 1;
            for (int j = 0; j < step; j++) {
                tx = tx + dx[i], ty = ty + dy[i];
                assert(BASE + tx >= 0 && BASE + ty >= 0);
                assert(BASE + tx < 2048 && BASE + ty < 2048);
                if (g[BASE + tx][BASE + ty]) {
                    ok = 0;
                    break;
                }
            }
            if (ok && g2[BASE + tx][BASE + ty] == 0) {
                g2[BASE + tx][BASE + ty] = 1;
                path[step - 1] = sdir[i];
                dfs(tx, ty, 1, step + 1);
                g2[BASE + tx][BASE + ty] = 0;
            }
        }
    }
}
int main() {
    int testcase, x[64], y[64];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        ban.clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x[i], &y[i]);
            ban.insert(make_pair(x[i], y[i]));
            g[BASE + x[i]][BASE + y[i]] = 1;
        }
        ways.clear();
        dfs(0, 0, -1, 1);
        sort(ways.begin(), ways.end());
        for (int i = 0; i < ways.size(); i++)
            puts(ways[i].c_str());
        printf("Found %d golygon(s).\n\n", ways.size());
        for (int i = 0; i < m; i++)
            g[BASE + x[i]][BASE + y[i]] = 0;
    }
    return 0;
}
/*
2
8
2
-2 0
6 -2
8
2
2 1
-2 0
1000
16
0
*/

Read More +

2014-10-05

解題區/解題區 - UVa

UVa 12785 - Emacs Plugin

Problem

每個 * 位置，可以任意替換成任何字串或者是空字串，是問是否有可能匹配主字串。

Sample Input

4
heyhelloyou
hel*
*o*e
e*o
hello
1
hello
x

Sample Output

yes
no
yes
yes
no

Solution

以 * 劃分，將其切割成好幾個 token，根據貪心原則只要按照順序出現這些 token 即可，因此盡可能靠左。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <sstream>
using namespace std;
#define MAXN 100005
char P[MAXN], T[MAXN];
int kmpTable[MAXN];
void KMPtable(const char *P, int len) {
    int i, j;
    kmpTable[0] = -1, i = 1, j = -1;
    while(i < len) {
        while(j >= 0 && P[j+1] != P[i])
            j = kmpTable[j];
        if(P[j+1] == P[i])
            j++;
        kmpTable[i++] = j;
    }
}
int KMPmatching(const char *T, int tlen, const char *P, int plen) {
    for(int i = 0, j = -1; i < tlen; i++) {
        while(j >= 0 && P[j+1] != T[i])
            j = kmpTable[j];
        if(P[j+1] == T[i])  j++;
        if(j == plen-1)
        	return i;
    }
    return -1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, plen, tlen;
    string token;
    while (scanf("%d", &n) == 1) {
        while (getchar() != '\n');
        gets(P);
        plen = strlen(P);
        for (int i = 0; i < n; i++) {
            gets(T);
            for (int j = 0; T[j]; j++) {
                if (T[j] == '*')
                    T[j] = ' ';
            }
            stringstream sin(T);
            int start = 0;
            while (sin >> token) {		
                KMPtable(token.c_str(), token.length());
                int test = KMPmatching(P + start, plen - start, token.c_str(), token.length());
//				printf("%s %d %s\n", token.c_str(), test, P + start);
                if (test == -1)	 {start = -1; break;}
                start += test + 1;
            }
            puts(start == -1 ? "no" : "yes");
        }
    }
    return 0;
}
/*
4
heyhelloyou
hel*
*o*e
e*o
hello
1
hello
x
10
rwoeyhtdvtswftfguuujqxdxdqylkyqaahianzbejckxbgeybq
oexktdvtswftf*w*n*q*rvdloll*qr
kdd*ts*ftv**ur**cdx*qi
*dtlk
**q**g****a**n
*/

Read More +

2014-10-05

解題區/解題區 - UVa

UVa 10597 - Right Words

Problem

對一個已經是 Chomsky normal form 的 CFG，問一個 string 是否在 CFG 之中。

Sample Input

S
SABC
ab
S -> AB
S -> BC
A -> BA
A -> a
B -> CC
B -> b
C -> AB
C -> a
# -> #
baaba
ab
abaa
a
aaaaa
bbbbb
#
S
SAB
ab
S -> AB
A -> AA
A -> a
B -> b
# -> #
ab
aaab
aba
baaaaaaaa
abbbbbb
aaaaaba
baaaaaaaab
aaaa
a
ab
#

Sample Output

baaba is in L(G)
ab is in L(G)
abaa is in L(G)
a is not in L(G)
aaaaa is in L(G)
bbbbb is not in L(G)
 
ab is in L(G)
aaab is in L(G)
aba is not in L(G)
baaaaaaaa is not in L(G)
abbbbbb is not in L(G)
aaaaaba is not in L(G)
baaaaaaaab is not in L(G)
aaaa is not in L(G)
a is not in L(G)
ab is in L(G)

Solution

因為 chomsky normal form 恰好劃分成兩個，定義字串 dp[l][r] 中可以解析出那些 nonterminal，藉由矩陣鍊乘積的方式，將其組合。最後檢查整個字串是否可以推回 start symbol。

#include <stdio.h> 
#include <string.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    char s1[1024], s2[1024];
    while (scanf("%s", s1) == 1) {
        char start = s1[0];
        scanf("%*s %*s");
        set<char> re[128];
        set<char> rule[128][128];
        while (scanf("%s -> %s", s1, s2) == 2 && s1[0] != '#') {
            if (s2[1] == '\0')
                re[s2[0]].insert(s1[0]);
            else {
                rule[s2[0]][s2[1]].insert(s1[0]);
            }
        }
        while (scanf("%s", s1) == 1 && s1[0] != '#') {
            int n = strlen(s1);
            set<char> dp[64][64];
            for (int i = 0; i < n; i++) {
                dp[i][i].insert(re[s1[i]].begin(), re[s1[i]].end());
            }
            for (int i = 1; i < n; i++) {
                for (int j = 0; i + j < n; j++) {
                    for (int k = j; k < i+j; k++) {
                        for (set<char>::iterator a = dp[j][k].begin();
                            a != dp[j][k].end(); a++)
                        for (set<char>::iterator b = dp[k+1][i+j].begin();
                            b != dp[k+1][i+j].end(); b++)
                            dp[j][i+j].insert(rule[*a][*b].begin(), rule[*a][*b].end());
                    }
                }
            }
            printf("%s is %sin L(G)\n", s1, dp[0][n-1].find(start) == dp[0][n-1].end() 
                                        ? "not " : "");
        }
        puts("");
    }
    return 0;
}

Read More +

2014-10-05

學校課程/計算幾何

計算幾何 - HW01

Chapter 1

1.1

The convex hull of a set S is defined to be the intersection of all convex sets that contain S. For the convex hull of a set of points it was indicated that the convex hull is the convex set with smallest perimeter. We want to show that these are equivalent definitions

a. Prove that the intersection of two convex sets is again convex. This implies that the intersection of a finite family of convex sets is convex as well.
b. Prove that the smallest perimeter polygon P containing a set of points P is convex.
c. Prove that any convex set containing the set of points P contains the smallest perimeter polygon P.

a. 證明兩個凸包交集仍然是凸包
假設凸包分別為$C1, C2$，題目所求$C = C1 \bigcap C2$
已知：A set$K$ is convex if each$u \neq v$, the line-segment$\bar{uv}$ is contained in$K$,$\bar{uv}\subseteq K$
假設$C$ 不是凸包，則存在$\bar{uv} \nsubseteq C$，根據定義$u, v \in C1, C2$，得到$\bar{uv} \nsubseteq C1, C2$，矛盾得證$C$ 一定是凸包。

b. 證明最小周長的多邊形 P 包含所有點集 S 一定是凸包
假設$P$ 是最小周長的非凸包多邊形，令$x, y \in P, and \bar{xy} \nsubseteq P$，則$\bar{xy}$ 會交$P$ 於至少兩點$x', y'$$P'$ 是將$\bar{x^{'}y^{'}}$ 連起所產生的新多邊形，顯然地$P'$ 的周長更小。矛盾得證。

c. 證明任何一個凸多邊形 C 包含點集 S 的同時也一定會包含最小周長的多邊形 P。
假設有 vertex$v \in P, but v \notin C$，同時 v 不會在 S 範圍中，因為 C 已經包含了 S$v1, v2$ 為$C, P$ 交點，則$P'$ 是$v1, v2$ 相連產生的多邊形，則 P’ 藉由 (b) 一定是多邊形，v1 到 v2 的距離更短，找到一個周長更小的多邊形。矛盾得證。

1.3

Let E be an unsorted set of n segments that are the edges of a convex polygon. Describe an O(nlogn) algorithm that computes from E a list containing all vertices of the polygon, sorted in clockwise order.

Algorithm:

得到所有點${(x1, y1), (x2, y2), ..., (xn, yn)}$，並且附加是屬於哪兩個邊的端點對點作排序。map< point, vector<seg> > R - O(n log n)

挑最左下的角當作$(x1, y1)$ 的其中一邊

A[0] = (x0, y0) = R.begin().first;
for (int i = 0; i < E.size(); i++) {
    for (seg s : R[A[0]]) {
        if (s.p0 == A[i] && (i == 0 || s.p1 != A[i-1]))
            A[i+1] = s.p1;
    }
}

檢查是否為順時針，否則反轉序列 - O(n)

1.8

The O(nlogn) algorithm to compute the convex hull of a set of n points in the plane that was described in this chapter is based on the paradigm of incremental construction: add the points one by one, and update the convex hull after each addition. In this exercise we shall develop an algorithm based on another paradigm, namely divide-and-conquer.

a. Let P1 and P2 be two disjoint convex polygons with n vertices in total. Give an O(n) time algorithm that computes the convex hull of P1 ∪P2.
b. Use the algorithm from part a to develop an O(nlogn) time divide-andconquer algorithm to compute the convex hull of a set of n points in the plane.

D&C 的 O(n log n) 凸包算法

a. 將兩個沒有相交的凸包，用 O(n) 時間內合併凸包$P1 \cup P2$。

假設兩個凸包儲存方式都是逆時針順序，並第一個節點為最左下的節點。
Algorithm:

將最左側的凸包另為 P1，反之 P2。

代碼如下，找到下凸包 - O(n)

vector C
C[m = 0] = P1[0]
for (i = 1, j = 0; i < P1.size(); i++) {
    if (m >= 2 && cross(C[m-1] - C[m-2], P2[j] - C[m-2]) <= 0)
        break;
    C[m++] = P1[i]
}
for (; j < P2.size(); j++)
    while (m >= 2 && cross(C[m-1] - C[m-2], P2[j] - C[m-2]) <= 0)
        m--;
    C[m++] = P2[j];

仿 2. 反過來作，找到上凸包 - O(n)
上下凸包合併 - O(n)

b.
Algorithm:

將所有點按照 x 做升排序 - O(n log n)

convex DC(int l, int r, point p[]) {
    if (l == r)
        return convex(p[l])
    convex leftconvex = DC(l, (l + r)/2, p);
    convex rightconvex = DC((l+r)/2 + 1, r, p);
    return merge(leftconvex, rightconvex);
}

Prove$T(n) = 2 T(n/2) + O(n)$,
by master theorem:$a = 2, b = 2, c = 1, log_{a}b = c, \Rightarrow T(n) = \theta (n^{c} log n) = \theta (n log n)$

Chapter 2

2.1

Let S be a set of n disjoint line segments whose upper endpoints lie on the line y=1 and whose lower endpoints lie on the line y=0. These segments partition the horizontal strip [−∞ : ∞]×[0 : 1] into n+1 regions. Give an O(nlogn) time algorithm to build a binary search tree on the segments in S such that the region containing a query point can be determined in O(logn) time. Also describe the query algorithm in detail.

參閱實作 b321: 河道分界

Algorithm: (build)

sort 線段 (根據上方的 (x, 1) 進行由小排到大 ) - O(n log n)

靜態建造，動態建造請參閱可平衡的 BST。因為任切一條 y = k 的線，保證相交的 x 值得順序不會變 (跟排序結果的順序相比)，因此一開始挑 y = 1 來做排序依據。

root = dfs(0, n - 1, segments) - `O(n)`
node dfs(int l, int r, segment segs[]) {
    if (l == r)
        return new node(segs[l]);
    else if (l < r)
        int mid = (l + r)/2;
        node ret = new node(segs[mid]);
        ret.lson = dfs(l, mid - 1, segs);
        ret.rson = dfs(mid + 1, r, segs);
        return ret;
    else
        return NULL;
}

Algorithm: (query)

令 lbound = null, rbound = null

走訪 BST

void query(node u, point p) {
    if u == NULL
        return;
    if p leftside by u.seg
        rbound = u
        dfs(u.lson, p)
    else
        lbound = u
        dfs(u.rson, p)
}

output (lbound, rbound)

2.5

Which of the following equalities are always true?
$$(1) Twin(Twin(\vec{e})) = \vec{e} \\ (2) Next(Prev(\vec{e})) = \vec{e} \\ (3) Twin(Prev(Twin(\vec{e}))) = Next(\vec{e}) \\ (4) IncidentFace(\vec{e}) = IncidentFace(Next(\vec{e})) \\$$

(1)(2)(4) are always true. (3) may not be true.

2.6

Give an example of a doubly-connected edge list where for an edge e the faces$IncidentFace(\vec{e})$ and$IncidentFace(Twin(\vec{e}))$ are the same.

已知$IncidentFace(\vec{e}) = IncidentFace(Next(\vec{e}))$ always true，讓$Next(\vec{e}) = Twin(\vec{e})$ always true。

Half-edge	Orign	Twin	IncidentFace	Next	Prev
$\vec{e_{1, 2}}$	$v_{1}$	$\vec{e_{2, 1}}$	f1	$\vec{e_{2, 1}}$	$\vec{e_{2, 1}}$
$\vec{e_{2, 1}}$	$v_{2}$	$\vec{e_{1, 2}}$	f1	$\vec{e_{1, 2}}$	$\vec{e_{1, 2}}$

2.14

Let S be a set of n disjoint line segments in the plane, and let p be a point not on any of the line segments of S. We wish to determine all line segments of S that p can see, that is, all line segments of S that contain some point q so that the open segment pq doesn’t intersect any p not visible line segment of S. Give an O(nlogn) time algorithm for this problem that uses a rotating half-line with its endpoint at p.

參閱實作 b325: 人格分裂

Algorithm:

對於所有的端點相對 p 做極角排序，並且知道相對應的角度上會存有那些線段的端點。

map<double, vector<int, int> > angle;
for (int i = 0; i < n; i++) {
    double v1 = atan2(D[i].s.y - pos.y, D[i].s.x - pos.x);
    double v2 = atan2(D[i].e.y - pos.y, D[i].e.x - pos.x);
    angle[v1].push_back(make_pair(i, 0));
    angle[v2].push_back(make_pair(i, 1));
}

藉由出現的角度，使用極角掃描，一開始必須將碰的線段加入。

double c;
CMP::base = pos;
double ftheta = angle.begin()->first;
pair<int, int> u = angle.begin()->second[0];
Pt fpt;
if (u.second == 0)
    fpt = D[u.first].s;
else
    fpt = D[u.first].e;
for (int i = 0; i < n; i++) {
    if (cross(pos, fpt, D[i].s) * cross(pos, fpt, D[i].e) < 0)
        S.insert(D[i]);
}
CMP::sin = sin(ftheta);
CMP::cos = cos(ftheta);
for (map<double, vector< pair<int, int> >, CMP2>::iterator it = angle.begin();
    it != angle.end(); it++) {
    CMP::sin = sin(it->first);
    CMP::cos = cos(it->first);
    for (int i = 0; i < it->second.size(); i++) {
        pair<int, int> u = it->second[i];
        if (u.second == 0)
            c = cross(pos, D[u.first].s, D[u.first].e);
        else
            c = cross(pos, D[u.first].e, D[u.first].s);
        if (fabs(c) > eps) {
            if (c > 0)
                S.insert(D[u.first]);
            else
                S.erase(D[u.first]);
        }
    }
    if (S.size()) {
        visual[S.begin()->label] = 1;
    }
}

心得

出題目，出題目，萌萌哒

Read More +

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

Chapter 1

1.1

1.3

1.8

Chapter 2

2.1

2.5

2.6

2.14

心得

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

提示：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

提示：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：