解題區/解題區 - UVa

UVa 10729 - Treequivalence

Problem

給一個平面圖的樹，請問是否同構，每一個節點相鄰的邊將會按照逆時針的順序給定。

Sample Input

1
2
3
4
5
2
A(B(C,D),E)
E(A,B(C,D))
A(B(C,D),E)
E(A(B(C,D)))

Sample Output

1
2
different
same

Solution

這一題與 UVa 12489 - Combating cancer 有點不同，這一題限制在平面圖，因此邊的紀錄是有順序性的。而題目不僅要求結構相同，同時在節點上面的 label 也要相同。

但是只要固定一個當作根，成為一個有根樹，那麼在最小表示法中，除了根的分支可以旋轉外，其餘的節點的分支都不能旋轉。因此固定其中一棵樹的根節點，接著窮舉另外一棵樹哪個節點作為根節點，分別找到最小表示法進行比對即可。

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
#include <stdio.h> 
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
// special !!!!!!!! normal planar representation
class Tree {
    public:
    vector<int> g[10005];
    char label[10005];
    int n;
    map<vector<int>, int> tmpR;
    int dfsMinExp(int u, int p) {
        vector<int>	branch;
        for(int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if(v == p)	continue;
            branch.push_back(dfsMinExp(v, u));
        }
        sort(branch.begin(), branch.end());
    
        int a = 63689, b = 378551;
        int ret = 0;
        branch.push_back(label[u]);
        for(int i = 0; i < branch.size(); i++)
            ret = ret * a + branch[i], a *= b;
        return ret;
    }
    vector<int> getTreeMinExp() { // simple (no plane)
        if(n == 1)	return vector<int>(1, (int)label[1]);
        int deg[10005] = {}, u, v;
        int topo[10005] = {}, idx = 0;
        queue<int> Q;
        for(int i = 1; i <= n; i++) {
            deg[i] = g[i].size();
            if(deg[i] == 1)	Q.push(i);
        }
        while(!Q.empty()) {
            u = Q.front(), Q.pop();
            topo[idx++] = u;
            for(int i = 0; i < g[u].size(); i++) {
                v = g[u][i];
                if(--deg[v] == 1)
                    Q.push(v);
            }
        }
        vector<int> ret;
        ret.push_back(dfsMinExp(topo[idx-1], -1));
        ret.push_back(dfsMinExp(topo[idx-2], -1));
        return ret;
    }
    
    int dfsCheck(Tree& tree, int u, int p) {
        vector<int> branch;
        if (p < 0) { // root
            for (int i = 0; i < tree.g[u].size(); i++) {
                int v = tree.g[u][i];
                branch.push_back(dfsCheck(tree, v, u));
            }
            
            int idx = 0, bn = branch.size();
            for (int s = 1; s < bn; s++) { // find cycle minExp
                for (int i = idx, j = s, k = 0; k < bn; k++) {
                    if (branch[i] != branch[j]) {
                        if (branch[j] < branch[i])	idx = s;
                        break;
                    }
                    if (++i >= bn)	i = 0;
                    if (++j >= bn)	j = 0;
                }
            }
            rotate(branch.begin(), branch.begin() + idx, branch.end());
        } else {
            int idx;
            for (idx = 0; tree.g[u][idx] != p; idx++);
            
            while (true) {
                idx++;
                if (idx >= tree.g[u].size())
                    idx = 0;
                int v = tree.g[u][idx];
                if (v == p)	break;
                branch.push_back(dfsCheck(tree, v, u));
            }
        }
        branch.push_back(-tree.label[u]);
        int &ret = tmpR[branch];
        if (ret == 0)	ret = tmpR.size();
        return ret;
    }
    int equal(Tree &other) { // normal planar representation
        if (n != other.n)	return 0;
        tmpR.clear();
        int b = dfsCheck(other, 1, -1);
        for (int i = 1; i <= n; i++) {
            int a = dfsCheck(*this, i, -1);
            if (a == b)
                return 1;
        }
        return 0;
    }
    void init(int N) { 
        for (int i = 0; i <= N; i++)
            g[i].clear();
        n = 0;
    } 
    int read(int p) {
        int x = ++n;
        char c;
        if (p >= 0)	g[x].push_back(p);
        scanf(" %c%c", &label[x], &c);
        if (c != '(') {
            ungetc(c, stdin);
            return x;
        }
        do {
            g[x].push_back(read(x));
            if (scanf("%c", &c) != 1 || c != ',')
                break;
        } while (true);
        return x;
    }
} tree1, tree2;
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        tree1.init(256); tree2.init(256);
        tree1.read(-1); tree2.read(-1);
        int same = tree1.equal(tree2);
        puts(same ? "same" : "different");
    }
    return 0;
}
/*
2
A(B(C,D),E)
E(A,B(C,D))
A(B(C,D),E)
E(A(B(C,D)))
9999
S(Y(Y(O),U(N(S,E,R(D)))))
D(R(N(U(Y(Y(O),S)),S,E)))
*/
Read More +
解題區/解題區 - UVa

