解題區/解題區 - UVa

UVa 12245 - Hyperactive Girl

Problem

可用工作區間為 [1, m]，則要求分配 [li, ri] 的方式，找到所有可能的分配集合符合

  • 所有區間完全覆蓋住 [1, m] (區間可以重疊)
  • 每一個區間至少單獨佔有一個時間點

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
9 9
2 7
3 5
6 8
5 6
2 8
2 6
0 2
7 9
2 8
18 9
8 15
1 17
0 10
9 18
12 15
1 5
5 6
0 10
11 17
8 7
0 3
2 5
5 8
1 3
3 6
4 6
0 2
1 1
0 1
2 1
0 1
0 0

Sample Output

1
2
3
4
5
4
2
4
1
0

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <iostream>
#include <map>
using namespace std;
struct Interval {
    int l, r;
    bool operator<(const Interval &a) const {
        return l < a.l || (l == a.l && r < a.r);
    }
};
int main() {
    int n, m;
    const int mod = 100000000;
    Interval D[128];
    while(scanf("%d %d", &m, &n) == 2 && n+m) {
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &D[i].l, &D[i].r);
        }
        sort(D, D+n);
        int dp[128][128] = {}; // [prev][now]
        int ret = 0;
        for (int i = 0; i < n; i++) {
            dp[i][i] = (D[i].l == 0);
            for (int j = i+1; j < n; j++) {
                if (D[j].l > D[i].l && D[j].r > D[i].r && D[j].l <= D[i].r) {
                    for (int k = 0; k <= i; k++) {
                        if (D[k].r >= D[j].l && k != i)
                            continue;
                        dp[i][j] = (dp[i][j] + dp[k][i])%mod;
                    }
                }
            }
            if (D[i].r == m) {
                for (int j = 0; j <= i; j++)
                    ret = (ret + dp[j][i])%mod;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12182 - Toll Road

Problem

給定一棵有權重的樹圖，求其連通子圖權重最大為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
4
1 2 -7
3 2 10
2 4 2
5 4 -2
3
1 2 -8
2 3 -8
3 4 -1000
5
14 15 0
15 92 10
92 65 -5
65 35 10
35 89 -30
0

Sample Output

1
2
3
12
0
15

Solution

這一題跟最大連續和區間一樣，把無向樹弄成有根樹，接著採用 greedy 的方式，找到包含子節點的最大子樹總和。

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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <iostream>
#include <map>
using namespace std;
#define MAXN 262144
struct edge {
    int to, v;
    edge(int a = 0, int b = 0):
    to(a), v(b) {}
};
vector<edge> g[MAXN];
int dp[MAXN];
int used[MAXN];
void dfs(int u, int p) {
    used[u] = 1;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i].to, w = g[u][i].v;
        if(used[v])    continue;
        dfs(v, u);
    }
    
    int ret = 0;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i].to, w = g[u][i].v;
        if(v == p)    continue;
        if (dp[v] + w > 0) {
            ret += dp[v] + w;
        }
    }
    dp[u] = ret;
}
map<int, int> R;
int rename(int x) {
    int &ret = R[x];
    return ret == 0 ? ret = (int)R.size() : ret;
}
int main() {
    int n, x, y, v;
    while(scanf("%d", &n) == 1 && n) {
        for (int i = 1; i <= R.size(); i++)
            g[i].clear();
        R.clear();
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d", &x, &y, &v);
            x = rename(x), y = rename(y);
            g[x].push_back(edge(y, v));
            g[y].push_back(edge(x, v));
//            printf("-- %d %d %d\n", x, y, v);
        }
        
        n = (int)R.size();
        for (int i = 1; i <= n; i++)
            dp[i] = 0;
        for (int i = 1; i <= n; i++)
            used[i] = 0;
        for (int i = 1; i <= n; i++) {
            if (used[i] == 0) {
                dfs(i, -1);
            }
        }
        
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            ret = max(ret, dp[i]);
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
*/
Read More +
解題區/解題區 - UVa

UVa 12173 - White Water Rafting

Problem

給滑水道兩邊緣座標，求最大半徑的圓可以再滑水道之間穿越。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
4
-5 -5
5 -5
5 5
-5 5
4
-10 -10
-10 10
10 10
10 -10
3
0 0
1 0
1 1
5
3 -3
3 3
-4 2
-1 -1
-2 -2

Sample Output

1
2
2.50000000
0.70710678

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
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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
using namespace std;
#define eps 1e-6
struct Pt {
    int x, y;
    Pt(int a = 0, int 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;
    }
    Pt operator-(const Pt &a) const {
        Pt ret;
        ret.x = x - a.x;
        ret.y = y - a.y;
        return ret;
    }
};
enum LINE_TYPE {LINE, SEGMENT};
struct LINE2D {
    Pt s, e;
    LINE_TYPE type;
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
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 between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
       cross(at, as, bs) * cross(at, as, bt) < 0 &&
       cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
       cross(bt, bs, as) * cross(bt, bs, at) < 0)
        return 1;
    return 0;
}
double distProjection(Pt as, Pt at, Pt s) {
    int a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
double dist2Seg(Pt sa, Pt sb, Pt p) {
    double c = 1e+30;
    if(between(sa, sb, p))
        c = min(c, distProjection(sa, sb, p));
    else
        c = min(c, min(dist(sa, p), dist(sb, p)));
    return c;
}
int main() {
    int testcase;
    int n, m;
    Pt Di[128], Do[128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d %d", &Di[i].x, &Di[i].y);
        scanf("%d", &m);
        for (int i = 0; i < m; i++)
            scanf("%d %d", &Do[i].x, &Do[i].y);
        
        double ret = 1e+30;
        Di[n] = Di[0], Do[m] = Do[0];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ret = min(ret, dist2Seg(Di[i], Di[i+1], Do[j]));
                ret = min(ret, dist2Seg(Do[j], Do[j+1], Di[i]));
            }
        }
        printf("%.8lf\n", ret/2);
    }
    return 0;
}
/*
 2
 4
 -5 -5
 5 -5
 5 5
 -5 5
 4
 -10 -10
 -10 10
 10 10
 10 -10
 3
 0 0
 1 0
 1 1
 5
 3 -3
 3 3
 -4 2
 -1 -1
 -2 -2
 */
