解題區/解題區 - 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 +
解題區/解題區 - UVa

UVa 1108 - Mining Your Own Business

Problem

给定一个连通图，设置一个些安全点，使得其他任意一些节点崩塌后，其他点都能到一个安全点，问安全点最小数量和情况数

Sample Input

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

Sample Output

1
2
Case 1: 2 4
Case 2: 4 1

Solution

先找到所有割點，而一個連通元件上可能連接好幾個割點，對於這個連通元件而言，不論割點是否崩塌，它們仍然可以通到其他連通元件上的逃生口。

如果這個連通元件只有一個割點，則萬一割點崩塌，則連通元件中至少要有一個逃生口，而方法數就是 component.size()，因此會發現，只需要將只有一個割點的連通元件的方法數相乘即可。

對於沒有割點的連通元件而言，至少要設置兩個逃生口，只有一個逃生口會造成萬一逃生口崩塌而死掉的情況，特別考慮方法數 component.size() * (component.size() - 1) / 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
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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define MAXN 65536
vector<int> g[MAXN];
int visited[MAXN], vIdx, back[MAXN], depth[MAXN];
int cutPoint[MAXN];
void tarjan(int u, int p, int root) {
    back[u] = depth[u] = ++vIdx;
    visited[u] = 1;
    int son = 0;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!visited[v]) {
            tarjan(v, u, root);
            back[u] = min(back[u], back[v]);
            son++;
            if ((u == root && son > 1) || (u != root && back[v] >= depth[u]))
                cutPoint[u]++;
        } else if (v != p) {
            back[u] = min(back[u], depth[v]);
        }
    }
}
//
set<int> adjCutPt;
int comSize = 0;
void dfs(int u) {
    visited[u] = 1, comSize++;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (cutPoint[v])	adjCutPt.insert(v);
        if (cutPoint[v] || visited[v])
            continue;
        dfs(v);
    }
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    int n, m, x, y;
    int cases = 0;
    while(scanf("%d", &m) == 1 && m) {
        int used[MAXN] = {}, usedn = 0;
        for (int i = 0; i < MAXN; i++)
            g[i].clear();
        n = 0;
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            n = max(n, max(x, y));
            x--, y--;
            used[x] = used[y] = 1;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        for (int i = 0; i < n; i++)
            usedn += used[i];
        // find all cut point
        vIdx = 0;
        for (int i = 0; i < n; i++)
            visited[i] = cutPoint[i] = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i] && used[i])
                tarjan(i, -1, i);
        }
//		for (int i = 0; i < n; i++)
//			printf("%d ", cutPoint[i]);
//		puts("");
        // find each component adjacent one cut point, without any cut point.
        vector<int> D; 
        for (int i = 0; i < n; i++)
            visited[i] = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i] && !cutPoint[i]) {
                comSize = 0, adjCutPt.clear();
                dfs(i);
                if (adjCutPt.size() == 1)
                    D.push_back(comSize);
            }
        }
        long long ways = 1, mn = D.size();
        for (int i = 0; i < D.size(); i++)
            ways *= D[i];
        if (D.size() == 0)	ways = (long long) usedn * (usedn-1) / 2, mn = 2;
        printf("Case %d: %lld %lld\n", ++cases, mn, ways);
    }
    return 0;
}
/*
3
1 2
2 3
3 1
32
15 15
8 4
17 7
6 1
12 6
3 17
5 9
20 8
20 4
7 15
4 18
7 17
14 1
14 3
5 3
5 18
13 18
5 15
1 13
18 3
2 4
20 4
20 16
5 20
2 3
10 4
6 6
13 16
2 7
6 17
14 14
1 15
33
10 12
17 14
19 3
2 3
19 9
17 16
9 2
8 9
6 8
14 10
3 13
14 4
9 3
1 18
10 7
15 14
13 1
15 1
16 6
14 20
12 7
6 17
19 5
19 1
10 13
5 3
18 6
12 17
4 5
9 18
9 17
9 20
15 15
*/
Read More +
解題區/解題區 - UVa

UVa 1011 - Crossing the Desert

Problem

在一個沙漠中，有 N 個綠洲，每一個綠洲只有水源可以獲取使用，食物可以從起點城鎮帶過來存放，但是綠洲本身不帶有食物獲取，每走一步將會損耗單位水和食物，身上負重最多 W，你可以攜帶一部分食物放置在綠洲，然後走回起點再帶食物過來存放，要推進到終點，至少要從城鎮中購買多少食物。

Sample Input

1
2
3
4
5
6
7
8
9
4 100
10 -20
-10 5
30 15
15 35
2 100
0 0
100 100
0 0

Sample Output

1
2
3
Trial 1: 136 units of food
Trial 2: Impossible

Solution

很簡單想的，我們只能從終點逆推回來，我們考慮綠洲 u 到終點 end 的最少食物花費 cost_u，現在考慮從 v 點到 u 再到 end，如果 cost_u 加上 e(v, u) 的花費不超過負重，則可以得知直接從 v 攜帶 cost_u 的食物量。

如果 cost_u 太大，則表示必須來來往往於 u, v 之間，而每一趟 v->u->v，攜帶路徑花費 1 倍水、 2 倍食物 (在 u 那邊打水即可)，剩下的空間為一次運送的食物量 (放置在 u 儲存)。最後一趟，則不考慮回程，額外可以增加攜帶食物量。

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
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
#define eps 1e-8
int main() {
    int n, m;
    int cases = 0;
    while (scanf("%d %d", &n, &m) == 2 && n+m) {
        double x[50], y[50];
        double g[50][50];
        double dp[50];
        int used[50] = {};
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x[i], &y[i]);
            dp[i] = 1e+6;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                double d = hypot(x[i] - x[j], y[i] - y[j]);
                g[i][j] = d;
            }
        }
        dp[n-1] = 0;
        for (int i = 0; i < n; i++) {
            int u = -1;
            for (int j = 0; j < n; j++) {
                if (used[j] == 0 && (u == -1 || dp[u] > dp[j]))
                    u = j;
            }
            used[u] = 1;
            for (int j = 0; j < n; j++) {
                if (used[j])	continue;
                double w = g[u][j];
                if (m >= dp[u] + 2 * w)
                    dp[j] = min(dp[j], dp[u] + w);
                else if (m >= 3 * w) {
                    int times = ceil((dp[u] - (m - 2 * w))/ (m - 3 * w));
                    dp[j] = min(dp[j], dp[u] + times * (2 * w) + w);
                }
            }
        }
        printf("Trial %d: ", ++cases);
        if (dp[0] != 1e+6)
            printf("%.0lf units of food\n", ceil(dp[0]));
        else
            puts("Impossible");
        puts("");
    }
    return 0;
}
/*
4 100
10 -20
-10 5
30 15
15 35
2 100
0 0
100 100
0 0
*/
Read More +