UVa 10335 - Ray Inside a Polygon

Problem

給一個凸多邊形，接著再給定一射線的起始位置和角度，請問經過 m 次反射後的位置為何？如果射線打入凸多邊形的端點時，視如射線遺失。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
4 4
2.00 0.00 0.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
4 0
2.00 0.00 45.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
0 0

Sample Output

1
2
lost forever...
4.00 2.00

Solution

模擬每一步的射線可能打入的凸邊形的邊，因此每一次反射將要窮舉所有邊，查看是否存在線段與射線相交，如果發現此一可能再找到下一個反射線的起點與方向向量。

找到反射線的起點很簡單，直接用線段交即可找到，問題是在於方向向量怎麼計算，如果是用角度旋轉會造成嚴重的誤差。因此先把射線起點投影到線段上，接著再打到對稱點，然後從對稱點拉到交點得到方向向量，這麼做會降低嚴重的誤差問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
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
// I hate it, more eps adjust. 
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    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;
    }
    double length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
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 cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
//		angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}
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);
}
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
int same(Pt a, Pt b) {
    return fabs(a.x - b.x) < 0.005 && fabs(a.y - b.y) < 0.005;
}
int main() {
    Pt p[32];
    double theta;
    int n, m;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        Pt S, lvec;
        S.read();
        scanf("%lf", &theta);
        theta = theta * pi / 180;
        lvec = Pt(cos(theta), sin(theta));
        for (int i = 0; i < n; i++) // anti-clockwise
            p[i].read();
        
        int lost = 0;
        Seg on;
        for (int i = 0, j = n-1; i < n; j = i++) {
            Seg b(p[j], p[i]);
            if (onSeg(b.s, b.e, S))
                on = b;
        }
        for (int it = 0; it <= m; it++) { // #reflect.
            Seg pick = on, a(S, S + lvec);
            for (int i = 0, j = n-1; i < n; j = i++) {
                Seg b(p[j], p[i]);
                if (cmpZero(cross(a.s, a.e, b.s)) * cmpZero(cross(a.s, a.e, b.e)) <= 0) {
                    if (b != pick) {
                        pick = b;
                        break;
                    }
                }
            }
            Pt poj = getIntersect(pick, Seg(S, S + Pt(pick.s.y - pick.e.y, pick.e.x - pick.s.x)));
            Pt sym = S + (poj - S) * 2;
            S = getIntersect(a, pick);	
            lvec = S - sym;			
//			printf("%lf %lf %lf %lf\n", pick.s.x, pick.s.y, pick.e.x, pick.e.y);
//			printf("%lf %lf\n", S.x, S.y);
            if (same(S, pick.s) || same(S, pick.e)) {
                lost = 1;
                break;
            }
//			double r;
//			if (dot(pick.e - pick.s, lvec) <= 0)
//				r = getAngle(lvec, pick.e - pick.s);
//			else
//				r = getAngle(lvec, pick.s - pick.e);
//			lvec = rotateRadian(lvec, 2 * r);
            on = pick;
//			printf("it %d: %lf %lf\n", it, S.x, S.y);
//			printf("%lf %lf %lf %lf\n", lvec.x, lvec.y, poj.x, poj.y);
        }
        if (lost)
            puts("lost forever...");
        else {
            if (fabs(S.x) < eps && S.x < 0)
                S.x = - S.x;
            if (fabs(S.y) < eps && S.y < 0)
                S.x = - S.y;
            printf("%.2lf %.2lf\n", S.x, S.y);
        }
    }
    return 0;
}
/*
4 4
2.00 0.00 0.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
4 0
2.00 0.00 45.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
3 501
10.99 109 0
10 10
11 110
11 10
3 0
1 0 91
0 0
5 5
5 0
3 1
1 0 91
0 0
5 5
5 0
3 2
1 0 91
0 0
5 5
5 0
0 0
*/
Read More +
解題區/解題區 - UVa

UVa 12684 - VivoParc

Problem

動物園的 4 種動物配置，動物都有地域性，不希望相鄰的地方會具有與自己相同的物種。

給一個 graph，最多用四個顏色著色，使得相鄰不同色，輸出任意種方案即可。

Sample Input

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

Sample Output

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

Solution