Read More +
解題區/解題區 - UVa

UVa 12134 - Find the Format String

Problem

給指定的輸入和輸出，找到一個正規表達的方式符合預期的 scanf(format, args);

Sample Input

1
2
3
4
5
6
7
8
9
5
"11" "11"
"243" "24"
"563" "56"
"784" "784"
"789" "78"
1
"A" "b" 
0

Sample Output

1
2
Case 1: [01245678]
Case 2: I_AM_UNDONE

Solution

其實這一題只是單純的切割字符串，但是要記住 scanf 的 format 是中 scanf("%[exp]", &str) 來說，exp 只填入塞選字符，不涵蓋其他的運算子，則會掃描到空白前且不存在 exp 中的字符為一個 token。 // 記住：直到第一個不符合條件的地方做切割。

接著要處理最小字典順序的問題，因此要對於非必要的塞選也要填入。

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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int main() {
    int n, cases = 0;
    char in[128][128], out[128][128];
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            scanf("%s %s", in[i], out[i]);
        
        int ascii[128] = {};
        for (int i = '0'; i <= '9'; i++)
            ascii[i] = 1;
        for (int i = 'A'; i <= 'Z'; i++)
            ascii[i] = 1;
        for (int i = 'a'; i <= 'z'; i++)
            ascii[i] = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; out[i][j]; j++) {
                if (in[i][j] != out[i][j]) {
                    ascii[in[i][j]] = 0;
                } else {
                    if (ascii[in[i][j]]) {
                        ascii[in[i][j]] |= 2;
                    }
                }
            }
        }
        
        char ret[128];
        int m = 0;
        for (int i = '0', j = '0' - 1; i < 128; i++) {
//            printf("%d %d\n", i, ascii[i]);
            if (ascii[i] == 3) {
                while (j < i) {
                    if (ascii[j] == 1)
                        ret[m++] = j;
                    j++;
                }
                ret[m++] = i;
            }
        }
        if (m == 0) {
            for (int i = '0'; i < 128; i++) {
                if (ascii[i] == 1) {
                    ret[m++] = i;
                    break;
                }
            }
        }
        ret[m] = '\0';
        char format[128];
        format[0] = '%', format[1] = '[';
        for (int i = 0; i < m; i++)
            format[i+2] = ret[i];
        format[m+2] = ']', format[m+3] = '\0';
        int ok = 1;
        if (m == 0)
            ok = 0;
        for (int i = 0; i < n && ok; i++) {
            char s[128] = {};
            in[i][strlen(in[i]) - 1] = '\0';
            sscanf(in[i]+1, format, s + 1);
            s[0] = '"';
            int len = (int)strlen(s);
            s[len] = '"', s[len+1] = '\0';
            ok &= !strcmp(s, out[i]);
        }
        printf("Case %d: %s\n", ++cases, ok ? format+1 : "I_AM_UNDONE");
    }
    return 0;
}
/*
 5
 "11" "11"
 "243" "24"
 "563" "56"
 "784" "784"
 "789" "78"
 1
 "A" "b" 
 0
 */
