解題區/解題區 - UVa

UVa 12524 - Arranging Heaps

Problem

現在有 n 個堆，位於位置 xi 的堆重量 wi，對於每一堆可以移動到位置大的地方，移動的成本為(xj - xi) * wi，請問集中 k 堆的最少花費為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
3 1
20 1
30 1
40 1
3 1
11 3
12 2
13 1
6 2
10 15
12 17
16 18
18 13
30 10
32 1
6 3
10 15
12 17
16 18
18 13
30 10
32 1

Sample Output

1
2
3
4
30
8
278
86

Solution

參考 work_freedom的专栏

dp[i][j] : 表示放入 i 堆，集中 j 堆的最少花費

1
2
3
4
dp[i][j] = dp[k][j-1] + X[i] * (sumW[i] - sumW[k]) - (sumXW[i] - sumXW[k])
dp[k][j-1] + sumXW[k] = X[i] * sumW[k] + dp[i][j] + sumXW[i] - sumW[i] * X[i]
^^^^^^^^^^^^^^^^^^^^^   ^^^^   ^^^^^^^   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
y = a x + b, a : monotone increasing, maintain upper convex

將公式調整為上述結果，會發現我們依序帶入的 X[i] 遞增，也就是斜率會越來越高，要使後半部常數越大越好，保證此線會相交於凸包的頂點上。

