解題區/解題區 - UVa

UVa 12551 - Shares

Problem

現在要購買股票，每一個股票都有其花費和預期的在未來的出售價格。

但是股票採用組合包的方式進行販售，但是每一種組合包都只能購買一次，請問在資金只有 C 元的情況下，最多能在未來淨利多少。

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
39
40
41
42
43
44
45
46
47
48
49
50
500
4 6
10 15
8 6
20 15
12 12
3 1 6 2 7 3 8
3 3 8 1 10 2 4
3 4 10 2 5 1 10
2 1 4 2 4
1 3 2
2 4 3 2 1
200000000
5 30
2800 3500
1400 4800
2900 2800
500 3800
3300 4700
2 2 13 4 15
4 4 1 1 22 3 17 5 22
1 3 2
1 3 6
4 1 11 2 5 3 7 5 15
1 5 1
4 2 26 1 21 3 8 5 26
2 3 5 2 26
4 2 30 4 12 3 7 5 14
3 3 8 2 20 5 3
1 5 30
2 1 29 3 3
5 3 3 1 20 5 26 4 9 2 25
3 1 2 2 16 3 5
2 5 5 4 26
5 2 18 5 10 4 18 1 12 3 30
3 2 5 3 27 5 4
4 3 2 4 8 1 20 2 6
3 2 14 1 1 4 22
5 2 23 3 26 1 27 5 3 4 6
1 2 16
4 1 13 4 10 2 23 5 2
1 1 14
1 2 20
1 3 14
2 3 21 1 22
1 2 27
3 5 24 1 26 3 13
5 4 15 3 3 2 21 1 5 5 16
4 2 22 5 1 4 10 1 30

Sample Output

1
2
52
2168800

Solution

每個東西只能購買一次，可見是一個 01 背包問題，但是由於 C 很大，也就是背包容量過大，導致 DP 上的困難。

但是題目並沒有特別說明測資的特殊性，後來才得知可以用 gcd 最大共同因數去降，就是縮小幣值，相當於換外國幣去思考。這麼一來 C 可以降很多，但在一般的背包問題中，gcd 的效應並不高。

把我的純真還回來啊，不想自己 yy 測資特殊性。

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
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int C, n, m;
    int x, s, q;
    int cost[512], profit[512];
    int cases = 0;
    while (scanf("%d", &C) == 1) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d %d", &cost[i], &profit[i]), profit[i] -= cost[i];
        vector< pair<int, int> > items;
        for (int i = 0; i < m; i++) {
            scanf("%d", &x);
            int c = 0, p = 0;
            for (int j = 0; j < x; j++) {
                scanf("%d %d", &s, &q);
                c += cost[s] * q;
                p += profit[s] * q;
            }
            if (c <= C && p > 0)
                items.push_back(make_pair(c, p));
        }
        if (cases++)	puts("");
        if (items.size() == 0) {
            puts("0");
            continue;
        }
        if (items.size() == 1) {
            printf("%d\n", items[0].second);
            continue;
        }
        int g = C;
        for (int i = 0; i < items.size(); i++)
            g = __gcd(g, items[i].first);
        C /= g;
        for (int i = 0; i < items.size(); i++)
            items[i].first /= g;
        vector<int> dp(C + 1, 0);
        for (int i = 0; i < items.size(); i++) {
            for (int j = C; j >= items[i].first; j--)
                dp[j] = max(dp[j], dp[j - items[i].first] + items[i].second);
        }
        printf("%d\n", dp[C]);
    }
    return 0;
}
/*
500
4 6
10 15
8 6
20 15
12 12
3 1 6 2 7 3 8
3 3 8 1 10 2 4
3 4 10 2 5 1 10
2 1 4 2 4
1 3 2
2 4 3 2 1
200000000
5 30
2800 3500
1400 4800
2900 2800
500 3800
3300 4700
2 2 13 4 15
4 4 1 1 22 3 17 5 22
1 3 2
1 3 6
4 1 11 2 5 3 7 5 15
1 5 1
4 2 26 1 21 3 8 5 26
2 3 5 2 26
4 2 30 4 12 3 7 5 14
3 3 8 2 20 5 3
1 5 30
2 1 29 3 3
5 3 3 1 20 5 26 4 9 2 25
3 1 2 2 16 3 5
2 5 5 4 26
5 2 18 5 10 4 18 1 12 3 30
3 2 5 3 27 5 4
4 3 2 4 8 1 20 2 6
3 2 14 1 1 4 22
5 2 23 3 26 1 27 5 3 4 6
1 2 16
4 1 13 4 10 2 23 5 2
1 1 14
1 2 20
1 3 14
2 3 21 1 22
1 2 27
3 5 24 1 26 3 13
5 4 15 3 3 2 21 1 5 5 16
4 2 22 5 1 4 10 1 30
*/
Read More +
解題區/解題區 - UVa

UVa 12550 - How do spiders walk on water

Problem

一個可以行走在靜止水面上的蜘蛛，現在要靠近瀑布，瀑布會於鄰近周圍會產生流速。