Read More +
解題區/解題區 - UVa

UVa 12118 - Inspector's Dilemma

Problem

將一個無向圖中，增加最少條邊，使得可以使用尤拉路徑或環道經過所有條邊。

Sample Input

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

Sample Output

1
2
Case 1: 4
Case 2: 4

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
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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int parent[1024], weight[1024];
int deg[1024];
int findp(int x) {
    return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y)
        return 0;
    if (weight[x] > weight[y])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
int main() {
    int cases = 0;
    int N, M, T, x, y;
    while (scanf("%d %d %d", &N, &M, &T) == 3 && N+M+T) {
        for (int i = 1; i <= N; i++)
            parent[i] = i, weight[i] = 1, deg[i] = 0;
        
        int component = N;
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &x, &y);
            deg[x]++, deg[y]++;
            if (joint(x, y))
                component--;
        }
        
        for (int i = 1; i <= N; i++) {
            if (weight[i] == 1 && findp(i) == i)
                component--;
        }
        int ret = M, odd[1024] = {};
        ret += component > 0 ? component - 1 : 0;
        for (int i = 1; i <= N; i++) {
            if (deg[i]&1)
                odd[findp(i)]++;
        }
        for (int i = 1; i <= N; i++) {
            if (odd[i] >= 4)
                ret += odd[i]/2 - 1;
        }
        printf("Case %d: %d\n", ++cases, ret * T);
    }
    return 0;
}
/*
 5 3 1
 1 2
 1 3
 4 5
 
 4 4 1
 1 2
 1 4
 2 3
 3 4
 0 0 0
 */
Read More +
解題區/解題區 - UVa

UVa 12096 - The SetStack Computer

Problem

將集合做交集、聯集、插入的操作，輸出每次操作的集合大小。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
9
PUSH
DUP
ADD
PUSH
ADD
DUP
ADD
DUP
UNION
5
PUSH
PUSH
ADD
PUSH
INTERSECT

Sample Output

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

Solution

STL 高招解決，都有提供集合交集和聯集，但是為了方便查找，使用重新命名每一個集合為一個整數表示。

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
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
#include <map>
using namespace std;
map< set<int>, int > R;
map<int, set<int> > mR;
int rename(set<int> s) {
    int &ret = R[s];
    if (ret == 0)
        ret = (int)R.size(), mR[ret] = s;
    return ret;
}
int main() {
    int testcase, n;
    int a, b;
    char cmd[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        stack<int> stk;
        for (int i = 0; i < n; i++) {
            scanf("%s", cmd);
            if (!strcmp(cmd, "PUSH")) {
                stk.push(rename(set<int>()));
            } else if(!strcmp(cmd, "DUP")) {
                stk.push(stk.top());
            } else if(!strcmp(cmd, "UNION")) {
                a = stk.top(), stk.pop();
                b = stk.top(), stk.pop();
                set<int> &A = mR[a], &B = mR[b], C;
                set_union(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin()));
                stk.push(rename(C));
            } else if(!strcmp(cmd, "INTERSECT")) {
                a = stk.top(), stk.pop();
                b = stk.top(), stk.pop();
                set<int> &A = mR[a], &B = mR[b], C;
                set_intersection(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin()));
                stk.push(rename(C));
            } else if(!strcmp(cmd, "ADD")) {
                a = stk.top(), stk.pop();
                b = stk.top(), stk.pop();
                set<int> B = mR[b];
                B.insert(a);
                stk.push(rename(B));
            }
            printf("%d\n", (int)mR[stk.top()].size());
        }
        puts("***");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12092 - Paint the Roads