凸包點 (sumW[k], dp[k][j-1] + sumXW[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
#include <stdio.h> 
#include <algorithm>
#include <string.h>
using namespace std;
#define MAXN 1024
long long dp[MAXN][MAXN], X[MAXN], W[MAXN];
long long sumW[MAXN] = {}, sumXW[MAXN] = {};
struct SlopeDP {
    int front, rear;
    long long X[MAXN], Y[MAXN];
    void init() {front = 0, rear = -1;}
    long long cross(long long x1, long long y1, long long x2, long long y2) {
        return x1 * y2 - y1 * x2;
    }
    int add(long long x, long long y) {
        while (front < rear && cross(X[rear]-X[rear-1], Y[rear]-Y[rear-1], x-X[rear-1], y-Y[rear-1]) < 0)
            rear--;
        rear++;
        X[rear] = x, Y[rear] = y;
    }
    long long get(long long m) {
        while (front < rear && Y[front+1]-Y[front] < (X[front+1]-X[front]) * m)
            front++;
        return Y[front] - m * X[front];
    }
} dpTool;
int main() {
    int N, M;
    while (scanf("%d %d", &N, &M) == 2) {
        for (int i = 1; i <= N; i++)
            scanf("%lld %lld", &X[i], &W[i]);
        for (int i = 1; i <= N; i++) {
            sumW[i] = sumW[i-1] + W[i];
            sumXW[i] = sumXW[i-1] + X[i] * W[i];
        }
        for (int i = 0; i <= N; i++)
            for (int j = 0; j <= M; j++) 
                dp[i][j] = 1LL<<60;
        dp[0][0] = 0;
//		for (int i = 1; i <= N; i++) {
//			for (int j = 1; j <= M; j++) {
//				for (int k = 0; k < i; k++)
//					dp[i][j] = min(dp[i][j], dp[k][j-1] + X[i] * (sumW[i] - sumW[k]) - (sumXW[i] - sumXW[k]));
//			}
//		}
        for (int i = 1; i <= M; i++) {
            dpTool.init();
            for (int j = i; j <= N; j++) {
                dpTool.add(sumW[j-1], dp[j-1][i-1] + sumXW[j-1]);
                long long val = dpTool.get(X[j]);
                dp[j][i] = val - (sumXW[j] - sumW[j] * X[j]);
            }
        }
        printf("%lld\n", dp[N][M]);
    }
    return 0;
}
/*
dp[i][j] = dp[k][j-1] + X[i] * (sumW[i] - sumW[k]) - (sumXW[i] - sumXW[k])
dp[k][j-1] + sumXW[k] = X[i] * sumW[k] + dp[i][j] + sumXW[i] - sumW[i] * X[i]
^^^^^^^^^^^^^^^^^^^^^   ^^^^   ^^^^^^^   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
y = a x + b, a : monotone increasing, maintain upper convex
*/
/*
3 1
20 1
30 1
40 1
3 1
11 3
12 2
13 1
6 2
10 15
12 17
16 18
18 13
30 10
32 1
6 3
10 15
12 17
16 18
18 13
30 10
32 1
*/
Read More +
解題區/解題區 - UVa

UVa 12141 - Line Chart

Problem

給 n 個點趨勢圖，可以選擇忽略某些點，忽略的點會被剩餘點補上靠左。

請問要恰好 k 個 peak 的情況，有多少不同的趨勢圖貌。這別要求兩個相鄰的點不可以有相同 y 值。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3
6 1
320 3
306 1
401 3
325 4
393 5
380 2
4 1
101 3
102 2
103 2
104 4
3 0
102 2
101 1
103 3

Sample Output

1
2
3
Case 1: 20
Case 2: 1
Case 3: 8

Solution

TLE 版本，答案是正確的。 O(n^2 m)

其實這有點接近貪心作法，狀態為 dp[i][k][3] 表示加入第 i 個點，產生 k 個 peak，並且下一次要接 y 值較高、較低、等於的點。

而考慮當前 k 個 peak y[i]，對於三種高地要求，我們只會轉移到不同的 y 值，也就是對於後面如果存有 y[p] = y[q], p < q，盡可能選擇 p 小的，否則會重複計算，要忽略 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
#include <stdio.h> 
#include <vector>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
int dp[10005][64][3] = {};
const int mod = 1000000;
int main() {
    freopen("in.txt", "r+t", stdin);
    freopen("out.txt", "w+t", stdout);
    int testcase, n, m, x, y;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        vector< pair<int, int> > D;
        map<int, int> R;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            R[y] = 0;
            D.push_back(make_pair(x, y));
        }
        sort(D.begin(), D.end());
        int v = 0;
        for (map<int, int>::iterator it = R.begin();
            it != R.end(); it++)
            it->second = v++;
        for (int i = 0; i < n; i++)
            D[i].second = R[D[i].second];
        memset(dp, 0, sizeof(dp));
        int used[10005] = {};
        for (int i = 0; i < n; i++) {
            if (used[D[i].second] == 0) {
                dp[i][0][0] = 1; // =
                dp[i][0][1] = 1; // <
                dp[i][0][2] = 1; // > next time
                used[D[i].second] = 1;
            }
        }
        int ret = 0;
        if (m == 0)
            ret++;
        for (int i = 0; i < n; i++) {
            ret = (ret + dp[i][m][0])%mod;
            memset(used, 0, sizeof(used));
//			for (int k = 0; k <= m; k++) 
//					printf("[%d %d] %d %d %d\n", i, k, dp[i][k][0], dp[i][k][1], dp[i][k][2]);
            for (int j = i+1; j < n; j++) {					
                if (used[D[j].second])	continue;
                used[D[j].second] = 1;
                for (int k = 0; k <= m; k++) {
                    if (D[j].second > D[i].second) { // larger
                        dp[j][k][0] = (dp[j][k][0] + dp[i][k][2])%mod;
                        dp[j][k+1][1] = (dp[j][k+1][1] + dp[i][k][2])%mod;
                        dp[j][k][2] = (dp[j][k][2] + dp[i][k][2])%mod;
                    } else if (D[j].second == D[i].second) {
//						dp[j][k][0] = (dp[j][k][0] + dp[i][k][0])%mod;
//						dp[j][k][1] = (dp[j][k][1] + dp[i][k][0])%mod;
//						dp[j][k][2] = (dp[j][k][2] + dp[i][k][0])%mod;
                    } else {
                        dp[j][k][0] = (dp[j][k][0] + dp[i][k][1])%mod;
                        dp[j][k][1] = (dp[j][k][1] + dp[i][k][1])%mod;
                        dp[j][k+1][2] = (dp[j][k+1][2] + dp[i][k][1])%mod;
                    }
                }
            }
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}

使用 binary indexed tree 優化 O(nm log n)

使用前綴總和來完成狀態轉移。為了防止相同 y[p] = y[q], p < q，由於會先拜訪到 p 進行狀態轉移，特別考慮 y[q] 基底的轉移狀態必須被扣除 y[p] 的結果。

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
#include <stdio.h> 
#include <vector>
#include <string.h>
#include <algorithm>
#include <map>
#include <assert.h>
using namespace std;
#define MAXN 10050
int dp[MAXN][64][3] = {};
int UBIT[64][3][MAXN], DBIT[64][3][MAXN];
int shift[64][3][MAXN] = {};
const int mod = 1000000;
int query(int A[], int idx) {
    int sum = 0;
    while (idx)
        sum = (sum + A[idx])%mod, idx -= idx&(-idx);
    return sum;
}
void modify(int A[], int idx, int val, int L) {
    while (idx <= L)
        A[idx] = (A[idx] + val)%mod, idx += idx&(-idx);
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout);
    int testcase, n, m, x, y;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        vector< pair<int, int> > D;
        map<int, int> R;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            R[y] = 0;
            D.push_back(make_pair(x, y));
        }
        sort(D.begin(), D.end());
        int L = 1;
        for (map<int, int>::iterator it = R.begin();
            it != R.end(); it++)
            it->second = L++;
        for (int i = 0; i < n; i++)
            D[i].second = R[D[i].second];
        memset(UBIT, 0, sizeof(UBIT));
        memset(DBIT, 0, sizeof(DBIT));
        memset(shift, 0, sizeof(shift));		
        int used[10005] = {};
        for (int i = 0; i < n; i++) {
            if (used[D[i].second] == 0) {
                shift[0][0][D[i].second] = -1; // =
                used[D[i].second] = 1;
            }
        }
        modify(UBIT[0][1], 1, 1, L);
        modify(UBIT[0][2], 1, 1, L);
        int ret = 0;
        if (m == 0)
            ret++;
        for (int i = 0; i < n; i++) {
            for (int k = 0; k <= m; k++) {
                int dp0 = query(UBIT[k][0], D[i].second) + query(DBIT[k][0], L - D[i].second-1) - shift[k][0][D[i].second];
                int dp1 = query(UBIT[k][1], D[i].second) + query(DBIT[k][1], L - D[i].second-1) - shift[k][1][D[i].second];
                int dp2 = query(UBIT[k][2], D[i].second) + query(DBIT[k][2], L - D[i].second-1) - shift[k][2][D[i].second];
//				printf("[%d %d] %d %d %d\n", i, k, dp0, dp1, dp2);
                dp0 %= mod, dp1 %= mod, dp2 %= mod;
                shift[k][0][D[i].second] += dp0;
                shift[k][1][D[i].second] += dp1;
                shift[k][2][D[i].second] += dp2;
                if (k == m)		ret = (ret + dp0)%mod;
                if (dp2) {
                    modify(UBIT[k][0], D[i].second+1, dp2, L);
                    modify(UBIT[k+1][1], D[i].second+1, dp2, L);
                    modify(UBIT[k][2], D[i].second+1, dp2, L);
                }
                if (dp1) {
                    modify(DBIT[k][0], L - D[i].second, dp1, L);
                    modify(DBIT[k][1], L - D[i].second, dp1, L);
                    modify(DBIT[k+1][2], L - D[i].second, dp1, L);
                }
            }
        }
        printf("Case %d: %d\n", ++cases, (ret + mod)%mod);
    }
    return 0;
}
/*
3
3 0
1 1
2 1
3 1
3 1
101 3
102 2
104 4
3
6 1
320 3
306 1
401 3
325 4
393 5
380 2
4 1
101 3
102 2
103 2
104 4
3 0
102 2
101 1
103 3
*/
Read More +
解題區/解題區 - UVa

