解題區/解題區 - UVa

UVa 13070 - Palm trees in the snow

Problem

給一排棕梠樹的樹高 $H_i$，經過大雪後，高度 $H_i \ge W$ 的樹都會攤倒，挑選一個區間滿足最多五棵屹立不搖的情況下，請問區間長度最長為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
3
30
10
10  30  50  20  40  60  30  40  50  36
40
10
10  30  50  20  40  20  10  10  20  36
20
3
40  10  15

Sample Output

1
2
3
7
10
3

Solution

將會倒的位置記錄下來，線性掃描過去即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        int W, N, x;
        scanf("%d %d", &W, &N);
        vector<int> A;
        A.push_back(-1);
        for (int i = 0; i < N; i++) {
            scanf("%d", &x);
            if (x >= W)
                A.push_back(i);
        }
        A.push_back(N);
        int ret = 0;
        for (int i = 1; i < A.size()-1; i++) {
            int x = A[min(i+5, (int)A.size()-1)];
            ret = max(ret, x - A[i-1]-1);
        }
        if (A.size() == 2)	ret = N;
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13036 - Birthday Gift to SJ - 2

Problem

問在區間 $[a, b]$ 之中最大的 interesting number，所謂的 interesting number 就是分解成數個費波納契數的乘積。

Sample Input

1
2
3
4
3
1  7
1  10
1  1000000000000000000

Sample Output

1
2
3
6
10
1000000000000000000

Solution

由於費波納契數成長速度非常快，用不著擔心會有好幾種不同數構成，因此可以採用中間相遇法，將前幾個小的費波納契數任意組合，後半則是剩餘的組合。至於要從哪裡開始拆團，必須手動測一下。

而這一題詢問次數非常多，儘管建好表，$\mathcal{O}(N \log N)$ 的搜索相當慢，甚至會 TLE，最好使用一次二分搜尋，或者利用單調性質降到 $\mathcal{O}(N)$ 以下最為保險。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
// Algorithm: Meet in Middle
const int MAXN = 85;
const long long MAXV = 1e+18;
long long F[100] = {2, 3};
vector<long long> S1, S2;
void bfs(int begin, int end, vector<long long> &S) {
    S.push_back(1);
    for (int i = begin; i < end; i++) {
        long long x = F[i];
        vector<long long> next(S);
        for (auto e : S) {
            while (MAXV / e / x) {
                e *= x;
                next.push_back(e);
            }
        }
        S = next;
    }
    sort(S.begin(), S.end());
  	S.resize(unique(S.begin(), S.end()) - S.begin());
}
int main() {
    for (int i = 2; i < MAXN; i++) {
        F[i] = F[i-1] + F[i-2];
        assert(F[i] / MAXV == 0);
    }
    int split = 9;
    bfs(0, split, S1);
    bfs(split, MAXN, S2);
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        long long a, b;
        long long ret = -1;
        scanf("%lld %lld", &a, &b);
        int idx1 = 0, idx2 = S2.size()-1;
        for (; idx1 < S1.size(); idx1++) {
            if (S1[idx1] > b)	break;
            long long e = S1[idx1];
            while (idx2 > 0 && b / S2[idx2] / e == 0)
                idx2--;
            long long t = S2[idx2] * e;
            if (t >= a)
                ret = max(ret, t);
        }
        vector<long long>::iterator it = lower_bound(S1.begin(), S1.end(), b);
        if (it == S1.end() || it != S1.begin() && *it > b)	it--;
        if (it != S1.end() && b / *it) {
            long long t = *it;
            if (t >= a)
                ret = max(ret, t);
        }
        it = lower_bound(S2.begin(), S2.end(), b);
        if (it == S2.end() || it != S2.begin() && *it > b)	it--;
        if (it != S2.end() && b / *it) {
            long long t = *it;
            if (t >= a)
                ret = max(ret, t);
        }
        printf("%lld\n", ret);
    }
    return 0;
}
/*
1
5231711 13073137
*/
Read More +
解題區/解題區 - UVa

UVa 13057 - Prove Them All

Problem

這家公司有自動推論引擎，請問至少要證明幾個基礎定理後，剩餘的都可以藉由推論引擎得到？

Sample Input

1
2
3
4
5
6
1
4  4
1  2
1  3
4  2
4  3

Sample Output

1
Case 1: 2