Problem

給一張無向圖，希望每一個點都剛好在 K 個不相交環上，如果不可能則輸出 -1，反之挑選最少花費的邊構成這一個條件。

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
4
4 8 1
0 1 1
1 0 2
2 3 1
3 2 2
0 2 5
2 0 6
1 3 5
3 1 6
4 8 1
0 1 1
1 0 10
2 3 10
3 2 1
0 2 10
2 0 1
1 3 1
3 1 10
4 8 2
0 1 1
1 0 2
2 3 1
3 2 2
0 2 5
2 0 6
1 3 5
3 1 6
3 4 1
0 1 5
1 0 6
0 2 7
2 0 8

Sample Output

1
2
3
4
6
4
28
-1

Solution

一道明顯的最小費用流，每一條邊最高流量是 1，而對於每個點都通過 K 個不相交環 (沒有共同邊)，則要將每個點拆分成出入兩點，也就是說總共會有 N K 個不相交的環，總流量會經過 N K 條邊。

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
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXN 128
struct Node {
    int x, y, cap, cost;// x->y, v
    int next;
} edge[100005];
int e, head[MAXN], dis[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
void addEdge(int x, int y, int cap, int cost) {
    edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
    edge[e].next = head[y], head[y] = e++;
}
int mincost(int s, int t, int &totflow) {
    totflow = 0;
    int mncost = 0, flow;
    int i, x, y;
    while(1) {
        memset(dis, 63, sizeof(dis));
        int oo = dis[0];
        dis[s] = 0;
        deque<int> Q;
        Q.push_front(s);
        while(!Q.empty()) {
            x = Q.front(), Q.pop_front();
            inq[x] = 0;
            for(i = head[x]; i != -1; i = edge[i].next) {
                y = edge[i].y;
                if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                    dis[y] = dis[x] + edge[i].cost;
                    pre[y] = x, record[y] = i;
                    if(inq[y] == 0) {
                        inq[y] = 1;
                        if(Q.size() && dis[Q.front()] > dis[y])
                            Q.push_front(y);
                        else
                            Q.push_back(y);
                    }
                }
            }
        }
        if(dis[t] == oo)
            break;
        flow = oo;
        for(x = t; x != s; x = pre[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for(x = t; x != s; x = pre[x]) {
            int ri = record[x];
            edge[ri].cap -= flow;
            edge[ri^1].cap += flow;
            edge[ri^1].cost = -edge[ri].cost;
        }
        totflow += flow;
        mncost += dis[t] * flow;
    }
    return mncost;
}
int main() {
    int testcase, N, M, K;
    int x, y, v;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &M, &K);
        e = 0;
        memset(head, -1, sizeof(head));
        int source = 2 * N, sink = 2 * N + 1;
        for (int i = 0; i < M; i++) {
            scanf("%d %d %d", &x, &y, &v);
            addEdge(2 * x, 2 * y + 1, 1, v);
        }
        
        for (int i = 0; i < N; i++) {
            addEdge(source, 2 * i, K, 0);
            addEdge(2 * i + 1, sink, K, 0);
        }
        int flow = 0;
        int cost = mincost(source, sink, flow);
        if (flow != N * K)
            puts("-1");
        else
            printf("%d\n", cost);
    }
    return 0;
}
/*
 4
 4 8 1
 0 1 1
 1 0 2
 2 3 1
 3 2 2
 0 2 5
 2 0 6
 1 3 5
 3 1 6
 
 4 8 1
 0 1 1
 1 0 10
 2 3 10
 3 2 1
 0 2 10
 2 0 1
 1 3 1
 3 1 10
 
 4 8 2
 0 1 1
 1 0 2
 2 3 1
 3 2 2
 0 2 5
 2 0 6
 1 3 5
 3 1 6
 
 3 4 1
 0 1 5
 1 0 6
 0 2 7
 2 0 8
 */