蜘蛛最多可以在 P 速度的水面上前進，請問最近可以靠近瀑布多少。現在已知從靜止水面靠近瀑布的部分流速，在未知的部分根據觀察是前面單位距離 1 距離 2 的線性關係。$v_{i} = a v_{i-1} + b v_{i-2}$)

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
3 3 0 1 1 1
10 2 0 1 1 2
10 3 0 1 1 2
10 4 0 1 1 2
10 5 0 1 1 2
10 6 0 1 1 2
10 7 0 1 1 2
10 8 0 1 1 2
10 9 0 1 1 2
10 3 1 1 2 2 2 3 3 3 3 4 4
10 5 1 1 2 2 2 3 3 3 3 4 4
10 5 6 6 6 6 8 8 8 11 30 41 42
10 2 0 1 1 1 1 1 1 1 1 1 1
50 200 0 3 6 15 36

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
The spider may fall!
7
6
6
5
5
5
4
4
2
The spider may fall!
The spider is going to fall!
The spider may fall!
45

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
#include <stdio.h> 
#include <algorithm>
#include <sstream> 
#include <iostream>
using namespace std;
char line[1048576];
pair<double, double> solve(double a1, double b1, double c1, double a2, double b2, double c2) {
    // a1 x + b1 y = c1, a2 x + b2 y = c2
    double dx, dy, d;
    d = a1 * b2 - b1 * a2;
    dx = c1 * b2 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return make_pair(dx / d, dy / d);
}
int main() {
    int D, P;
    while (gets(line)) {
        stringstream sin(line);
        sin >> D >> P;
        double d[32767];
        int n = 0;
        while (sin >> d[n])	n++;
        int pos = 0;
        if (n < D + 1) {
            pair<double, double> sol = solve(d[n-4], d[n-3], d[n-2], d[n-3], d[n-2], d[n-1]);
//			printf("%lf %lf\n", sol.first, sol.second);
            for (int i = n; i < D + 1; i++, n++) {
                d[i] = sol.first * d[i-2] + sol.second * d[i-1];
                if (P < d[i])	break;
            }
        }		
        for (int i = 0; i < D + 1; i++) {
            if (P < d[i])	break;
            pos++;
        }
        if (pos == D + 1)
            puts("The spider may fall!");
        else if (pos == 0)
            puts("The spider is going to fall!");
        else
            printf("%d\n", D - pos + 1);
    }
    return 0;
}
/*
*/
Read More +
解題區/解題區 - UVa

UVa 12094 - Battle of the Triangle

Problem

平面上有士兵和戰車，分別有 S 個、T 個，接著會有 Q 組詢問，每組詢問有三條線，每組詢問之間的線保證斜率會彼此相同 (只是移動線，這需求非常奇怪。)，請問三條線拉出的 7 個區域中，中間與外側三塊地士兵、戰車個數差異為何？

Sample Input

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

Sample Output

1
2
3
Battle Field 1:
Query 1: 1 -2
Query 2: 1 -1

Solution

先獲得需要劃分的斜率，對三種斜率進行點的排序，因此對得到六個排序結果 (士兵和戰車)。之後就能在排序結果中，二分搜尋該線的左側、右側分別有多少點。

解決這個之後，要來看看噁心的排容原理，這裡還是建議參照 flere 的圖示：

對於拉出的三角形三個交點編號 A, B, C，接著對其做區域編號，

(1) BC 線段的左邊 有區域 1 2 3 6
(2) AC 線段的左邊 有區域 2 6 7
(3) AB 線段的下面 有區域 2 3 4
(1) - (2) - (3) 就可以得到區域 1 - 2 - 7 - 4
就是我們要的答案

flere

在程式邏輯上，挑一點與其一線同側，另兩條線與點異側。