Solution

把這張圖的所有 SCC 元件全部縮成一點，變成 DAG 後，計算有幾個節點的 indegree 等於零，其零的個數就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
// similar as UVa 11504 - Dominos 
// algorithm: SCC
const int MAXN = 32767;
class SCC {
public:
    int n;
    vector<int> g[MAXN], dag[MAXN];
    // <SCC begin>
    int vfind[MAXN], findIdx;
    int stk[MAXN], stkIdx;
    int in_stk[MAXN], visited[MAXN];
    int contract[MAXN];
    int scc_cnt;
    // <SCC end>
    int scc(int u) {
        in_stk[u] = visited[u] = 1;
        stk[++stkIdx] = u, vfind[u] = ++findIdx;
        int mn = vfind[u], v;
        for(int i = 0; i < g[u].size(); i++) {
        	v = g[u][i];
            if(!visited[v])
                mn = min(mn, scc(v));
            if(in_stk[v])
                mn = min(mn, vfind[v]);
        }
        if(mn == vfind[u]) {
            do {
                in_stk[stk[stkIdx]] = 0;
                contract[stk[stkIdx]] = scc_cnt;
            } while(stk[stkIdx--] != u);
            scc_cnt++;
        }
        return mn;
    }
    void addEdge(int u, int v) { // u -> v
        g[u].push_back(v);
    }
    void solve() {
        for (int i = 0; i < n; i++)
            visited[i] = in_stk[i] = 0;
        scc_cnt = 0;
        for (int i = 0; i < n; i++) {
        	if (visited[i])	continue;
        	stkIdx = findIdx = 0;
        	scc(i);
        }
    }
    void make_DAG() {
        int x, y;
        for (int i = 0; i < n; i++) {
            x = contract[i];
            for (int j = 0; j < g[i].size(); j++) {
                y = contract[g[i][j]];
                if (x != y)
                    dag[x].push_back(y);
            }
        }
        for (int i = 0; i < scc_cnt; i++) {
            sort(dag[i].begin(), dag[i].end());
            dag[i].resize(unique(dag[i].begin(), dag[i].end()) - dag[i].begin());
        }
    }
    void init(int n) {
        this->n = n;
        for (int i = 0; i < n; i++)
            g[i].clear(), dag[i].clear();
    }
} g;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, m, u, v;
        scanf("%d %d", &n, &m);
        g.init(n);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            u--, v--;
            g.addEdge(u, v);
        }
        g.solve();
        g.make_DAG();
        
        int indeg[MAXN] = {}, ret = 0;
        for (int i = 0; i < g.scc_cnt; i++) {
            for (auto &e : g.dag[i]) {
                indeg[e]++;
            }
        }
        for (int i = 0; i < g.scc_cnt; i++)
            ret += indeg[i] == 0;
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13015 - Promotions

Problem

有 $N$ 名員工，他們彼此之間會推薦、相互提拔對方，因此站在公司的角度來看，提拔順序不能違反這張圖的上下關係，亦即若要提拔某人，其推薦他的人全部都要被提拔。請問若要提拔 $A$ 個人，有哪些人一定會被提拔，同樣的，回答提拔 $B$ 個人的情況，最後回答，若提拔 $B$ 個人，誰一定不會被提拔？

Sample Input

1
2
3
4
5
6
7
8
9
3  4  7  8
0  4
1  2
1  5
5  2
6  4
0  1
2  3
4  5

Sample Output

1
2
3
2
4
3

Solution