Read More +
解題區/解題區 - UVa

UVa 12048 - Inhabitants

Problem

給定一個凸包，詢問點是否在凸包內。

Sample Input

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

Sample Output

1
2
3
n
n
y

Solution

由於詢問次數相當多，必須將複雜度降到 O(log n)，採用的方式將凸包其中一個點當作基準，則如果在凸包的點而言，一定會落在某個以基點拉出的三角形內部中，為了方便計算，則可以拿外積的正負邊界上。

得到可能的三角形後，從邊界中可以藉由外積計算是否同側。

採用射線法 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
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
#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;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x, &y);
            ch[i] = Pt(x, y);
        }
//        n = monotone(n, D, ch);
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%lf %lf", &x, &y);
            int f = inside_convex(Pt(x, y), ch, n);
            puts(f ? "y" : "n");
        }
        
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12039 - Goldbach's Cardinality

Problem

求任兩個相異質數總和介於 [L, R] 之間的個數。

Sample Input

1
2
3
10 20
30 40
0 0

Sample Output

1
2
9
16

Solution

一開始使用 O(n log n) 的二分解法，但是遲遲沒有通過，最後改用 O(n) 的方式遞減 index。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxL (10000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
int P[1048576], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 10000000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
long long g(int n) {
    long long ret = 0;
    int pos = (int)(upper_bound(P+1, P+Pt, n) - (P+1));
    for (int i = 1; i < Pt && P[i] < n; i++) {
//        int pos = (int)(upper_bound(P+1, P+Pt, n - P[i]) - (P+1));
        while (pos > 0 && P[i] + P[pos] > n)
            pos--;
        if (pos >= i)
            ret--;
        ret += pos;
    }
    return ret/2;
}
int main() {
    sieve();
    int L, R;
    while (scanf("%d %d", &L, &R) == 2 && L+R) {
        R = R/2 * 2;
        L = (L-1)/2 * 2;
        printf("%lld\n", g(R) - g(L));
    }
    return 0;
}
/*
 10 20
 30 40
 0 0
 */
Read More +
解題區/解題區 - UVa

UVa 12035 - War Map

Problem

給每個節點的度 (degree)，是否能構成二分圖？

Sample Input

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

Sample Output

1
2
3
4
Case 1: NO
Case 2: YES
Case 3: NO
Case 4: YES

Solution

劃分成兩個集合，則兩邊的 degree 總和一定會相同，因此得到了基礎的窮舉概念。

然後對於窮舉的時候，左集合的元素最大值一定要小於等於右集合大小，反之亦然。
// s 和 t 集合, max(s[i]) <= |t|

這樣窮舉只能保證基礎的條件，而事實上採用 greedy 的驗證方式，從最大度的點開始分配連線給最大度的點，如果最後能分配完成即可找到一種二分圖的解。當然，有人嘗試了 maxflow 的驗證方式也是相當靠譜，不過速度會慢了些，而且還不是很容易 coding。

而這樣的解法仍然會拉 TLE 的緊抱，因此考慮將相同 degree 的窮舉方式壓縮，例如說有 3 個 2 需要窮舉，而採用兩個集合劃分的方式 (0, 3) (1, 2) (2, 1) (3, 0) 四種方式 …，從 2^3 = 8 降到 4 次，速度會快快快很多。

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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int n, m, A[32], B[32], totdeg;
pair<int, int> C[32];
int Ldeg[32], Rdeg[32];
int checkBipartite(int Ldeg[], int L, int Rdeg[], int R) {
    priority_queue<int> pQ;
    int x, cc = 0;
    for (int i = 0; i < R; i++)
        pQ.push(Rdeg[i]);
    for (int i = 0; i < L; i++)
        B[cc++] = Ldeg[i];
    sort(B, B+L, greater<int>());
    for (int i = 0; i < L; i++) {
        queue<int> Q;
        while (B[i] && !pQ.empty()) {
            B[i]--;
            x = pQ.top(), pQ.pop();
            x--;
            if (x)
                Q.push(x);
        }
        if (B[i])
            return 0;
        while (!Q.empty())
            pQ.push(Q.front()), Q.pop();
    }
    return pQ.empty();
}
int dfs(int idx, int lsize, int rsize, int ldeg, int rdeg, int lneed, int rneed) {
    if (ldeg > totdeg/2 || rdeg > totdeg/2)
        return 0;
    if (lneed + rneed > n || lsize + n - idx < lneed || rsize + n - idx < rneed)
        return 0;
    if (idx == m)
        return lsize >= lneed && rsize >= rneed && checkBipartite(Ldeg, lsize, Rdeg, rsize);
    for (int i = idx == 0; i <= C[idx].second; i++) {
        int l = i, r = C[idx].second - i, ln = lneed, rn = rneed;
        for (int j = 0; j < l; j++)
            Ldeg[lsize+j] = C[idx].first, rn = max(rn, C[idx].first);
        for (int j = 0; j < r; j++)
            Rdeg[rsize+j] = C[idx].first, ln = max(ln, C[idx].first);
        if (dfs(idx+1, lsize+l, rsize+r, ldeg+C[idx].first*l, rdeg+C[idx].first*r, ln, rn)) {
            return 1;
        }
    }
    return 0;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        totdeg = 0;
        for (int i = 0; i < n; i++)
            totdeg += A[i];
        sort(A, A+n, greater<int>());
        m = 0;
        C[m] = make_pair(A[0], 1), m++;
        for (int i = 1; i < n; i++) {
            if (A[i] == C[m-1].first)
                C[m-1].second++;
            else
                C[m] = make_pair(A[i], 1), m++;
        }
        int flag = totdeg%2 == 0 && dfs(0, 0, 0, 0, 0, 0, 0);
        printf("Case %d: %s\n", ++cases, flag ? "YES" : "NO");
    }
    return 0;
}