沒有辦法單獨對區域內部搜尋點個數，然後統計完再相減，即使使用 range query，也無法在有效時間內完成任意三角形的範圍搜索 (矩形可以考慮，用等腰直角三角形也好。)。

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
#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define eps 1e-6
const double pi = acos(-1); 
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;
    }
    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);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double length(Pt a) {
    return hypot(a.x, a.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);
}
double angle(Pt a, Pt b) {
    return acos(dot(a, b) / length(a) / length(b));
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
Pt getIntersection(Pt p, Pt l1, Pt q, Pt l2) {
    double a1, a2, b1, b2, c1, c2;
    double dx, dy, d;
    a1 = l1.y, b1 = -l1.x, c1 = a1 * p.x + b1 * p.y;
    a2 = l2.y, b2 = -l2.x, c2 = a2 * q.x + b2 * q.y;
    d = a1 * b2 - a2 * b1;
    dx = b2 * c1 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return Pt(dx / d, dy / d);
}
struct Line {
    int A, B, C;
    bool operator<(const Line &a) const {
        double t1 = atan2(B, A);
        double t2 = atan2(a.B, a.A);
        if (t1 < 0)	t1 += pi;
        if (t2 < 0)	t2 += pi;
        return t1 < t2;
    }
};
Pt getIntersection(Line l1, Line l2) {
    double a1, a2, b1, b2, c1, c2;
    double dx, dy, d;
    a1 = l1.A, b1 = l1.B, c1 = -l1.C;
    a2 = l2.A, b2 = l2.B, c2 = -l2.C;
    d = a1 * b2 - a2 * b1;
    dx = b2 * c1 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return Pt(dx / d, dy / d);
}
struct cmp {
    static Line base;
    bool operator() (const Pt &p1, const Pt &p2) const {
        double c1, c2;
        c1 = p1.x * base.A + p1.y * base.B;
        c2 = p2.x * base.A + p2.y * base.B;
        if (fabs(c1 - c2) > eps)
            return c1 < c2;
        return false;
    }
};
Line cmp::base;
int main() {
    int cases = 0;
    int n, m, q;
    double x, y;
    while (scanf("%d %d %d", &n, &m, &q) == 3 && n) {
        vector<Pt> soldiers, tanks;
        vector<Pt> soldier[3], tank[3];
        Line Q[10000][3];
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x, &y);
            soldiers.push_back(Pt(x, y));
        }
        for (int i = 0; i < m; i++) {
            scanf("%lf %lf", &x, &y);
            tanks.push_back(Pt(x, y));
        }
        for (int i = 0; i < q; i++) {
            for (int j = 0; j < 3; j++) {
                scanf("%d %d %d", &Q[i][j].A, &Q[i][j].B, &Q[i][j].C);
                if (Q[i][j].A < 0 || (Q[i][j].A == 0 && Q[i][j].B < 0)) {
                    Q[i][j].A = -Q[i][j].A;
                    Q[i][j].B = -Q[i][j].B;
                    Q[i][j].C = -Q[i][j].C;
                }
            }
            sort(Q[i], Q[i] + 3);
        }
        for (int i = 0; i < 3; i++) {
            soldier[i] = soldiers;
            tank[i] = tanks;
            cmp::base = Q[0][i];
            sort(soldier[i].begin(), soldier[i].end(), cmp());
            sort(tank[i].begin(), tank[i].end(), cmp());
        }
//		for (int i = 0; i < 3; i++) {
//			for (int j = 0; j < soldier[i].size(); j++)
//				printf("%.2lf %.2lf ,", soldier[i][j].x, soldier[i][j].y);
//			puts("\n--++--");
//		}
        printf("Battle Field %d:\n", ++cases);
        for (int i = 0; i < q; i++) {
//			for (int j = 0; j < 3; j++)
//				printf("%d %d %d -\n", Q[i][j].A, Q[i][j].B, Q[i][j].C);
            Pt pabc[3];
            pabc[0] = getIntersection(Q[i][1], Q[i][2]); // bc
            pabc[1] = getIntersection(Q[i][0], Q[i][2]); // ac
            pabc[2] = getIntersection(Q[i][0], Q[i][1]); // ab
            int ret1 = 0, ret2 = 0;
            int tmp[3];
            for (int j = 0; j < 3; j++) {
                cmp::base = Q[i][j];
                tmp[j] = (int)(lower_bound(soldier[j].begin(), soldier[j].end(), 
                pabc[(j+1)%3], cmp()) - soldier[j].begin());
                int v1 = (Q[i][j].A * pabc[j].x + Q[i][j].B * pabc[j].y + Q[i][j].C < 0);
                int v2 = (Q[i][j].A * soldier[j][0].x + Q[i][j].B * soldier[j][0].y + Q[i][j].C < 0);
                int v3 = (Q[i][j].A * soldier[j][soldier[j].size()-1].x + Q[i][j].B * soldier[j][soldier[j].size()-1].y + Q[i][j].C < 0);
                    
                if (j == 0)  {
                    if (tmp[j]) {
                        if (v1 != v2)
                            tmp[j] = soldier[j].size() - tmp[j];
                    } else {
                        if (v1 == v3)
                            tmp[j] = soldier[j].size() - tmp[j];
                    }
                } else {
                    if (tmp[j]) {
                        if (v1 == v2)
                            tmp[j] = soldier[j].size() - tmp[j];
                    } else {
                        if (v1 != v3)
                            tmp[j] = soldier[j].size() - tmp[j];
                    }
                }
//				printf("[%d] soldier %d\n", j, tmp[j]);
            }
            ret1 = tmp[0] - tmp[1] - tmp[2];
            for (int j = 0; j < 3; j++) {
                cmp::base = Q[i][j];
                tmp[j] = (int)(lower_bound(tank[j].begin(), tank[j].end(), 
                pabc[(j+1)%3], cmp()) - tank[j].begin());
                int v1 = (Q[i][j].A * pabc[j].x + Q[i][j].B * pabc[j].y + Q[i][j].C < 0);
                int v2 = (Q[i][j].A * tank[j][0].x + Q[i][j].B * tank[j][0].y + Q[i][j].C < 0);
                int v3 = (Q[i][j].A * tank[j][tank[j].size()-1].x + Q[i][j].B * tank[j][tank[j].size()-1].y + Q[i][j].C < 0);
                    
                if (j == 0)  {
                    if (tmp[j]) {
                        if (v1 != v2)
                            tmp[j] = tank[j].size() - tmp[j];
                    } else {
                        if (v1 == v3)
                            tmp[j] = tank[j].size() - tmp[j];
                    }
                } else {
                    if (tmp[j]) {
                        if (v1 == v2)
                            tmp[j] = tank[j].size() - tmp[j];
                    } else {
                        if (v1 != v3)
                            tmp[j] = tank[j].size() - tmp[j];
                    }
                }
//				printf("[%d] tank %d\n", j, tmp[j]);
            }
            ret2 = tmp[0] - tmp[1] - tmp[2];
            printf("Query %d: %d %d\n", i+1, ret1, ret2);
        }
    }
    return 0;
}
/*
8 5 2
-1 8
-7 3
-2 1
-2 -1
-5 -2
6 -1
2 -4
-4 -5
1 7
1 1
3 4
-6 5
-12 -6
2 -2 10
-2 6 6
-5 -3 1
1 -1 5
1 -3 -3
5 3 -15
0 0 0
*/
Read More +
解題區/解題區 - UVa