一定是張 DAG，否則不能處理。對於輸入多存一張反向圖，接著每一次都去找其下屬節點有多少個，藉此構造出任何提拔方案中，最好和最差排名為多少。處理全部排名計算 $\mathcal{O}(V^2 E)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
// O(VE)
const int MAXN = 5005;
int A, B, E, P;
vector<int> G[MAXN], invG[MAXN];
int used[MAXN] = {}, cases = 0;
int dfs(int u, vector<int> g[]) {
    if (used[u] == cases)	return 0;
    used[u] = cases;
    int ret = 1;
    for (auto v : g[u])
        ret += dfs(v, g);
    return ret;
}
int main() {
    int x, y;
    while (scanf("%d %d %d %d", &A, &B, &E, &P) == 4) {
        for (int i = 0; i < E; i++)
            G[i].clear(), invG[i].clear();
        // Must DAG
        for (int i = 0; i < P; i++) {
            scanf("%d %d", &x, &y);
            G[x].push_back(y), invG[y].push_back(x);
        }
        
        int retA = 0, retB = 0, retN = 0;
        for (int i = 0; i < E; i++) {
            int worst, best;
            cases++;
            worst = E - dfs(i, G) + 1;
            cases++;
            best = dfs(i, invG);
            if (worst <= A)	retA++;
            if (worst <= B)	retB++;
            if (best > B)	retN++;
        }
        printf("%d\n%d\n%d\n", retA, retB, retN);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13024 - Saint John Festival

Problem

給予 $N$ 個大天燈的所在位置，隨後有 $Q$ 個小天燈位置，施放天燈後，請問有多少小天燈處於任三個天燈構成的三角形內部？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
8
3  4
2  8
5  4
1  8
4  7
3  10
11  2
7  3
6
5  12
3  7
3  3
4  5
0  4
2  6

Sample Output

1
3

Solution

由於只詢問任意三個點構成的三角形內部，貪心就能想到一定是挑選凸包上的三點，只需要判定某點是不是在凸包內部，由於所有天燈已經給定，只需要跑一次 $\mathcal{O}(N \log N)$ 凸包算法，接著詢問一點是否在凸包內，只需要 $\mathcal{O}(\log N)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <algorithm>
using namespace std;
#define eps 1e-10
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if (fabs(x-a.x) > eps)	return x < a.x;
        return y < a.y;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for (i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for (i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m-1;
}
double g(Pt a, Pt b, double x) {
    Pt vab = b - a;
    return a.y + vab.y * (x - a.x) / vab.x;
}
int inside_convex(const Pt &p, Pt ch[], int n) {
    if (n < 3)
        return false;
    if (cross(ch[0], p, ch[1]) > eps)
        return false;
    if (cross(ch[0], p, ch[n-1]) < -eps)
        return false;
    
    int l = 2, r = n-1;
    int line = -1;
    while (l <= r) {
        int mid = (l + r)>>1;
        if (cross(ch[0],p, ch[mid]) > -eps) {
            line = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return cross(ch[line-1], p, ch[line]) < eps;
}
Pt D[131072], ch[262144];
int main() {
    int testcase, n, m;
    double x, y;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x, &y);
            D[i] = Pt(x, y);
        }
        n = monotone(n, D, ch);
        scanf("%d", &m);
        int ret = 0;
        for (int i = 0; i < m; i++) {
            scanf("%lf %lf", &x, &y);
            int f = inside_convex(Pt(x, y), ch, n);
            ret += f;
        }        
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13029 - Emoticons

Problem

給一個由 ^, _ 構成的字串，請湊出最多的 ^_^ 子字串。

Sample Input

1
2
3
4
5
6
5
_^^_^^_
^__^__^
______
^^__^^
^_^^_^

Sample Output

1
2
3
4
5
Case 1: 1
Case 2: 1
Case 3: 0
Case 4: 2
Case 5: 2

Solution

從左掃瞄到右邊，貪心著手容易得到兩種狀態

  • $h1$: ^ 的個數。
  • $h2$: 湊成 ^???_ 的個數，可以從 $h1$ 合併 _ 構成。

然而有一些特殊案例 ^_^_^^，需要重新排列，他們之間有巢狀關係 (^_(^_^)^)，因此建立狀態 $h3$ 為 ^_^???_，若遇到下一個 ^ 貪心拆解成 (^_(^_^)???)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
char s[131072];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", s);
        int n = strlen(s);
        int ret = 0;
        int h1 = 0, h2 = 0, h3 = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '^' && h2) {
                h2--, ret++;
            } else if (s[i] == '^') {
                if (h3 && ret)
                    h2++, h3--;
                else
                    h1++;
            } else if (s[i] == '_' && h1) {
                h1--, h2++;
            } else if (s[i] == '_') {
                if (ret > h3)
                    h3++;
            }
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13017 - Canvas Painting

Problem

有 $N$ 塊畫布排成一列，並且目標將每一塊畫布變成不同顏色，每一次可以將一個區間塗成相同顏色，花費便是區間 $C_i$ 總和，請問最少花費為何。

Sample Input

1
2
3
4
5
2
3
7  4  7
4
5  3  7  5

Sample Output

1
2
29
40

Solution

每一次最多完成一個不同顏色的畫布，那麼著色解法看來就是二元樹，每一個畫布處於葉節點，因此最少花費就相當於編碼長度乘上葉權重最少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
// Huffman Coding, Greedy
// input A[1...n]
// minimum \sum A[i]*code[i]
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, x;
        long long t;
        multiset<long long> S;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &x), S.insert(x);
            
        long long ret = 0;
        for (int i = n-2; i >= 0; i--) {
            long long a, b;
            a = *S.begin();
            S.erase(S.begin());
            b = *S.begin();
            S.erase(S.begin());
            ret += a+b;
            S.insert(a+b);
        }
        printf("%lld\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13079 - On the beach

Problem

在炎炎夏日的海邊，需要建立地下通道，把所有海岸飯店聯通在一起，請問最少地下通道個數為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
4
1  4
6  15
2  10
12  20
2
1  4
4  8
2
1  4
3  8
0

Sample Output

1
2
3
2
2
1

Solution

把這些區間排序，根據左端點由小到大開始貪心，可行解若看成一個區間，隨著區間加入，右端點會逐漸地靠近左端點，若產生無解，勢必要建立一個新通道。不斷地貪心，最後可得到最少通道個數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    while (scanf("%d", &N) == 1 && N) {
        vector<pair<int, int>> A;
        int L, R;
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &L, &R);
            A.push_back(make_pair(L, R));
        }
        sort(A.begin(), A.end());
        
        int ret = 0;
        int PQ = INT_MAX;
        for (int i = 0; i < N; i++) {
            int line_x = A[i].first;
            if (PQ != INT_MAX && PQ <= line_x) {
                ret++;
                PQ = INT_MAX;
            }
            PQ = min(PQ, A[i].second);
        }
        if (PQ != INT_MAX)
            ret++;
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

批改娘 10038. Fast Covering Problem

題目背景

終於把所有練習題都放上 Judge Girl，測資都已經確認過一遍，某 M 打算離開一陣子。「反正是個令人唾棄的助教吧 …」

題目描述

考試出題總很難讓所有人滿意，老師決定給予學生們選擇考試出題方向，但每一個人只能提出兩種意見，接著老師會出一套方案滿足每一位學生的其中一種意見。由於出一套題步驟繁瑣，把數個意見出在同一題非常困難，最後每一種意見將單獨被出成一道題。

由於助教們要負責出測資、檢驗測資正確與可行性，希望題目數量越少越好，否則助教會忙翻天。現在要找到最少題目來滿足所有學生的需求。

例如 :

  • 現在有 4 名學生的意見
  • 四名學生分別提案 $(0, 1), (100, 1), (100, 0), (100, 200)$
  • 如果選擇 ${ 0, 100 }$ 或者是 ${ 1, 100 }$ 都是最好的選擇，助教只需要完成 2 題的檢驗。相反地，如果 ${0, 100, 200 }$ 雖然可以滿足所有學生，但需要出成 3 道題目。

輸入格式

只有一組測資，每組第一行會有一個整數 $N$，表示有多少位學生，接下來會有 $N$ 行，每 $i$ 行上會有兩個整數 $A_i, B_i$ 表示第 $i$ 個學生的出題意見。

  • $0 < N \le 1000$
  • $0 \le A_i, \; B_i \le 10000$
  • 意見類型總數不超過 100 種

輸出格式

對於每一組測資輸出一行，表示最少要準備的方案數量能滿足所有學生。

範例輸入

1
2
3
4
5
4
0 1
100 1
100 0
100 200

範例輸出

1
2

提示

DLX

Solution

當年在 NCPC 搞不出來的 Problem I Christmas Gifts (NP-hard)，在賽後用 DLX 運行效果不錯，在啟發函數加上延遲標記更是屹立排名前數位已久。最近又因為平行把題目挖回來討論，在去年釣到大一學弟來解，便以飛快的速度擊破測資，最後達到加速 20x。再把當初需要跑 30 秒的測資來運行，現在只需要短短的 50ms。

原本要拿來出平行題目，看到這麼驚人的速度，想必就不要出題。

通用解法 DLX 加上啟發式函數就能解決最少重複覆蓋，然而在圖論的最少點集覆蓋問題中，性質又變得更加強烈。當不選某一個點時，必然與其相連的邊為了要覆蓋，另一端必然成為必選點。這時候搜索空間大幅度地下降。若在一般 DLX 算法中提及的最少可能的列中，窮舉某行來覆蓋一些列，那麼就很難看到搜索空間下降的性質。

因此，步驟簡單分成下列步驟：

  1. 將圖轉換成某行可以覆蓋哪幾列，轉換成 Dancing Links 的格式
  2. 找到可以覆蓋最多尚未覆蓋列最多的那一行
    1. 選擇這一行，並且移除這一行所有覆蓋列，遞迴窮舉。
    2. 移除這一行，選擇必選行，並嘗試移除等價行。

附錄：和交通大學謝旻錚(Min-Zheng Shieh) 教練的討論

在想確實能用 dancing links 來搞，還要搭配維護 degree order，不過這算法吳邦一老師是說 worst case 為 3 regular graph。
另外先前找過日本人 iwi 的論文，他也搞了個高級 VC solver 並做了測試，詳見論文 Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover, Takuya Akiba, Yoichi Iwata 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#define MAXNODE 100000
#define MAXCOL 5005
#define MAXN 5005
struct DancingNode {
    int left, right, up, down;
    int ch, rh;
} DL[MAXNODE];
struct HelperNode {
    int head, size, next, prev;
} HN[MAXNODE];
int help_head;
int s[MAXCOL];
int head, size, Ans, Dep;
int markStk[MAXNODE], markIdx = -1;
void Remove(int c) {
    for (int i = DL[c].down; i != c; i = DL[i].down) {
    	if (HN[DL[i].rh].head == i)
    		HN[DL[i].rh].head = DL[i].left;
    	HN[DL[i].rh].size--;
        DL[DL[i].right].left = DL[i].left;
        DL[DL[i].left].right = DL[i].right;
        s[DL[i].ch]--;
    }
}
void Resume(int c) {
    for (int i = DL[c].down; i != c; i = DL[i].down) {
    	if (HN[DL[i].rh].head == i)
    		HN[DL[i].rh].head = DL[i].right;
    	HN[DL[i].rh].size++;
        DL[DL[i].right].left = i;
        DL[DL[i].left].right = i;
        s[DL[i].ch]++;
    }
}
void Reduce(int i) {
    int t = DL[i].rh;
    HN[HN[t].next].prev = HN[t].prev;
    HN[HN[t].prev].next = HN[t].next;
    s[DL[i].ch]--;
    DL[DL[i].down].up = DL[i].up;
    DL[DL[i].up].down = DL[i].down;
    for (int k = DL[i].right; k != i; k = DL[k].right) {
        DL[DL[k].down].up = DL[k].up;
        DL[DL[k].up].down = DL[k].down;
        s[DL[k].ch]--;
    }
}
void Recover(int i) {
    int t = DL[i].rh;
    HN[HN[t].next].prev = t;
    HN[HN[t].prev].next = t;
    s[DL[i].ch]++;
    DL[DL[i].down].up = i;
    DL[DL[i].up].down = i;
    for (int k = DL[i].right; k != i; k = DL[k].right) {
        DL[DL[k].down].up = k;
        DL[DL[k].up].down = k;
        s[DL[k].ch]++;
    }
}
void Select(int i) {
    int s = DL[i].rh;
    HN[HN[s].next].prev = HN[s].prev;
    HN[HN[s].prev].next = HN[s].next;
    Remove(i);
    for (int j = DL[i].right; j != i; j = DL[j].right)
        Remove(j);
    Dep++;
}
void Cancel(int i) {
    int s = DL[i].rh;
    for (int j = DL[i].right; j != i; j = DL[j].right)
        Resume(j);
    Resume(i);    
    HN[HN[s].next].prev = s;
    HN[HN[s].prev].next = s;
    Dep--;
}
int Decision() {
    int has = 0;
    for (int i = DL[head].right; i != head; i = DL[i].right) {
        if (s[i] == 1) {
            Select(DL[i].down);
            markStk[++markIdx] = DL[i].down;
            has = 1;
        }
    }
    return has;
}
int Subset(int x, int y) {	// 0: x in y, 1: y in x 
    assert(DL[x].ch == DL[y].ch);
    int a = 0, b = 0;
    int i, j;
    for (i = DL[x].right, j = DL[y].right; i != x && j != y; ) {
        if (DL[i].ch == DL[j].ch)
            i = DL[i].right, j = DL[j].right;
        else if (DL[i].ch < DL[j].ch)
            i = DL[i].right, a = 1;
        else
            j = DL[j].right, b = 1;
        if (a && b)
            break;
    }
    if (i != x)    a = 1;
    if (j != y)    b = 1;
    return a || b ? (a - b) : 1;
}
int Duplicate() {
    int has = 0;
    for (int i = DL[head].right; i != head; i = DL[i].right) {
        for (int j = DL[i].down; j != i; j = DL[j].down) {
            for (int k = DL[j].down; k != j && k != i; k = DL[k].down) {
                int cmp = Subset(j, k);
                if (cmp == 0)
                    continue;
                if (cmp == 1) {
                	markStk[++markIdx] = j;
                	Select(j);
            	} else {
            		markStk[++markIdx] = k;
                	Select(k);
                }
                has = 1;
            }
        }
    }
    return has;
}
int H(int limit) {
    static int c, ret, i, j, time = 0;
    static int used[MAXCOL] = {};
    for (c = DL[head].right, ++time, ret = 0; c != head; c = DL[c].right) {
        if (used[c] == time)
        	continue;
    	ret ++, used[c] = time;
    	if (ret >= limit)	return ret;
        for (i = DL[c].down; i != c; i = DL[i].down) {
            for (j = DL[i].right; j != i; j = DL[j].right)
            	used[DL[j].ch] = time;
        }
    }
    return ret;
}
void DFS() {
    int hval = H(Ans - Dep);
    if (DL[head].right == head && Dep < Ans)
    	Ans = Dep;
    if (Dep + hval >= Ans)
        return ;
    int cover_max = -1, cover_idx = -1;
    for (int i = HN[help_head].next; i != help_head; i = HN[i].next) {
        if (HN[i].size > cover_max) {
            cover_max = HN[i].size;
            cover_idx = HN[i].head;
        }
    }
    
    Select(cover_idx);
    DFS();
    Cancel(cover_idx);
    
    Reduce(cover_idx);
    int markEsp = markIdx;
    while (!Decision() && !Duplicate());
    DFS();
    while (markIdx > markEsp)
        Cancel(markStk[markIdx--]);
    Recover(cover_idx);
}
int new_node(int up, int down, int left, int right) {
    DL[size].up = up, DL[size].down = down;
    DL[size].left = left, DL[size].right = right;
    DL[up].down = DL[down].up = DL[left].right = DL[right].left = size;
    return size++;
}
void new_row(int n, int Row[], int rh) {
    int r, row = -1, k;
    int h = size;
    for (int i = 0; i < n; i++) {
        r = Row[i];
        DL[size].ch = r, s[r]++;
        DL[size].rh = rh;
        if (row == -1) {
            row = new_node(DL[DL[r].ch].up, DL[r].ch, size, size);
        } else {
            k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
        }
    }
    HN[rh].size = n;
    HN[rh].head = h;
    HN[rh].next = HN[help_head].next;
    HN[rh].prev = help_head;
    HN[HN[help_head].next].prev = rh;
    HN[help_head].next = rh;
}
void init(int m) {
    size = 0;
    help_head = 0, HN[help_head].next = HN[help_head].prev = help_head;
    head = new_node(0, 0, 0, 0);
    int i;
    for (i = 1; i <= m; i++) {
        new_node(i, i, DL[head].left, head);
        DL[i].ch = i, s[i] = 0;
        DL[i].rh = 0;	// important pointer (fail pointer)
    }
}
int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
    	int A[MAXN], B[MAXN];
        int toy[10005] = {}, R[MAXCOL];
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &A[i], &B[i]);
            toy[A[i]]++, toy[B[i]]++;
        }
        
        init(n);
        int run_id = 0;
        for (int i = 0; i <= 10000; i++) {
            int nt = 0;
            for (int j = 1; j <= n; j++) {
                if (A[j] == i || B[j] == i)
                    R[nt++] = j;
            }
            if (nt) {
                run_id++;
                new_row(nt, R, run_id);
            }
        }
        Ans = n;
        Dep = 0, markIdx = -1;
        Decision();
        DFS();
        printf("%d\n", Ans);
        fflush(stdout);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13009 - Fence the vegetables fail