看起來 N 還算大，窮舉順序會稍微影響速度，依序窮舉節點，檢查是否存在相鄰同色。由於不曉得是不是只有一個連通元件，連通元件分開找解，防止浪費時間的搜索。

接著根據 bfs 順序進行窮舉，來加快退回的速度。事實上也發現到四色問題如果保證有解，事實上應該很容易找到其中一組解。

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 <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> g[128];
int visited[128];
int A[128], An, color[128];
int used[128];
int dfs(int idx) {
    if (idx == An)
        return 1;
    for (int c = (idx == 0 ? 4 : 1); c <= 4; c++) {
        int u = A[idx], v, ok = 1;
        for (int i = 0; i < g[u].size() && ok; i++) {
            v = g[u][i];
            if (used[v] && color[v] == c)
                ok = 0;
        }
        if (ok) {
            used[u] = 1;
            color[u] = c;
            if (dfs(idx+1))
                return 1;
            used[u] = 0;
        }
    }
    return 0;
}
void bfs(int st) {
    queue<int> Q;
    int u;
    An = 0;
    Q.push(st), visited[st] = 1;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        A[An++] = u;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (visited[v] == 0) {
                visited[v] = 1;
                Q.push(v);
            }
        }
    }
    memset(used, 0, sizeof(used));
    dfs(0);
}
int main() {
    char line[128];
    int x, y, n, cases = 0;
    while (scanf("%d", &n) == 1) {
        while (getchar() != '\n'); 
        for (int i = 0; i <= n; i++)
            g[i].clear();
        while (gets(line)) {
            if (line[0] == '\0')
                break;
            sscanf(line, "%d-%d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        for (int i = 1; i <= n; i++) {
            sort(g[i].begin(), g[i].end());
            g[i].resize(distance(g[i].begin(), unique(g[i].begin(), g[i].end())));
        }
        memset(visited, 0, sizeof(visited));
        for (int i = 1; i <= n; i++) {
            if (visited[i] == 0) {
                bfs(i);
            }
        }
        if (cases++)	puts("");
        for (int i = 1; i <= n; i++)
            printf("%d %d\n", i, color[i]);
    }
    return 0;
}
/*
8
1-2
3-1
4-5
4-8
1-7
1-4
7-1
2-4
1-8
6-7
2-3
1-5
1-6
7-6
7-8
2-5
7-1
3-4
5-6
7-8
*/
Read More +
解題區/解題區 - UVa

UVA 12763 - Dicey Dice

Problem

有兩個玩家 A, B，盤面上有三個骰子，先手先挑一個骰子出來，後手再從剩餘兩個骰子中挑一個。接著兩個人會分別骰出點數，骰出最大的那個玩家獲勝，如果骰出一樣點數則平手

給予先手玩家，和三個六面骰子，請問獲勝機率高的玩家為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
3
A
1 1 1 1 1 1
2 3 2 4 5 3
6 6 6 6 6 6
A
4 3 7 9 2 5
8 1 4 6 9 2
6 5 1 8 3 7
B
1 2 3 4 4 4
1 2 3 4 4 4
1 2 3 4 4 4

Sample Output

1
2
3
A
B
fair

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    int testcase;
    char s[10];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", s);
        int player = s[0] - 'A';
        int dice[3][6];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 6; j++) {
                scanf("%d", &dice[i][j]);
            }
        }
        double rmx = 0, rmx2 = 1;
        for (int i = 0; i < 3; i++) { // A player pick
            double mx = 1, mx2 = 0;
            for (int j = 0; j < 3; j++) { // B player pick
                if (i == j)	continue;
                int pa = 0, pb = 0;
                for (int p = 0; p < 6; p++) {
                    for (int q = 0; q < 6; q++) {
                        pa += dice[i][p] > dice[j][q];
                        pb += dice[i][p] < dice[j][q];
                    }
                }
                
                if (mx > pa / 36.0 || (mx == pa / 36.0 && mx2 < pb/36.0)) {
                    mx = pa /36.0;
                    mx2 = pb / 36.0;
                }
            }
            if (rmx < mx || (rmx == mx && rmx2 > mx2)) {
                rmx = mx;
                rmx2 = mx2;
            }
        }
        if (rmx > rmx2)
            printf("%c\n", player + 'A');
        else if (rmx < rmx2)
            printf("%c\n", 1 - player + 'A');
        else
            printf("fair\n");
//			printf("%lf %lf\n", rmx, rmx2);
    }
    return 0;
}
/*
3
A
1 1 1 1 1 1
2 3 2 4 5 3
6 6 6 6 6 6
A
4 3 7 9 2 5
8 1 4 6 9 2
6 5 1 8 3 7
B
1 2 3 4 4 4
1 2 3 4 4 4
1 2 3 4 4 4
*/
Read More +
解題區/解題區 - UVa