UVa 11600 - Masud Rana

Problem

給 N 個城市，城市之間會有 M 條當前的安全邊，在其餘邊皆有邪惡組織出現，來阻擋城市之間的運行。

現在人在編號 1，每次將隨機挑任何相鄰的城市走過去 (隔天又會再挑一個鄰近的城市)，如果走過去的路上遇到邪惡組織則會將其殲滅，請問期望值需要幾天才能將 N 個城市彼此之間都存有連通路徑。

Sample Input

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

Sample Output

1
2
Case 1: 1.000000
Case 2: 3.500000

Solution

特別小心輸出的誤差要在 1e-6，以為只需要輸出 1 位，結果一直 WA。

事實上，將狀態壓縮成每一個連通元件的節點個數，對於連通元件之間做拉邊即可。

對於狀態 u, v，期望值 E[u] = 1 + E[v] p + E[u] q，

E[v] * p 表示：將兩個不同連通元件之間拉邊，則會將兩個連通元件融合，機率 p。
E[u] * q 表示：在各自的連通元件內布拉邊，不影響狀態結果。

左移一下得到 E[u] = (1 + E[v] * p) / (1 - q);

這一題必須考慮現在位於哪個連通元件，所以特別標記狀態的第一個連通元件為當前所在位置。

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
#include <stdio.h> 
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
// similar 1390 - Interconnect
int parent[32], weight[32];
int findp(int x) {
    return parent[x] == x ? x : findp(parent[x]);
}
void joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y)	return;
    if (weight[x] > weight[y])
        parent[y] = x, weight[x] += weight[y];
    else
        parent[x] = y, weight[y] += weight[x];
}
#define hash_mod 1000003
struct state {
    vector<int> c;
    unsigned int hash() {
        unsigned int a = 63689, b = 378551;
        unsigned int value = 0;
        for (int i = 0; i < c.size(); i++) {
            value = value * a + c[i];
            a *= b;
        }
        return value % hash_mod;
    }
    bool operator<(const state &a) const {
        if (c.size() != a.c.size())
            return c.size() < a.c.size();
        for (int i = 0; i < c.size(); i++)
            if (c[i] != a.c[i])
                return c[i] < a.c[i];
        return false;
    }
};
map<state, double> hash[hash_mod];
double dfs(state &u) {
    if (u.c.size() == 1)	return 0;
    sort(u.c.begin() + 1, u.c.end());
    int h = u.hash();
    if (hash[h].find(u) != hash[h].end())
        return hash[h][u];
    double &ret = hash[h][u];
    double self = 0, total = 0;
    ret = 0;
    for (int i = 0; i < u.c.size(); i++)
        total += u.c[i];
    total = total - 1, self = u.c[0] - 1;
    for (int i = 1; i < u.c.size(); i++) {
        state v = u;
        v.c[0] += v.c[i];
        v.c.erase(v.c.begin() + i);
        ret += u.c[i] * dfs(v);
    }
    // E[u] = 1 + E[v] * p + E[u] * q
    ret = (ret / total) + 1;
    ret = ret / (1 - self / total);
    return ret;
}
int main() {
    int n, m, x, y;
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++)
            parent[i] = i, weight[i] = 1;
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            joint(x, y);
        }
        
        state st;
        
        for (int i = 1; i <= n; i++) {
            if (parent[i] == i && parent[i] == findp(1))
                st.c.push_back(weight[i]);
        } 
        for (int i = 1; i <= n; i++) {
            if (parent[i] == i && parent[i] != findp(1)) // root
                st.c.push_back(weight[i]);
        }
        printf("Case %d: %lf\n", ++cases, dfs(st));
    }
    return 0;
}
/*
2
3 1
2 3
4 1
2 3
9999
3 3
1 2
2 3
3 1
*/
Read More +
解題區/解題區 - UVa

UVa 11529 - Strange Tax Calculation

Problem

任挑三個點拉出三角形，三角形內部的點數期望值為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
5
29 84
81 81
28 36
60 40
85 38
5
0 0
10 0
0 10
10 10
6 7
0

Sample Output

1
2
City 1: 0.20
City 2: 0.20

Solution

反過來寫，這一點會被多少個三角形包含住。

為了要計算這一個點 P 被多少三角形包含住，把這個點 P 當作基礎點，對其他點做極角排序。排序完套用極角掃描線算法，對於當前線上的點 Q，往回追溯 180 度內，任挑兩個點與其並成三角形，保證不包含 P。

那麼要得到包含 P 的就反過來用全部組合扣到不包含的結果。