Problem

給一個平行兩軸的簡單多邊形花圃以及一堆蔬菜的座標，請問有多少蔬菜在柵欄的外部，把那些在外部的蔬菜編號加總後輸出。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
4 8
1 2
1 0
5 3
3 4
0 1
6 1
6 4
4 4
4 3
2 3
2 5
0 5
6 12
6 5
1 9
3 6
3 4
2 0
4 4
5 8
5 3
2 3
2 5
4 5
4 7
0 7
0 1
7 1
7 10
0 10
0 8
1 4
1 1
2 0
2 2
0 2
0 0

Sample Output

1
2
3
6
15
0

Solution

判斷一個點是否在簡單多邊形內部可以使用射線法，然而有很多點詢問，單筆詢問複雜度 $\mathcal{O}(N)$，這樣很明顯地會 TLE。

為了加速判斷，採用掃描線算法，依序放入平行 x 軸的線段，掃描過程中離線詢問某點往 y 軸負方向的射線交點個數為何，維護求交點個數可以利用 binary indexed tree 維護前綴和，前綴和相當於射線交點個數。就能在 $\mathcal{O}(N \log N)$ 完成所有詢問。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <math.h>
using namespace std;
struct Pt {
    int x, y, v;
    Pt(int a = 0, int b = 0):
    x(a), y(b) {}
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator<(const Pt &a) const {
        if (x != a.x)
            return x < a.x;
        if (y != a.y)
            return y < a.y;
        return false;
    }
};
struct Seg {
    int xl, xr, y;
    Seg(int a = 0, int b = 0, int c = 0):
    xl(a), xr(b), y(c) {}
    bool operator<(const Seg &u) const {
        return xl < u.xl;
    }
};
Pt P[131072], D[131072];
int BIT[262144];
void modify(int x, int val, int L) {
    while (x <= L)
        BIT[x] += val, x += x&(-x);
}
int query(int x) {
    int sum = 0;
    while (x)
        sum += BIT[x], x -= x&(-x);
    return sum;
}
void solve(int N, int M) {
    map<int, int> RX, RY;
    for (int i = 0; i < N; i++)
        RX[P[i].x] = RY[P[i].y] = 0;
    for (int i = 0; i < M; i++)
        RX[D[i].x] = RY[D[i].y] = 0;
    
    int label_x = 0, label_y = 0;
    
    for (auto &x : RX)
        x.second = ++label_x;
    for (auto &y : RY)
        y.second = ++label_y;
    
    memset(BIT, 0, sizeof(BIT));
    
    for (int i = 0; i < N; i++)
        P[i].x = RX[P[i].x], P[i].y = RY[P[i].y];
    for (int i = 0; i < M; i++)
        D[i].x = RX[D[i].x], D[i].y = RY[D[i].y];
    
    vector<Seg> segs;
    for (int i = 0; i < M; i++) {
        if (D[i].y == D[(i+1)%M].y) {
            int xl = min(D[i].x, D[(i+1)%M].x);
            int xr = max(D[i].x, D[(i+1)%M].x);
            segs.push_back(Seg(xl, xr, D[i].y));
        }
    }
    
    long long outer_val = 0;
    sort(P, P+N);
    sort(segs.begin(), segs.end());
    int Pidx = 0;
    set<std::pair<int, int>> PQ;
    for (int i = 0, line_x = 1; line_x <= label_x; line_x++) {
        while (Pidx < N && P[Pidx].x <= line_x) {
            int intersect = query(P[Pidx].y);
            if (intersect%2 == 0)
                outer_val += P[Pidx].v;
            Pidx++;
        }
        while (!PQ.empty() && PQ.begin()->first <= line_x)
            modify(PQ.begin()->second, -1, label_y), PQ.erase(PQ.begin());
        while (i < segs.size() && segs[i].xl == line_x) {
            modify(segs[i].y, 1, label_y);
            PQ.insert(make_pair(segs[i].xr, segs[i].y));
            i++;
        }
    }
    printf("%lld\n", outer_val);
}
int main() {
    int N, M;
    while (scanf("%d %d", &N, &M) == 2) {
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &P[i].x, &P[i].y);
            P[i].v = i+1;
        }
        
        for (int i = 0; i < M; i++)
            scanf("%d %d", &D[i].x, &D[i].y);
        
        solve(N, M);
    }
    return 0;
}
Read More +