UVa 12769 - Kool Konstructions

Problem

有一長度為 n 的都市地帶，每一次將會做區段的都市更新，將建築物都增加高度 v。

操作

  • B X Y V ： 將區間 [X, Y] 都增加 V 高度
  • Q X ： 詢問當前位置 X 的建築物高度為何

(題目中的圖示貌似有錯誤)

Sample Input

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

Sample Output

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

Solution

想要區間更新、單點查詢，有兩種方案 segment tree 附加懶操作、或者 binary indexed tree、最後是塊狀鏈表這幾種方式。這裡使用 binary indexed tree。雖然 binary indexed tree 原本的操作是單點修改，前綴總和查找。利用這一點完成區間修改的操作。

由於這一題還是單純的加法，那麼符合加法原則，當區間修改 B X Y V 時，相當於修改單點 Arr[X] += V，Arr[Y+1] -= V，從前綴和 SUM[1...Z] = \sum Arr[i]來看，保證只有區間 [X, Y] 的詢問增加了 V 值，其他保持不變。

單筆操作都是 O(log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h> 
#include <string.h> 
#define MAXN 100000
int BIT[MAXN + 5];
void modify(int x, int val, int L) {
    while (x <= L) {
        BIT[x] += val;
        x += x&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += BIT[x];
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int n, a, b, y;
    char cmd[8];
    while (scanf("%d", &n) == 1 && n) {
        memset(BIT, 0, sizeof(BIT));
        for (int i = 0; i < n; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'B') {
                scanf("%d %d %d", &a, &b, &y);
                modify(a, y, MAXN);
                modify(b + 1, -y, MAXN);
            } else {
                scanf("%d", &a);
                int ret = query(a);
                printf("%d\n", ret);
            }
        }
    }
    return 0;
}
/*
9
B 5 5 2
B 8 8 2
B 10 13 1
Q 8
B 8 13 1
Q 8
B 15 16 1
B 2 10 1
Q 8
9
B 5 5 2
B 8 8 2
B 10 13 1
Q 8
B 8 13 1
Q 8
B 15 16 1
B 2 10 1
Q 8
0
*/
Read More +
解題區/解題區 - UVa

UVa 745 - Numeric Puzzles Again

Problem

給定七巧板拼圖，保證每一個拼圖都會在最後的盤面上，並且每一個拼圖不可旋轉。

但是在輸出的時候，選擇一個最大權重的表示法進行輸出，同時每組測資保證最多一種同構解。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
7
6
3333
33
3333
 33
 33
7  7
7  7
7777
88888
 6
666
 66
  22
222
  2
  5
 55
 55
555
5 5
#
0

Sample Output

1
2
3
4
5
6
7
8777333
8733333
8733323
8777323
8655222
6665552
6655555

Solution

轉換成精準覆蓋問題，套用 DLX 做法來完成。

特別小心輸出的表示法，計算權重時，有可能會有嚴重的 overflow，可以用大數比大小、或者 double 來完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
char pattern[32][4][32][32]; // [id][rotate][x][y]
char prob_out[4][32][32], out[32][32];
int n, m;
int mx[30];
void out_update() {
    int mxrt = -1;
    for (int rt = 1; rt < 4; rt++) {
        for (int p = 0; p < n; p++) {
            for (int q = 0; q < n; q++) {
                prob_out[rt][p][q] = prob_out[rt-1][q][n - 1 - p];
            }
        }
    }
    for (int rt = 0; rt < 4; rt++) {
        int sum[30] = {};
        for (int p = 0; p < n; p++) {
            for (int q = 0; q < n; q++)
                sum[q] += prob_out[rt][p][n - q - 1] - '0';
        }
        for (int p = 0; p < 29; p++)
            sum[p+1] += sum[p]/10, sum[p] %= 10;
        int flag = 0;
        for (int p = 29; p >= 0; p--) {
            if (sum[p] != mx[p]) {
                flag = sum[p] > mx[p] ? 1 : -1;
                break;
            }
        }
        if (flag == 1) {
            for (int p = 29; p >= 0; p--)
                mx[p] = sum[p];
            mxrt = rt;
        }
    }
    if (mxrt >= 0) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) 
                out[i][j] = prob_out[mxrt][i][j];
    }
}
class DLX {
    public:
    struct DancingLinks {
        int left, right, up, down, ch;
        int id, rotate, px, py; // extra data
    } DL[131072 + 256];
    int s[512], o[512], head, size;		
    void remove(int c) {
        DL[DL[c].right].left = DL[c].left;
        DL[DL[c].left].right = DL[c].right;
        int i, j;
        for(i = DL[c].down; i != c; i = DL[i].down) {
            for(j = DL[i].right; j != i; j = DL[j].right) {
                DL[DL[j].down].up = DL[j].up;
                DL[DL[j].up].down = DL[j].down;
                s[DL[j].ch]--;
            }
        }
    }
    void resume(int c) {
        int i, j;
        for(i = DL[c].down; i != c; i = DL[i].down) {
            for(j = DL[i].left; j != i; j = DL[j].left) {
                DL[DL[j].down].up = j;
                DL[DL[j].up].down = j;
                s[DL[j].ch]++;
            }
        }
        DL[DL[c].right].left = c;
        DL[DL[c].left].right = c;
    }
    int found;
    void print(int dep) {
        for (int i = 0; i < dep; i++) {
            int id = DL[o[i]].id, rt = DL[o[i]].rotate;
            int px = DL[o[i]].px, py = DL[o[i]].py;
            for (int p = 0; p < n; p++) {
                for (int q = 0; q < n; q++) {
                    if (pattern[id][rt][p][q] != ' ')
                        prob_out[0][px + p][py + q] = pattern[id][rt][p][q];
                }
            }
        }
        out_update();
    }
    void dfs(int dep) {
        if (found) return;
        if (DL[head].right == head) {
        	print(dep);
            found++;
            return;
        }
        int tmp = 0x3f3f3f3f, c, i, j;
        for(i = DL[head].right; i != head; i = DL[i].right)
            if(s[i] < tmp)
                tmp = s[i], c = i;
        remove(c);
        for(i = DL[c].down; i != c; i = DL[i].down) {
            o[dep] = i;
            for(j = DL[i].right; j != i; j = DL[j].right)
                remove(DL[j].ch);
            dfs(dep+1);
            for(j = DL[i].left; j != i; j = DL[j].left)
                resume(DL[j].ch);
        }
        resume(c);
    }
    int getnode(int u, int d, int l, int r) {
        DL[size].up = u, DL[size].down = d;
        DL[size].left = l, DL[size].right = r;
        DL[u].down = DL[d].up = DL[l].right = DL[r].left = size;
        assert(size < 131072);
        return size++;
    }
    void newrow(int r[], int rn, int id, int rotate, int px, int py) {
        int i, j, h;
        for(i = 0; i < rn; i++) {
            DL[size].ch = r[i], s[r[i]]++;
            DL[size].id = id; // extra data
            DL[size].rotate = rotate; // extra data
            DL[size].px = px; // extra data
            DL[size].py = py; // extra data
            if(i) {
                j = getnode(DL[DL[r[i]].ch].up, DL[r[i]].ch, DL[h].left, h);
            } else {
                h = getnode(DL[DL[r[i]].ch].up, DL[r[i]].ch, size, size);
            }
        }
    }
    void init(int c) {// total column
        size = 0;
        head = getnode(0,0,0,0);
        int i;
        for(i = 1; i <= c; i++) {
            getnode(i, i, DL[head].left, head);
            DL[i].ch = i, s[i] = 0;
        }
    }
} DLX;
int validPos(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n; 
}
char in[32767][128];
int main() {
    while (scanf("%d %d", &n, &m) == 2 && n) {
        while (getchar() != '\n');
        DLX.init(n * n + m);
        
        int t = 0;
        while (gets(in[t]) && in[t][0] != '#') {
            t++;
        }
        memset(pattern, ' ', sizeof(pattern));
        
        int test = 0;
        for (int i = 0, idx = 0; i < m; i++) {
            int r = 0, c = 0;
            char label = -1;
            for (int j = 0; in[idx][j]; j++)
                if (in[idx][j] >= '0' && in[idx][j] <= '9')
                    label = in[idx][j];
                    
            for (r = 0; ; r++) {
                int ok = 0;
                for (int j = 0; in[idx][j]; j++)
                    if (in[idx][j] == label)
                        ok = 1;
                if (ok == 0)	break;
                for (int j = 0; in[idx][j]; j++) {
                    if (in[idx][j] == label) {
                        pattern[i][0][r][j] = in[idx][j];
                        c = max(c, j + 1);
                        test++;
                    }
                }
                idx++;
            }
            r = c = max(r, c);
            assert(r <= n && c <= n && r > 0);
            for (int rt = 1; rt < 4; rt++) {
                for (int p = 0; p < r; p++) {
                    for (int q = 0; q < c; q++) {
                        pattern[i][rt][p][q] = pattern[i][rt-1][q][r - 1 - p];
                    }
                }
            }
            for (int rt = 0; rt < 1; rt++) {
                for (int p = -20; p <= n; p++) { 
                    for (int q = -20; q <= n; q++) { // top-left corner
                        int ok = 1, row[512], rn = 0;
                        for (int p1 = 0; p1 < r && ok; p1++) {
                            for (int q1 = 0; q1 < c && ok; q1++) {
                                if (pattern[i][rt][p1][q1] != ' ') {
                                    ok &= validPos(p1 + p, q1 + q);
                                    row[rn++] = (p1 + p) * n + (q1 + q) + 1;
                                }
                            }
                        }
                        if (ok) {
                            row[rn++] = n * n + i + 1;
                            DLX.newrow(row, rn, i, rt, p, q);
                        }
                    }
                }	
            }
//			for (int kind = 0; kind < 4; kind++) {
//				for (int p = 0; p < r; p++, puts("")) {
//					for (int q = 0; q < c; q++)
//						printf("%c", pattern[i][kind][p][q]);
//				}
//				puts("---");
//			}
        }
        memset(mx, 0, sizeof(mx));
        DLX.found = 0;
        DLX.dfs(0);
        assert(DLX.found && test == n*n);
        if (DLX.found) {
            for (int i = 0; i < n; i++, puts("")) {
                for (int j = 0; j < n; j++) {
                    putchar(out[i][j]);
                    assert(out[i][j] != ' ');
                }
            }
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 738 - A Logical Problem

Problem

給予 AND, OR, NOT 結合的電路圖，保證最多 26 個變數，分別由大寫字母表示，接著對於每一組詢問輸出電路結果。

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
A-:\
  : )-?
B-:/
*
00000000000000000000000000
10000000000000000000000000
01000000000000000000000000
11000000000000000000000000
*
  +-A
  |
  +-:\
    : >o-:\
  +-:/   : )-?
  |+----o:/
B-+|
 C-+
*
00000000000000000000000000
11100000000000000000000000
*
A-:\
  : )-?