UVa 11910 - Closest Fractions

Problem

對於每一個浮點數，找到一個最靠近的分數，分子分母限制在 [1, 1000] 的整數。

Sample Input

1
2
3
3.141592654
66.66666666
333.3333333

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
Input : 3.141592654
    1 : 3.141592920 =  355 / 113
    2 : 3.141630901 =  732 / 233
    3 : 3.141552511 =  688 / 219
Input : 66.66666666
    1 : 66.66666667 =  200 / 3
    2 : 66.64285714 =  933 / 14
    3 : 66.69230769 =  867 / 13
Input : 333.3333333
    1 : 333.3333333 = 1000 / 3
    2 : 333.5000000 =  667 / 2
    3 : 333.0000000 =  333 / 1

Solution

預先將所有分數建表，然後每一次二分搜索。

最麻煩在於輸出要保證長度 10 位，細讀 printf() 後，發現頂多限制小數點後的位數、小數點前的位數，如果要同時限制還是要自己來。

最後使用 %*.*f，* 號部分要自己帶入參數。如果用 substring 會造成四捨五入的地方消失而拿到 WA。

原本想不建表，直接用鄰近搜索，誤差害死人。

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 <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
class Frac {
    public:
    int x, y;
    Frac(int a = 0, int b = 0):
        x(a), y(b) {}
    double toDouble() const {
        return (double) x/y;
    }
    bool operator<(const Frac &a) const {
        return toDouble() < a.toDouble();
    }
} D[1048576];
double DD[1048576];
double cmpv;
bool cmp(Frac a, Frac b) {
    return fabs(a.toDouble() - cmpv) < fabs(b.toDouble() - cmpv);
}
int f(double v) {
    if (v >= 1000)	return 4;
    if (v >= 100)	return 3;
    if (v >= 10)	return 2;
    return 1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n = 0;
    for (int y = 1; y <= 1000; y++) {
        for (int x = 1; x <= 1000; x++) {
            if (__gcd(x, y) == 1)
                D[n++] = Frac(x, y);
        }
    }
    sort(D, D + n);
    for (int i = 0; i < n; i++)
        DD[i] = D[i].toDouble();
    char s[32];
    double v;
    while (scanf("%s", s) == 1) {
        printf("Input : %s\n", s);
        sscanf(s, "%lf", &v);
        int pos = lower_bound(DD, DD + n, v) - DD;
        vector<Frac> A;
        for (int i = max(0, pos - 6); i < min(n, pos + 6); i++)
            A.push_back(D[i]);
        cmpv = v;
        sort(A.begin(), A.end(), cmp);
        for (int i = 0, j = 1; i < 3 && i < A.size(); i++, j++)
            printf("    %d : %*.*lf = %4d / %d\n", j, f(A[i].toDouble()), 10 - f(A[i].toDouble()), A[i].toDouble(), A[i].x, A[i].y);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11768 - Lattice Point or Not

Problem

給一個浮點數一位的線段，請問中間經過多少個整數點。

Sample Input

1
2
3
4
3
10.1 10.1 11.2 11.2
10.2 100.3 300.3 11.1
1.0 1.0 2.0 2.0

Sample Output

1
2
3
1
0
2

Solution

找到原本線段 ax + by = c 的線，為了使其落在整數座標上調整為 10a x + 10b y = c，在這個情況下找到符合的 (x, y) 整數解，但是其結果要被限制上線段上。

努力地做細部微調 …

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
long long gcd(long long x, long long y) {
    long long t;
    while (x%y)
        t = x, x = y, y = t%y; 
    return y;
}
long long exgcd(long long x, long long y, long long &a, long long &b) {
    // ax + by = gcd(x,y)
    int flag = 0;
    long long t, la = 1, lb = 0, ra = 0, rb = 1;
    while(x%y) {
        if(flag == 0)
            la -= x/y*ra, lb -= x/y*rb;
        else
            ra -= x/y*la, rb -= x/y*lb;
        t = x, x = y, y = t%y;
        flag = 1 - flag;
    }
    if(flag == 0)
        a = ra, b = rb;
    else
        a = la, b = lb;
    return y;
}
long long countSolution(long long n1, long long n2, long long n, 
					long long lx, long long rx, long long ly, long long ry) {
//	printf("%lld %lld %lld\n", n1, n2, n);
    if (lx > rx || ly > ry)	return 0;
    if (n1 == 0)	return rx - lx + 1;
    if (n2 == 0)	return ry - ly + 1;
    long long a, b, g;
    g = exgcd(n1, n2, a, b); // a*n1 + b*n2 = gcd(n1,2)
    if(n%g) return 0;
    long long k = n/g, k1, k2;
    a *= k, b *= k;// a*n1 + b*n2 = n
    // (a+F)*n1 + (b+G)*n2 = n =>  Fn1 + Gn2 = 0, F = lcm(n1, n2)/n1 * i, G = lcm(n1, n2)/n2 * i
    k1 = n1*n2/g/n1, k2 = n1*n2/g/n2;
    long long x1, x2, x3, x4, y1, y2, y3, y4;
    k = (a - lx)/k1;
    a -= k*k1, b += k*k2;
    while (a < lx) {
    	if (k1 < 0)	a -= k1, b += k2;
    	else		a += k1, b -= k2;
    }
    x1 = a, y1 = b;
    
    k = (b - ly)/k2;
    a += k*k1, b -= k*k2;  
    while (b < ly) {
    	if (k2 < 0)	a += k1, b -= k2;
    	else		a -= k1, b += k2;
    }
    x3 = a, y3 = b;  
    
    k = (a - rx)/k1;
    a -= k*k1, b += k*k2;
    while (a > rx) {
    	if (k1 < 0)	a += k1, b -= k2;
    	else		a -= k1, b += k2;
    }
    x2 = a, y2 = b;
    
    k = (b - ry)/k2;
    a += k*k1, b -= k*k2;
    while (b > ry) {
    	if (k2 < 0)	a -= k1, b += k2;
    	else		a += k1, b -= k2;
    }
    x4 = a, y4 = b;
    long long l1 = 0, r1 = (x2 - x1)/ k1;
    long long l2 = (x3 - x1)/k1, r2 = (x4 - x1)/k1;
    if (l2 > r2)	swap(l2, r2);
    if (x1 > x2 || y3 > y4)	return 0;
//    printf("%lld %lld %lld %lld\n", x1, y1, x2, y2);
//    printf("%lld %lld %lld %lld\n", x3, y3, x4, y4);
//    printf("%lld %lld %lld %lld\n", l1, r1, l2, r2);
    l1 = max(l1, l2), r1 = min(r1, r2);
    if (l1 <= r1)	return r1 - l1 + 1;
    return 0;
}
long long read1Float() {
    long long x, y;
    scanf("%lld.%lld", &x, &y);
    return x * 10 + y;
}
int main() {    
//	freopen("in.txt","r+t",stdin);
//  freopen("out2.txt","w+t",stdout);
    int testcase, cases = 0;
    long long sx, sy, ex, ey;
    scanf("%d", &testcase);
    while (testcase--) {
        sx = read1Float();
        sy = read1Float();
        ex = read1Float();
        ey = read1Float();
        long long minx, miny, maxx, maxy;
        minx = ceil(min(sx, ex)/10.0);
        maxx = floor(max(sx, ex)/10.0);
        miny = ceil(min(sy, ey)/10.0);
        maxy = floor(max(sy, ey)/10.0);
        long long a, b, c;
        a = (ey - sy), b = (sx - ex), c = (a * sx + b * sy);
        a = a * 10, b = b * 10;
//		printf("[%lld %lld] [%lld %lld]\n", minx, maxx, miny, maxy);
        printf("%lld\n", countSolution(a, b, c, minx, maxx, miny, maxy));
    }
    return 0;
}
/*
5
10.1 10.1 11.2 11.2
10.2 100.3 300.3 11.1
1.0 1.0 2.0 2.0
1.0 1.0 1.0 1.0
1.0 3.0 1.0 7.0
100
74779.7 170072.4 114261.9 224.6
12284.7 149345.2 89292.2 24355.6
119238.0 59748.9 153776.5 88822.9
146984.2 79235.1 116519.4 144150.1
75703.5 8776.5 147012.5 132491.5
93698.8 27585.7 137374.4 134649.2
100
142566.2 47373.1 4487.9 81130.6
122932.1 117873.7 7944.5 24862.7
164852.3 50346.6 58670.9 47341.7
140828.3 21325.9 141292.5 16763.8
144206.3 130562.5 96260.1 53203.7
100
175593.7 137910.8 151744.6 21975.7
66918.0 141841.9 170688.8 108941.3
110334.9 103217.3 145166.0 126201.0
40233.7 62521.1 116634.3 146758.8
187820.7 131930.2 69771.4 66737.3
*/
Read More +
解題區/解題區 - UVa

UVa 11731 - Ex-circles

Problem

給三個圓，它們彼此之間的內公切線會構成一個三角形，現在給定三角形的三邊長，請問灰色扇形面積為何。

Sample Input

1
2
3
3 4 5
10 11 12
0 0 0

Sample Output

1
2
Case 1: 30.00 21.62
Case 2: 211.37 144.73

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
#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#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);
}
double getGrayArea(Pt A, Pt B, Pt C) {
    double r = fabs(cross2(B - A, C - A)) / dist(B, C);
    double radBAC = angle(B - A, C - A);
    return r * r * radBAC /2;
}
int main() {
    int cases = 0;
    double a, b, c;
    while(scanf("%lf %lf %lf", &a, &b, &c) == 3 && a+b+c) {
        Pt A, B, C, D, E, F;
        double radBAC = acos((b*b + c*c - a*a)/(2*b*c));
        double radABC = acos((a*a + c*c - b*b)/(2*a*c));
        double radACB = acos((a*a + b*b - c*c)/(2*a*b));
        A = Pt(0, 0);
        B = Pt(c, 0);
        C = A + rotateRadian(Pt(1, 0), radBAC) * b;
        double t1, t2, t3;
        t1 = (pi - radBAC)/2;
        t2 = (pi - radABC)/2;
        t3 = (pi - radACB)/2;
        Pt divA, divB, divC;
        divA = rotateRadian(C - A, t1); 
        divB = rotateRadian(B - A, t2);
        divC = rotateRadian(C - B, t3);
        D = getIntersection(A, divA, C, divC);
        E = getIntersection(B, divB, C, divC);
        F = getIntersection(A, divA, B, divB);
//		printf("%lf %lf, %lf %lf, %lf %lf\n", A.x, A.y, B.x, B.y, C.x, C.y);
//		printf("%lf %lf, %lf %lf, %lf %lf\n", D.x, D.y, E.x, E.y, F.x, F.y);
        double area = fabs(cross2(E - D, F - D))/2;
        double gray = getGrayArea(D, A, C) + getGrayArea(E, B, C) + getGrayArea(F, A, B);
        printf("Case %d: %.2lf %.2lf\n", ++cases, area, gray);
    }
    return 0;
}
/*
3 4 5
10 11 12
*/
Read More +
解題區/解題區 - UVa

UVa 10794 - The Deadly Olympic Returns

Problem

給你兩個三維空間的射線，請問它們的最近距離為何。

Sample Input

1
2
3
4
5
6
7
2
1
0 0 0 1 0 0
0 -1 0 0 -2 0
4
0 0 0 1 0 0
-1 0 0 -2 0 0

Sample Output

1
2
Case 1: 1.0000
Case 2: 1.0000

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
struct Point3D {
    double x, y, z;
    Point3D(double a = 0, double b = 0, double c = 0):
        x(a), y(b), z(c) {}
    void read() {
        scanf("%lf %lf %lf", &x, &y, &z);
    }
    Point3D operator+(const Point3D &a) const {
        return Point3D(x + a.x, y + a.y, z + a.z);
    }
    Point3D operator-(const Point3D &a) const {
        return Point3D(x - a.x, y - a.y, z - a.z);
    }
    Point3D operator/(const double &a) const {
        return Point3D(x/a, y/a, z/a);
    }
    Point3D operator*(const double &a) const {
        return Point3D(x*a, y*a, z*a);
    }
    double dist(Point3D a) const {
        return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y) + (z - a.z) * (z - a.z));
    }
    double dist2(Point3D a) const {
        return (x - a.x) * (x - a.x) + (y - a.y) * (y - a.y) + (z - a.z) * (z - a.z);
    }
};
int main() {
    int testcase, cases = 0;
    double time;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lf", &time);
        Point3D A, B, C, D, V1, V2;
        A.read(), B.read();
        C.read(), D.read();
        V1 = (B - A) / time;
        V2 = (D - C) / time;
        double l = 0, r = 1e+8;
        double mid, midmid, md, mmd;
        double mndist = A.dist2(C);
        while (fabs(l - r) > 1e-8) {
            mid = (l + r)/2;
            midmid = (mid + r)/2;
            md = ((V1 * mid) + A).dist2((V2 * mid) + C);
            mmd = ((V1 * midmid) + A).dist2((V2 * midmid) + C);
            mndist = min(mndist, md);
            mndist = min(mndist, mmd);
            if (md < mmd)
                r = midmid;
            else
                l = mid;
        }
        printf("Case %d: %.4lf\n", ++cases, sqrt(mndist));
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1627 - Team them up

Problem

現在有 2 個 team，每個 team 至少一個成員，同一個 team 成員之間必然會互相認識，不同 team 的成員之間則不一定。

給定他們互相認識的關係圖，請問他們可以分屬的 team 的情況，並且輸出 team 人數差距最少的那一組。

Sample Input

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

Sample Output

1
2
3
4
No solution
3 1 3 5
2 2 4

Solution

對於不認識的兩個人，保證他們在不同的 team。

取補圖，建造相互不認識的兩個人的關係圖，對於每一個 component 做二分圖判定，找到每個二分圖的兩個集合大小。

對於每一個二分圖結果，使用背包問題的解法，將兩個 team 的總數劃分均勻。

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
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXN 128
int g[MAXN][MAXN], visited[MAXN];
int color[MAXN], n;
int dfs(int u, int c, vector<int> &s0, vector<int> &s1) {
    visited[u] = 1, color[u] = c;
    if (c == 0)	s0.push_back(u);
    else		s1.push_back(u);
    for (int i = 1; i <= n; i++) {
        if ((!(g[u][i] == 1 && g[i][u] == 1)) && i != u) {
            if (visited[i] == 0) {
                if (!dfs(i, !color[u], s0, s1))
                    return 0;
            } else {
                if (color[u] == color[i])
                    return 0;
            }
        }
    }
    return 1;
}
int main() {
    int testcase, x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        while (getchar() != '\n');
        memset(g, 0, sizeof(g));
        memset(visited, 0, sizeof(visited));
        memset(color, 0, sizeof(color));
        for (int i = 1; i <= n; i++) {
            while (scanf("%d", &x) == 1 && x)
                g[i][x] = 1;
        }
        int ok = 1, m = 0;
        vector<int> s0[MAXN], s1[MAXN];
        for (int i = 1; i <= n; i++) {
            if (visited[i] == 0) {
                m++;
                ok &= dfs(i, 0, s0[m], s1[m]);
            }
        }
        if (!ok) {
            puts("No solution");
        } else {
            int dp[MAXN][MAXN] = {}, from[MAXN][MAXN] = {};
            dp[0][0] = 1;
            for (int i = 1; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    if (dp[i - 1][j]) {
                        dp[i][j + s0[i].size()] = 1;
                        dp[i][j + s1[i].size()] = 1;
                        from[i][j + s0[i].size()] = 0;
                        from[i][j + s1[i].size()] = 1;
                    }
                }
            }
            int ch = -1;
            for (int i = n/2; i >= 1; i--) {
                if (dp[m][i])	ch = i, i = -1;
            }
            assert(ch > 0);
            vector<int> team1, team2;
            for (int i = m; i >= 1; i--) {
                if (from[i][ch] == 0) {
                    ch -= s0[i].size();
                    team1.insert(team1.end(), s0[i].begin(), s0[i].end());
                    team2.insert(team2.end(), s1[i].begin(), s1[i].end());
                } else {
                    ch -= s1[i].size();
                    team1.insert(team1.end(), s1[i].begin(), s1[i].end());
                    team2.insert(team2.end(), s0[i].begin(), s0[i].end());
                }
            }
            printf("%d", team1.size());
            for (int i = 0; i < team1.size(); i++)
                printf(" %d", team1[i]);
            puts("");
            printf("%d", team2.size());
            for (int i = 0; i < team2.size(); i++)
                printf(" %d", team2[i]);
            puts("");
        }
        if (testcase)	puts("");
    }
    return 0;
}
/*
2
5
3 4 5 0
1 3 5 0
2 1 4 5 0
2 3 5 0
1 2 3 4 0
5
2 3 5 0
1 4 5 3 0
1 2 5 0
1 2 3 0
4 3 2 1 0
*/
Read More +
解題區/解題區 - UVa