因為要窮舉每一點做極角排序，作法會在 O(n^2 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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
#define eps 1e-9
const double pi = acos(-1);
struct Pt {
    double x, y;
    double angle;
    Pt(double a = 0, double b = 0):x(a), y(b) {
        angle = atan2(b, a);
    }
    bool operator<(const Pt &a) const {
        if (fabs(angle - a.angle) > eps)
            return angle < a.angle;
        return false;
    }
}; 
long long C[1300][1300] = {};
long long getContainTriangle(int st, Pt D[], int n) {
    static Pt A[4096];
    int m = 0;
    for (int i = 0; i < n; i++) {
        if (i == st)	continue;
        A[m++] = Pt(D[i].x - D[st].x, D[i].y - D[st].y);
    }
    sort(A, A + m);
    for (int i = 0; i < m; i++)
        A[i + m] = A[i], A[i+m].angle += 2 * pi;
    long long ret = 0;
    for (int i = 0, j = 1; i < m; i++) { // point(i, ?, ?)
        while (A[j].angle - A[i].angle <= pi - eps)	j++;
        ret += C[j - i - 1][2];
    }
    return C[m][3] - ret;
}
int main() {
    C[0][0] = 1;
    for (int i = 0; i < 1205; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
    int n, cases = 0;
    Pt D[1500];
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) 
            scanf("%lf %lf", &D[i].x, &D[i].y);
        long long contain = 0;// contain
        for (int i = 0; i < n; i++)
            contain += getContainTriangle(i, D, n); // with i-th point.
        printf("City %d: %.2lf\n", ++cases, (double)contain / C[n][3]);
    }
    return 0;
}
/*
5
29 84
81 81
28 36
60 40
85 38
5
0 0
10 0
0 10
10 10
6 7
0
*/
Read More +
解題區/解題區 - UVa

UVa 1331 - Minimax Triangulation

Problem

將一個簡單多邊形三角化，並且讓最大面積的三角形越小越好。

Sample Input

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

Sample Output

1
9.0

Solution

矩陣鏈乘積的方式著手 dp。