A-:/
*
00000000000000000000000000
10000000000000000000000000
*

Sample Output

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

Solution

不想轉化成 graph，那麼就直接針對盤面做遞迴分析，特別要記錄之前的方向位置，以免電路接錯路徑。而題目沒有說明 ? 銜接的方向，有可能四個方向都有。一開始沒有注意到這個問題，導致刷了很多 RE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <assert.h>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 512
char g[MAXN][MAXN], val[MAXN];
int n;
int validPos(int x, int y) {
    return x >= 0 && x < MAXN && y >= 0 && y < MAXN;
}
int query(int x, int y, int dir, char pre) {
    if (g[x][y] == '?')
        return query(x, y - 1, 2, '?');
    if (g[x][y] >= 'A' && g[x][y] <= 'Z')
        return val[g[x][y] - 'A'] - '0';
    if (g[x][y] == 'o')
        return !query(x, y - 1, 2, 'o');
    if (g[x][y] == ')')
        return query(x - 1, y - 3, 2, ')') && query(x + 1, y - 3, 2, ')');
    if (g[x][y] == '>')
        return query(x - 1, y - 3, 2, '>') || query(x + 1, y - 3, 2, '>');
    if (g[x][y] == '-') {
        if (dir == 2)
            return query(x, y - 1, 2, '-');
        if (dir == 3)
            return query(x, y + 1, 3, '-');
        assert(false);
    }
    if (g[x][y] == '|') {
        if (dir == 0)
            return query(x - 1, y, 0, '|');
        if (dir == 1)
            return query(x + 1, y, 1, '|');
        assert(false);
    }
    if (g[x][y] == '+') {
        if (dir != 1 && validPos(x-1, y) && g[x-1][y] == '|')
            return query(x - 1, y, 0, '|');
        if (dir != 0 && validPos(x+1, y) && g[x+1][y] == '|')
            return query(x + 1, y, 1, '|');
        if (dir != 3 && validPos(x, y-1) && g[x][y-1] == '-')
            return query(x, y - 1, 2, '-');
        if (dir != 2 && validPos(x, y+1) && g[x][y+1] == '-')
            return query(x, y + 1, 3, '-');
        assert(false);
    }
    assert(g[x][y] == ' ' && pre != '?');
    return 0;
}
int main() {
    memset(g, ' ', sizeof(g));
    while (gets(g[0])) {
        int qx = -1, qy = -1;
        for (n = 1; gets(g[n]) && g[n][0] != '*'; n++);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < MAXN; j++) {
                if (g[i][j] == '?') {
                    qx = i, qy = j;
                }
            }
        }
        
        int dir = -1;
        if (validPos(qx-1, qy) && g[qx-1][qy] == '|')
        	qx--, dir = 0;
        else if (validPos(qx+1, qy) && g[qx+1][qy] == '|') 
        	qx++, dir = 1;
        else if (validPos(qx, qy-1) && g[qx][qy-1] == '-') 
        	qy--, dir = 2;
        else if (validPos(qx, qy+1) && g[qx][qy+1] == '-') 
        	qy++, dir = 3;
        assert(qx >= 0 && qy >= 0);
        while (scanf("%s", val) == 1 && val[0] != '*')
            printf("%d\n", query(qx, qy, dir, '?'));
        puts("");
        memset(g, ' ', sizeof(g));
        while (getchar() != '\n');
    }
    return 0;
}
/*
A-:\
  : )-?
B-:/
*
00000000000000000000000000
10000000000000000000000000
01000000000000000000000000
11000000000000000000000000
*
  +-A
  |
  +-:\
    : >o-:\
  +-:/   : )-?
  |+----o:/
B-+|
 C-+
*
00000000000000000000000000
11100000000000000000000000
*
A-:\
  : )-?
A-:/
*
00000000000000000000000000
10000000000000000000000000
*
A-o:\
   : )o-?
A-o:/
*
00000000000000000000000000
10000000000000000000000000
*
        ? 
A-o:\   | 
   : )o-+
A-o:/
*
00000000000000000000000000
10000000000000000000000000
*
 */