接近 TLE 的版本，概率通過得 AC。

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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int n, A[32], B[32], totdeg;
int Ldeg[32], Rdeg[32];
int checkBipartite(int Ldeg[], int L, int Rdeg[], int R) {
    priority_queue<int> pQ;
    int x, cc = 0;
    for (int i = 0; i < R; i++)
        pQ.push(Rdeg[i]);
    for (int i = 0; i < L; i++)
        B[cc++] = Ldeg[i];
    sort(B, B+L, greater<int>());
    for (int i = 0; i < L; i++) {
        queue<int> Q;
        while (B[i] && !pQ.empty()) {
            B[i]--;
            x = pQ.top(), pQ.pop();
            x--;
            if (x)
                Q.push(x);
        }
        if (B[i])
            return 0;
        while (!Q.empty())
            pQ.push(Q.front()), Q.pop();
    }
    return pQ.empty();
}
int dfs(int idx, int lsize, int rsize, int ldeg, int rdeg, int lneed, int rneed) {
    if (ldeg > totdeg/2 || rdeg > totdeg/2)
        return 0;
    if (lneed + rneed > n || lsize + n - idx < lneed || rsize + n - idx < rneed)
        return 0;
    if (idx == n)
        return lsize >= lneed && rsize >= rneed && checkBipartite(Ldeg, lsize, Rdeg, rsize);
    Ldeg[lsize] = A[idx];
    if (dfs(idx+1, lsize+1, rsize, ldeg+A[idx], rdeg, lneed, max(rneed, A[idx])))
        return 1;
    Rdeg[rsize] = A[idx];
    
    if (idx > 0) {
    if (dfs(idx+1, lsize, rsize+1, ldeg, rdeg+A[idx], max(lneed, A[idx]), rneed))
        return 1;
    }
    return 0;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        totdeg = 0;
        for (int i = 0; i < n; i++)
            totdeg += A[i];
        sort(A, A+n);
        int flag = totdeg%2 == 0 && dfs(0, 0, 0, 0, 0, 0, 0);
        printf("Case %d: %s\n", ++cases, flag ? "YES" : "NO");
    }
    return 0;
}
/*
 10000
 6
 3 0 2 2 3 0
 12
 0 0 0 0 0 0 0 0 0 0 0 0
 20
 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19
 4
 3 1 3 3
 5
 1 2 1 1 3
 4
 2 3 2 3
 7
 4 1 2 3 1 2 3
 */
Read More +