UVa 1390 - Interconnect

Problem

N 個城鎮之間一開始有一些邊相連，接著每次任挑兩個城鎮拉一條邊相連，請問期望值需要幾次才能將 N 個城鎮彼此相連成為一個連通元件。

原本彼此連通的城鎮，也有可能重複拉邊。

Sample Input

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

Sample Output

1
2
0.0 
1.5

Solution

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

對於狀態 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
#include <stdio.h> 
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
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) {
    sort(u.c.begin(), u.c.end());
    if (u.c.size() == 1)	return 0;
    
    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++) {
        self += u.c[i] * (u.c[i] - 1) / 2.0;
        total += u.c[i];
    }
    total = total * (total - 1) / 2.0;
    for (int i = 0; i < u.c.size(); i++) {
        for (int j = i+1; j < u.c.size(); j++) {
            state v = u;
            v.c[i] += v.c[j];
            v.c.erase(v.c.begin() + j);
            ret += u.c[i] * u.c[j] * 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;
    while (scanf("%d %d", &n, &m) == 2) {
        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) // root
                st.c.push_back(weight[i]);
        }
        printf("%lf\n", dfs(st));
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1383 - Harmony Forever

Problem

  • 加入一個數字 X 於陣列尾端
  • 找到序列中 mod Y 的最小值的數字 X 位置，如果有相同的，取最後加入的數字位置。

Sample Input

1
2
3
4
5
6
7
8
9
10
5 
B 1 
A 5 
B 10 
A 5 
A 40 
2 
B 1 
A 2
0

Sample Output

1
2
3
4
5
6
7
Case 1: 
1 
2 
1 
Case 2: 
1

Solution

怎麼想都沒有好的思路，最後還是用多次區間查找來完成這個最小值詢問。

每一次查詢區間 [0, Y - 1]、[Y, 2Y - 1]、[2Y, 3Y - 1] … 的最小值。

因此每一次會需要詢問 O(500000 / Y * log (500000))，當 Y 夠大的時候，效率會比直接搜索來得快，如果 Y 太小則直接搜索的效果會比較好，因為增加的數字 X 最多 40000 個。

閥值 5000。

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
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 524288
struct E {
    int value, index;
    E(int a = 0, int b = 0):
        value(a), index(b) {}
    bool operator<(const E &a) const {
        return value < a.value;
    }
};
E tree[(MAXN<<1) + 10];
int M;
void setTree(int s, int t) {
    int i;
    for(i = 2 * M - 1; i >= 0; i--) {
    	tree[i] = E(0x3f3f3f3f, 0);
    }
}
E query(int s, int t) {
    E ret(0x3f3f3f3f, 0);
    for(s = s + M - 1, t = t + M + 1; (s^t) != 1;) {
        if(~s&1)
            ret = min(ret, tree[s^1]);
        if(t&1)
            ret = min(ret, tree[t^1]);
        s >>= 1, t >>= 1;
    }
    return ret;
}
void update(int s, E v) {
    tree[s + M] = v;
    for (s = s + M; s > 0; s >>= 1)
        tree[s] = min(tree[s], v);
}
int main() {
    int n, x, cases = 0;
    char cmd[5];
    while (scanf("%d", &n) == 1 && n) {
        for (M = 1; M < 500000+2; M <<= 1);
        setTree(0, M);
        int B = 0;
        vector<int> BX;
        if (cases++)
            puts("");
        printf("Case %d:\n", cases);
        for (int i = 0; i < n; i++) {
            scanf("%s %d", cmd, &x);
            if (cmd[0] == 'B') {
                update(x + 1, E(x + 1, ++B));
                BX.push_back(x);
            } else {
                if (BX.size() == 0)
                    puts("-1");
                else if (x < 5000) {
                    int mn1 = 0x3f3f3f3f, mn2 = -1, u;
                    for (int i = BX.size() - 1; i >= 0; i--) {
                        u = BX[i]%x;
                        if (u == 0) {
                            mn1 = 0, mn2 = i + 1;
                            break;
                        }
                        if (u < mn1)
                            mn1 = u, mn2 = i + 1;
                    }
                    printf("%d\n", mn2);
                } else {
                    int mn1 = 0x3f3f3f3f, mn2 = -1;
                    for (int y = 0; y <= 500000; y += x) {
                        E t = query(y + 1, min(y + 1 + x - 1, 500000));
                        if (t.value - y < mn1 || (t.value - y == mn1 && t.index > mn2))
                            mn1 = t.value - y, mn2 = t.index;
                    }
                    printf("%d\n", mn2);
                }
            }
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1182 - Sequence Alignment

Problem

基因對齊的最大匹配問題，或者是說 minimum edit distance，最小編輯距離。

花費方案

  • 連續個 - 獲益 -1，也就是 ----- = -1、a--b--c = -2
  • 對齊 a - a 獲益 2。
  • 不對 a - b 獲益 0。 (這一個對法，題目沒有講，因此很容易掛 WA。)

Sample Input

1
2
3
4
5
2
AADDEFGGHC 
ADCDEGH 
ERTTHCBYNQC 
BEARTBCHQYN

Sample Output

1
2
9 
8

Solution

狀態 dp[i][j][a_str or b_str][prev gap/ no prev gap]

先將 a, b 反轉，靠右對齊不是重點！

考慮 a 字串 i 位置匹配到 b 字串 j 位置，然後考慮尾端的狀態，要不兩個都是字符，要不其中一個是 - 產生的 gap，而這個 gap 可能在 a 字串或者是 b 字串，如果已經存在 gap，放置時則不需要花費，反之額外增加花費。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
void inv(char s[], int n) {
    for (int i = 0, j = n-1; i < j; i++, j--)
        swap(s[i], s[j]);
}
int dp[64][64][2][2];
int main() {
    int testcase;
    char s1[64], s2[64];
    scanf("%d", &testcase);
    while (getchar() != '\n');
    while (testcase--) {
        gets(s1);
        gets(s2);
        int n1 = strlen(s1), n2 = strlen(s2);
        inv(s1, n1), inv(s2, n2);
        for (int i = 0; i <= n1; i++) {
            for (int j = 0; j <= n2; j++) {
                dp[i][j][0][0] = dp[i][j][0][1] = -0x3f3f3f3f;
                dp[i][j][1][0] = dp[i][j][1][1] = -0x3f3f3f3f;
            }
        }
        dp[0][0][0][1] = 0;
        dp[0][0][1][1] = 0;
        int ret = -0x3f3f3f3f;
        for (int i = 0; i <= n1; i++) {
            for (int j = 0; j <= n2; j++) {
                int v = max(dp[i][j][0][0], dp[i][j][0][1]);
                v = max(v, max(dp[i][j][1][0], dp[i][j][1][1]));
                dp[i+1][j+1][0][1] = max(dp[i+1][j+1][0][1], v);
                dp[i+1][j+1][1][1] = max(dp[i+1][j+1][1][1], v);
                if (s1[i] == s2[j]) {
                    dp[i+1][j+1][0][1] = max(dp[i+1][j+1][0][1], v + 2);
                    dp[i+1][j+1][1][1] = max(dp[i+1][j+1][1][1], v + 2);
                }
                dp[i+1][j][0][0] = max(dp[i+1][j][0][0], dp[i][j][0][0]);
                dp[i+1][j][0][0] = max(dp[i+1][j][0][0], dp[i][j][1][0] - 1);
                dp[i+1][j][0][0] = max(dp[i+1][j][0][0], dp[i][j][0][1] - 1);
                dp[i+1][j][0][0] = max(dp[i+1][j][0][0], dp[i][j][1][1] - 1);
                
                dp[i][j+1][1][0] = max(dp[i][j+1][1][0], dp[i][j][1][0]);
                dp[i][j+1][1][0] = max(dp[i][j+1][1][0], dp[i][j][0][0] - 1);
                dp[i][j+1][1][0] = max(dp[i][j+1][1][0], dp[i][j][0][1] - 1);
                dp[i][j+1][1][0] = max(dp[i][j+1][1][0], dp[i][j][1][1] - 1);
                if (j == n2 || i == n1) {
                    ret = max(ret, max(dp[i][j][0][0], dp[i][j][0][1]));
                    ret = max(ret, max(dp[i][j][1][0], dp[i][j][1][1]));
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
2
AADDEFGGHC
ADCDEGH
ERTTHCBYNQC
BEARTBCHQYN
3
ABC
ABC
ABC
AC
BAC
AC
*/
Read More +