Read More +
解題區/解題區 - UVa

UVa 12905 - Volume of Revolution

Problem

給定一個方程式，接著繞 x 軸旋轉，計算區間 [l, r] 的體積。

考慮積分與數值積分的情況，計算兩者之間計算的誤差。其中會給定數值積分在 x 軸劃分的依準，以及繞行 x 軸轉換要切幾等分。

Sample Input

1
2
3
2
2 1 -4 5 1 4 4 3
1 1 0 1 4 4 3

Sample Output

1
2
Case 1: 27.9042
Case 2: 36.3380

Solution

這題最麻煩就是計算椎台體積

在幾何學中，錐台又稱平截頭體，指的是圓錐或稜錐被兩個平行平面所截後，位於兩個平行平面之間的立體。根據所截的是圓錐還是稜錐，可分為圓台與稜台。

參照 wiki Frustum

兩平行的上下底面積 S1, S2，根據高度 h，得到體積 V = (S1 + S2 + sqrt(S1 * S2)) /3 * h。之後就模擬劃分計算體積。

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 <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
double P[32], Q[32];
const double pi = acos(-1);
#define eps 1e-6
void integral(double Q[]) {
    for (int i = 31; i >= 1; i--)
        Q[i] = Q[i-1] / (i);
    Q[0] = 0;
}
double calcVal(double Q[], double x) {
    double ret = 0;
    for (int i = 31; i >= 0; i--)
        ret = ret * x + Q[i];
    return ret;
}
int main() {
    int testcase, cases = 0;
    int n, slices, stacks;
    double a, b;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        memset(P, 0, sizeof(P));
        memset(Q, 0, sizeof(Q));
        for (int i = n; i >= 0; i--)
            scanf("%lf", &P[i]);
            
        scanf("%lf %lf", &a, &b);
        scanf("%d %d", &slices, &stacks);
        
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                Q[i+j] += P[i] * P[j];
        integral(Q);
        double trueVal = (calcVal(Q, b) - calcVal(Q, a)) * pi;
        double apprVal = 0;
        double dx = (b - a) / stacks, dtheta = 2 * pi / slices;
        for (double x = a; x + dx - eps <= b; x += dx) {
            double x1 = x, x2 = x + dx, x12;
            double fx1, fx2, S1, S2, fx12, S12;
            fx1 = calcVal(P, x1);
            fx2 = calcVal(P, x2);
            S1 = fx1 * fx1 * sin(dtheta) /2;
            S2 = fx2 * fx2 * sin(dtheta) /2;
            apprVal += dx * (S1 + S2 + sqrt(S1 * S2)) /3 * slices;
        }
        printf("Case %d: %.4lf\n", ++cases, fabs(trueVal - apprVal) * 100 / trueVal);
    }
    return 0;
}
/*
2
2 1 -4 5 1 4 4 3
1 1 0 1 4 4 3
*/
Read More +
解題區/解題區 - UVa