在此必須檢查劃分兩區間的三角形中內部不包含任何點，這裡利用外積 cross 進行計算。

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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define eps 1e-6
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;
        if (fabs(y-a.y) > eps)
            return y < a.y;
        return false;
    }
    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);
    }
    bool operator==(const Pt &a) const {
    	return (fabs(x - a.x) < eps && fabs(y - a.y) < eps);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
struct Seg {
    Pt s, e;
    Seg(Pt a = Pt(), Pt b = Pt()):
        s(a), e(b) {}
};
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 ptToSeg(Seg seg, Pt p) {
    double c = 1e+30;
    if(between(seg.s, seg.e, p))
        c = min(c, distProjection(seg.s, seg.e, p));
    else
        c = min(c, min(dist(seg.s, p), dist(seg.e, p)));
    return c;
}
double getArea(Pt a, Pt b, Pt c) {
    return fabs(cross(a, b, c))/2.0;
}
int isEmptyTriangle(Pt a, Pt b, Pt c, Pt D[], int n) {
    for (int i = 0; i < n; i++) {
        if (D[i] == a || D[i] == b || D[i] == c)
            continue;
        if (cross(a, D[i], b) * cross(a, D[i], c) < 0 && 
            cross(b, D[i], a) * cross(b, D[i], c) < 0 &&
            cross(c, D[i], a) * cross(c, D[i], b) < 0)
            return 0;
    }
    return 1;
}
int main() {
    int testcase, n;
    Pt D[128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            D[i].read();
        for (int i = 0; i < n; i++)
            D[i + n] = D[i];
        double dp[128][128];
        for (int i = 0; i < 2 * n; i++) {
            for (int j = 0; j < 2 * n; j++) {
                dp[i][j] = 1e+30;
            }
            dp[i][i] = dp[i][i+1] = 0;
        }
        double ret = 1e+30;
        for (int i = 2; i < n; i++) {
            for (int j = 0; j < n; j++) {// [j, j+i]
                int l = j, r = j + i;
                double &v = dp[l][r];
                for (int k = l+1; k < r; k++) {
                    if (isEmptyTriangle(D[l], D[r], D[k], D, n))
                        v = min(v, max(max(dp[l][k], dp[k][r]), getArea(D[l], D[r], D[k])));
                }
            }
        }
        for (int i = 0; i < n; i++)
            ret = min(ret, dp[i][i + n - 1]);
        printf("%.1lf\n", ret);
    }
    return 0;
}
/*
1
6
7 0
6 2
9 5
3 5
0 3
1 1
*/
Read More +
學校課程/通識課程

[通識] 文明的進程 小考集

好幾題都 0 分，也許只是相性不合。而我也只是寫寫我的回答，沒有什麼標準答案。

Week 1

  1. Brad 小學時的校長做了一件甚麼事情讓 Brad 終身難忘？
    讓 Brad 參加音樂會，在音樂會的最後上台自白疾病的原因與如何面對，受到同學們的認同與理解。

  2. Brad 的父親最後幫學校圖書館建書櫃，還送 Brad 甚麼當作和解的禮物？
    一頂工地安全帽。

  3. Brad 接電話時為什麼總是先說自己養了狗？
    因為妥瑞症引起的聲音有如狗吠一般，先避免對方猜疑發生了什麼。

  4. Brad 說他也有閱讀困難，是怎麼樣的困難？
    無法控制自己的脖子不時擺動，使得無法長時間專注於書本內容。

  5. Brad 對於進入那些公共場合有所顧忌？為什麼？
    圖書館、教會、電影院、音樂會。因為那而的人們必須保持固定的儀態和禮貌。

Week 2

  1. 哪個特質不屬於現代心靈：(1) 顧忌他人觀感 (2) 喜怒形於色 (3) 觀察盤算對方。
    (2) 喜怒形於色。(1)(3) 都有著抑制自我生物本能、顧及他人的模式，(2) 則沒有。

  2. 中世紀餐桌上最不常見的餐具是？ (1) 主餐盤 (2) 刀子 (3) 叉子
    (3) 叉子。刀子與主餐盤為餐點必備的工具和器材，而叉子是用來區隔他人食物而存在，當時物質不豐裕的情況下，算是奢侈地存在。

  3. 為什麼 Erasmas 在禮儀書中判斷「用餐時胡吃海塞」是鄉巴佬的行為？
    原本作答為 有如飢餓的野獸，為了區隔人與野獸的差別。 0 分
    行為不得體，沒有顧及他人的觀感，鄉巴佬總是做這些事情。(應該類似於這種回答？)

  4. 人際互動的「文明化」如何有助於科學研究方法的發展？
    原本作答為 文明化的互動反應物質生活與當時文化的流行，是一個直接的證據。 0 分
    人際互動的行為反應社會階級結構，藉此了解結構進行研究。(應該類似於這種回答？)

  5. 越是自命文明的人就越容易對他人的舉止感到「不舒服」為什麼？
    原本作答為 因為認為禮儀與自己相同才算文明，舉止不同的他人只會像野獸。 0 分
    階級高低的差別反應在舉止，因此在對於不同階級的人感到厭惡，也等同於對別人行為感到不舒服。

Week 3

  1. 中世紀貴族用餐最可能出現的菜色是：牛排、無骨鴨胸肉、全羊？
    全羊。當時還沒有食物幕後處理的概念，之後才有避見死相的道德感。

  2. 中世紀禮儀最不可能反映的是：身分階級、個人偏好、家庭背景？
    個人偏好。當時禮儀與階級有關，不會涉及強調個人。

  3. 文藝復興禮儀書最不可能說的是：不可粗俗、注意衛生、迴避不雅？
    原本作答為 衛生是後期科技進步，才用衛生理由取代粗俗的理由。 0 分
    注意衛生。當時講就是顧及別人，從不可粗俗、迴避不雅中可以發現都在顧及別人的觀感。注意衛生是在民主平等後，階級不重要，顧及自己才更有約束力。

  4. 就食物的準備而言，為何西方人覺得中華文化的飲食方式很「文明」？
    因為食物會經過多道手法，讓食用時看不出原貌，並且便於入口。不用吐骨。

  5. 這兩張「最後的晚餐」，哪張場景看起來年代較早？你的理由？
    第二張較早，因為沒有個人的餐具。晚期的餐具才比較普及。

    居然有藝術類型學生答題，根據畫風的不同來判斷年代 … 等，給這專業跪了，不過想必是 0 分 。

Week 4

  1. 文藝復興時期常常提醒人們「天使無所不在」，目的是什麼？
    在不需要顧及他人的需求時，仍要遵守禮儀的理由。

  2. 禮儀書說，便後從廁所回到社交場合時，不能讓人看出洗過手，為什麼？
    會讓場合的人因濕淋淋的手而想起廁所的那些汙穢。(備註：早期甚至希望不洗手。)

  3. 台北捷運地上劃的排隊等候線，其實不是 高度文明 的標誌，為什麼？
    因為需要外物的約束，如何不需要線就能遵守，表示規則內化，那是更文明。

  4. 為何用禮儀書來提升自己氣質的人，反而暴露自己階級地位不高？
    原本作答為 禮儀書的存在是在階級流動的幫手，教導低階級融入上層階級。 0 分
    教導階級高的社為人士的行為模式，正因為需要學習，才表示自己不處於上層階級。

  5. 就 Elias 而言，為什麼社會越文明，其兒童與成人之間的差距就越大？
    成人的禮儀要求越高，兒童在短時間內無法對百年禮儀融會貫通，而這只是相對差距。

Week 5

  1. 在課程 ppt 中，老師用多重比基尼泳裝的貓咪來嘲諷什麼？
    原本作答為 沒有必要這麼遮遮掩掩，一個母親的象徵竟被當作情色。 0 分
    過度地遮掩身體、過度道德化的結果。

  2. 以下何者 不是 社會歷史發展的結果？(1) 哈欠 (2) 洗手 (3) 掩鼻 (4) 遮體。為什麼？
    打哈欠一直都是生物自然反應。其餘皆為後天環境影響而做的事情。但是打哈欠用手遮住也算是後天教育而成。

  3. 為什麼當前的清涼穿著其是 不是 世風日下，而是文明化成功的象徵。

    世風日下：社會的風俗習慣日漸澆薄，每況愈下。(答題時根本不知道這個詞什麼意思。)

    原本作答為 因為向別人暴露身體原本是羞恥的事，面對自己身體不怕外人注目，是心靈上的昇華，外表遮掩不是限制。 0 分 (生物本能不就是要遮掩自我弱點嗎？)
    因為環境影響，代表治安好，不會有鹹豬手的人出現，因此才敢做出清涼穿著。

  4. 「人生：就是成人的生活」這個信念對於中世紀的兒童教育有何引響？
    原本作答為 讓兒童失去原本應有的童年，更早步入成人階段，沒有純真無潔的思想，都被羞恥的教育而想太多什麼不能做的事情。 0 分
    很多事情不能去做、不能去想。因此很多事情也不知道後果的嚴重性。

  5. 文明的 硬體技術 可以使得羞恥情感固定下來，請舉一個例子說明。

    那時卡在硬體設備與軟體技術，兩個弄在一起時，一直想不到那是什麼鬼，於是在被迫交卷前亂填答案。結果只是單純講硬體設備。

    廁所。利用大量的裝飾、氣氛，來隔絕與生物的排泄行為的聯想。

結語

被助教寫了 沒掌握本課程關鍵重點 、 沒有吸收 。我不否認，好幾堂課還在想算法分析。

Read More +
解題區/解題區 - UVa

UVa 12058 - Highway Monitor

Problem

在 n 個點的高速公路上，需要監視 m 條邊上的情況，監視器只能位於點上，並且可以監控所有與該點相連的邊，費用有限最多只能放置 k 個監視器，找到其中一種使用少於等於 k 個監視器的方法。

Sample Input

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

Sample Output

1
2
Case #1: no
Case #2: yes 1 2 5

Solution

解決最少點集覆蓋所有邊，是一個 NP 問題，雖然這一題已經給定限制搜索必須小於等於 K。

對於 DLX (Dancing Links and Algorithm X) 運用在最少重複覆蓋而言，K 是沒有太大的必要，事實上根據 degree 最大的節點開始窮舉的效果跟 DLX 差不多的。而這一題沒有要求最少，只是請求在範圍內的任一解輸出即可。

DLX 一開始用在精準覆蓋，解決重複覆蓋的效果只能說還算可以，大多的時間都花在計算估價函數，那個啟發式估價是用最簡單的貪心。有時候需要覆蓋的 colume 數量非常多，所以寫法上用 memset 也許是不錯的，但是用懶標記是更為快速。

DLX 的精神在於雙十字鏈表，並且每次找最少可能的 colume 開始窮舉，窮舉時會斷開所有相關在其他 colume 的可能，並在移除掉不需要窮舉的 colume，而在重複覆蓋上則不會移除掉需要窮舉的 colume。

  • 精确覆盖：
    首先选择当前要覆盖的列(含1最少的列)，将该列和能够覆盖到该列的行全部去掉，再枚举添加的方法。枚举某一行r，假设它是解集中的一个，那么该行所能覆盖到的所有列都不必再搜，所以删除该行覆盖到的所有列，又由于去掉的列相当于有解，所以能够覆盖到这些列的行也不用再搜，删之。
  • 重复覆盖：
    首先选择当前要覆盖的列(同上)，将该列删除，枚举覆盖到该列的所有行：对于某一行r，假设它是解集中的一个，那么该行所能覆盖到的列都不必再搜，所以删除该行覆盖到的所有列。注意此时不用删去覆盖到这些列的行，因为一列中允许有多个1。这里有一个A*的优化：估价函数h意义为从当前状态最好情况下需要添加几条边才能覆盖。

這一題會有 n 個 row，每一個 row 會覆蓋第 i 個節點覆蓋哪些邊。因此需要對所有輸入的邊進行編號，也就是 colume 會有 m 個。m 最大 50 萬，窮舉起來相當刺激。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXV 0x3f3f3f3f
#define MAXE 1048576
#define MAXC 1048576
#define MAXR 1024
struct DacingLinks {
    int left, right;
    int up, down;
    int ch, rh;
    int data; // extra info
} DL[MAXE];
int s[MAXC], o[MAXR], head, size, Ans, findflag;
void Remove(int c) {
    static int i;
    for(i = DL[c].down; i != c; i = DL[i].down) {
        DL[DL[i].right].left = DL[i].left;
        DL[DL[i].left].right = DL[i].right;
        s[DL[i].ch]--;
    }
}
void Resume(int c) {
    static int i;
    for(i = DL[c].down; i != c; i = DL[i].down) {
        DL[DL[i].right].left = i;
        DL[DL[i].left].right = i;
        s[DL[i].ch]++;
    }
}
int used[MAXC] = {};
int H() {
    static int c, ret, i, j, time = 0;
    for(c = DL[head].right, ++time, ret = 0; c != head; c = DL[c].right) {
        if(used[c] != time) {
            ret ++, used[c] = time;
            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 k) {
    if(k + H() >= Ans)    return;
    if(DL[head].right == head) {
        if(k < Ans) {
        	Ans = k, findflag = 1;
            printf("yes");
            for (int i = 0; i < k; i++)
                printf(" %d", DL[o[i]].data);
            puts("");
        }
        return;
    }
    int t = MAXV, c, i, j;
    for(i = DL[head].right; i != head; i = DL[i].right) {
        if(s[i] < t) {
            t = s[i], c = i;
        }
    }
    for(i = DL[c].down; i != c; i = DL[i].down) {
        o[k] = i;
        Remove(i);
        for(j = DL[i].right; j != i; j = DL[j].right)	Remove(j);
        DFS(k+1);
        for(j = DL[i].left; j != i; j = DL[j].left)     Resume(j);
        Resume(i);
        if (findflag)	break;
    }
}
int new_node(int up, int down, int left, int right) {
    assert(size < MAXE);
    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 addrow(int n, int Row[], int data) {
    int a, r, row = -1, k;
    for(a = 0; a < n; a++) {
        r = Row[a];
        DL[size].ch = r, s[r]++;
        DL[size].data = data;
        if(row == -1) {
            row = new_node(DL[DL[r].ch].up, DL[r].ch, size, size);
            DL[row].rh = a;
        }else {
            k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
            DL[k].rh = a;
        }
    }
}
void init(int m) {
    size = 0;
    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;
    }
} 
int main() {
    int testcase, cases = 0;
    int n, m, k, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &n, &m, &k);
        vector<int> g[1024];
        for (int i = 1; i <= m; i++) {
            scanf("%d %d", &x, &y);
            g[x].push_back(i);
            g[y].push_back(i);
        }
        assert(m < MAXC);
        init(m);
        int row[1024];
        for (int i = 1; i <= n; i++) {
            sort(g[i].begin(), g[i].end());
            for (int j = 0; j < g[i].size(); j++)
                row[j] = g[i][j];
            addrow(g[i].size(), row, i);
        }
        printf("Case #%d: ", ++cases);
        Ans = k + 1, findflag = 0;
        DFS(0);
        if (Ans == k+1)
            puts("no");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12052 - Cyber cafe

Problem

給一張圖有 N 個節點、M 條邊，其中要放置 S 台新主機於其中 S 個節點，而沒放置的節點繼續使用舊主機，為了服務舊主機的網咖，每個舊節點旁邊最多只能有一個新主機網咖。

請問有多少種放置方法。

Sample Input

1
2
3
4
5
6
7
8
9
10
Dhaka
6 2 7
AB BC CD DE EF FA AD
Chittagong
4 3 4
AB AC AD BC
Sylhet
3 2 3
AB BC CA
TheEnd

Sample Output

1
2
3
4
5
6
7
Dhaka
9
Chittagong
1
Sylhet
0
TheEnd

Solution

對於每一個節點的連接方式用一個 32-bit 壓縮，接著窮舉所有可能放置方法 state，對於沒有放置的節點，直接壓縮結果與 state 做 AND 運算，算 bits 數是否都小於 2。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    char ss[1024];
    int n, s, p;
    while (scanf("%s", &ss) == 1) {
        printf("%s\n", ss);
        if (!strcmp(ss, "TheEnd"))
            break;
        scanf("%d %d %d", &n, &s, &p);
        int g[26][26] = {};
        for (int i = 0; i < p; i++) {
            scanf("%s", ss);
            int x = ss[0] - 'A', y = ss[1] - 'A';
            g[x][y] = g[y][x] = 1;
        }
        int mask[26] = {};
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                mask[i] |= g[i][j]<<j;
        int ret = 0;
        for (int i = (1<<n)-1; i >= 0; i--) {
            if (__builtin_popcount(i) == s) {
                int ok = 1;
                for (int j = 0; j < n && ok; j++) {
                    if ((i>>j)&1)	continue;
                    if (__builtin_popcount(mask[j]&i) >= 2)
                        ok = 0;
                }
                ret += ok;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12051 - Mazes in Higher Dimensions

Problem

好比 2D 方格，從左下角到右上角的方法數。而這一題是在三維空間，一樣的方式要越來越靠近右上方的頂點，但是部分點會有障礙物，會造成無法通行。

題目給定的維度事實上是終點座標，而非該維度數，用 row major 的時候要計算 dim[i]+1。

Sample Input

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

Sample Output

1
2
Case 1: 756756
Case 2: 6318655200

Solution

特地用懶標記完成 dp 計算，但是忘了有可能無法抵達終點，忘了補上最對於終點的懶標記操作，直接輸出 dp[ret] 結果一直噴 WA。

懶標記檢查 if (used[ret] != testcase) dp[ret] = 0;。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXN 3000005
long long dp[MAXN] = {};
int used[MAXN] = {}, ob[MAXN] = {}; // obstacle
int main() {
    memset(dp, 0, sizeof(dp));
    memset(ob, 0, sizeof(ob));
    memset(used, 0, sizeof(used));
    int n, m, dim[16], row[16], v[16];
    int testcase = 0, cases = 0;
    while (scanf("%d %d", &n, &m) == 2 && n+m) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &dim[i]);
            dim[i]++;
        }
        testcase++;
        row[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--)
            row[i] = row[i+1] * dim[i+1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++)
                scanf("%d", &v[j]);
            int x = 0;
            for (int j = 0; j < n; j++)
                x += v[j] * row[j];
            ob[x] = testcase;
        }
        if(ob[0] == testcase){
            printf("Case %d: 0\n", ++cases);
            continue;
        }
        int ret = 0;
        for (int i = 0; i < n; i++)
            ret += (dim[i] - 1) * row[i];
        queue<int> Q;
        Q.push(0), used[0] = testcase;
        dp[0] = 1;
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            long long ways = dp[x];
            for (int i = 0; i < n; i++)
                v[i] = x / row[i], x %= row[i];
            for (int i = 0; i < n; i++) {
                v[i]++;
                if (v[i] < dim[i]) {
                    x = 0;
                    for (int j = 0; j < n; j++)
                        x += v[j] * row[j];
                    if (ob[x] != testcase) {
                        if (used[x] != testcase)
                            dp[x] = 0;
                        dp[x] += ways;
                        if (used[x] != testcase)
                            Q.push(x), used[x] = testcase;
                    }
                }
                v[i]--;
            }
        }
        if (used[ret] != testcase)	dp[ret] = 0;
        printf("Case %d: %lld\n", ++cases, dp[ret]);
    }
    return 0;
}
/*
3 0 
5 5 5
 
3 1 
9 8 7
1 1 1
3 2
9 8 7
1 1 1
5 6 6
3 2
9 8 7
2 3 4
9 8 7
3 2
9 8 7
2 3 4
9 8 7
0 0
*/
Read More +