UVa 12904 - Load Balancing

Problem

給定一些學生的成績，希望建造一個分級制度，使得每一級的人數差距越少越好。

分級制度化分成 A, B, C, D 四級，每一級都是一個連續區間，假設現在有 N 個人，期望能將每一堆分成 N/4 個人，把每一堆人數與期望的 N/4 的差總和越小越好。

輸出字典順序最小的劃分方式。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
8
0
40
41
80
85
120
150
155
9
0
40
41
80
85
120
121
150
155

Sample Output

1
2
Case 1: 40 80 120
Case 2: 40 80 120

Solution

如何直接窮舉劃分線，想必也要消耗 O(160^3) 的時間。這花費太昂貴。

發現到每一個人的分數並不高，落在 0 - 160 之間的整數，那麼先統計每個分數有多少人。

接著考慮 dp[i][j] 前 i 個分級制度，劃分線為 j 的最小差總和。接著加入下一級，得到

1
dp[i+1][k+1] = min(dp[i+1][k+1], fabs(peopleCount[j, k] - avg) + dp[i][j]);

因此需要 O(4 * 160 * 160) 來完成。考慮輸出最小字典順序的劃分方式，一樣採用 dp 的思路，逆推回去查看是否能得到目標的最佳解，之後再順著被標記的路線走即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
#define MAXV 165
#define eps 1e-6
int main() {
    int testcase, n, x;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        int A[MAXV] = {};
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            A[x]++;
        }
        for (int i = 1; i < MAXV; i++)
            A[i] += A[i-1];
        double dp[5][MAXV];
        int used[5][MAXV] = {};
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < MAXV; j++) {
                dp[i][j] = 1e+30;
            }
        }
        dp[0][0] = 0;
        double avg = n/4.0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < MAXV; j++) {
                if (dp[i][j] == 1e+30)
                    continue;
                for (int k = j; k < MAXV; k++) {
                    int cnt = A[k] - (j ? A[j-1] : 0);
                    dp[i+1][k+1] = min(dp[i+1][k+1], fabs(cnt - avg) + dp[i][j]);
                }
            }
        }
        used[4][MAXV - 1] = 1;
        for (int i = 3; i >= 0; i--) {
            for (int j = 0; j < MAXV; j++) {
                if (dp[i][j] == 1e+30)
                    continue;
                for (int k = j; k < MAXV; k++) {
                    int cnt = A[k] - (j ? A[j-1] : 0);
                    if (fabs(fabs(cnt - avg) + dp[i][j] - dp[i+1][k+1]) < eps)
                        used[i][j] |= used[i+1][k+1];
                }
            }
        }
        
        printf("Case %d:", ++cases);
        
        int pos = 0;
        for (int i = 0; i < 3; i++) {
            for (int k = pos; k < MAXV; k++) {
                int cnt = A[k] - (pos ? A[pos-1] : 0);
                if (fabs(fabs(cnt - avg) + dp[i][pos] - dp[i+1][k+1]) < eps && used[i+1][k+1]) {
                    printf(" %d", k);
                    pos = k+1;
                    break;
                }
            }
        }
        puts("");
    }
    return 0;
}
/*
2
8
0
40
41
80
85
120
150
155
9
0
40
41
80
85
120
121
150
155
Case 1: 40 80 120
Case 2: 40 80 120
*/
Read More +
解題區/解題區 - UVa

UVa 12897 - Decoding Baby Boos

Problem

每一個主字串，接著根據一大堆規則， 依序 將字母做替換。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
AVVU_TUMI_COLING_PARO_NAY
3
B V
D L
H Y
AABBCCY
3
A B
B C
C A

Sample Output

1
2
ABBU_TUMI_CODING_PARO_NAH
CCCCBBY

Solution

由於主字串可能很長，不用針對每次詢問將每一個主字串都拿來修改。只需考量每一種字符轉換的可能，例如源頭 ‘A’ -> ‘Z’, ‘B’ -> ‘X’, ‘C’ -> ‘Z’, … 那麼，接下來遇到 ‘Z’ -> ‘W’，只需要針對 ‘A’ -> ‘W’, ‘C’ -> ‘W’ 即可。

因此，每一次詢問最多消耗 O(26) 完成。

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
#include <stdio.h> 
#include <string.h>
using namespace std;
char s[1048576];
int main() {
    int testcase, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", s);
        scanf("%d", &n);
        
        char R[128], s1[10], s2[10];
        for (int i = 0; i < 128; i++)
            R[i] = i;
        for (int i = 0; i < n; i++) {
            scanf("%s %s", s1, s2);
            for (int j = 'A'; j <= 'Z'; j++)
                if (R[j] == s2[0])
                    R[j] = s1[0];
        }
        
        for (int i = 0; s[i]; i++)
            putchar(R[s[i]]);
        puts("");
    }
    return 0;
}
/*
2
AVVU_TUMI_COLING_PARO_NAY
3
B V
D L
H Y
AABBCCY
3
A B
B C
C A
*/
Read More +