解題區/解題區 - UVa

UVa 12862 - Intrepid climber

Problem

從山頂往下爬不需要花費，往上爬則要根據給定的邊上的花費計算。現在有朋友在特定的點上，找到一條花費最少的路徑。(花費計算到抵達最後一個朋友的所在地，不用特地返回山頂。)

給定的圖為一棵樹。

Sample Input

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

Sample Output

1
2
3
2
2
0

Solution

如果把最後停留的點再走回去山頂，則會構成一個尤拉環道，而在這一題可以觀察出這個尤拉環道的花費是固定的。

那麼要找停留的地方，必然是扣除返回山頂的最大花費，這樣就能找到拜訪所有朋友的最小花費。對於某些朋友可能不是在葉節點，如果其子樹內沒有朋友，就可以不用走訪。概念上，需要將這個樹稍微壓縮一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
vector< pair<int, int> > g[131072];
int f[131072], w = 0, ret = 0;
void dfs(int u, int &friends, int dep) {
    int v, ff = 0, cost;
    friends = f[u];
    if (f[u])	ret = max(ret, dep);
    for (int i = 0; i < g[u].size(); i++) {
        v = g[u][i].first;
        dfs(v, ff, dep + g[u][i].second);
        if (ff > 0) {
            w += g[u][i].second;
            friends += ff;
        }
    }
}
int main() {
    int n, m, x, y, v;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 1; i <= n; i++)
            g[i].clear(), f[i] = 0;
        for (int i = 1; i < n; i++) {
            scanf("%d %d %d", &x, &y, &v);
            g[x].push_back(make_pair(y, v));
        }
        for (int i = 0; i < m; i++) {
            scanf("%d", &x);
            f[x] = 1;
        }
        w = 0, ret = 0;
        dfs(1, x, 0);
        printf("%d\n", w - ret);
    }
    return 0;
}
/*
6 2
1 2 2
2 4 2
1 3 3
3 6 3
3 5 1
5 2
4 2
1 2 2
1 3 1
3 4 2
2 4
4 2
1 4 1
1 3 1
4 2 2
2 4
*/
Read More +
解題區/解題區 - UVa

UVa 12861 - Help cupid

Problem

要配對情侶，但是每一個情侶在不同的 24 時區，告知在 24 個時區的情況，希望分配兩兩一組 (先不管男女、還是男男、女女)，配對花費就是兩個時區之間的差$min(|i-j|, 24 - |i-j|)$ (超過 12 小時，則會在另一個時段)，求總花費最小為何？

Sample Input

1
2
3
4
5
6
6
-3 -10 -5 11 4 4
2
-6 6
8
0 0 0 0 0 0 0 0

Sample Output

1
2
3
5
12
0

Solution

首先必須知道，配對的區間不會重疊，並且盡可能與自己同一時段的人匹配。

藉此直接把同一時段的倆倆匹配，因此在每一時區要不 0 要不 1 個人。

接著窮取 24 時區的匹配花費，其一定與相鄰的匹配，窮舉一下即可。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        int time[24] = {}, x;
        for (int i = 0; i < n; i++)
            scanf("%d", &x), time[x+11]++;
        for (int i = 0; i < 24; i++)
            time[i] = time[i]&1;
        int A[64], m = 0, ret = 0x3f3f3f3f;
        for (int i = 0; i < 24; i++)
            if (time[i])	A[m++] = i;
        for (int i = 0; i < m; i++)
            A[i + m] = A[i] + 24;
        if (m == 0)	ret = 0;
        for (int i = 0; i < m; i++) {
            int c = 0;
            for (int j = 0; j < m; j += 2)
                c += A[i+j+1] - A[i+j];
            ret = min(ret, c);
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
6
-3 -10 -5 11 4 4
2
-6 6
8
0 0 0 0 0 0 0 0
*/
Read More +
解題區/解題區 - UVa

UVa 12855 - Black and white stones

Problem

目標將所有的黑色 (B) 搬到最左邊。隨意位置交換兩元素成本為 A，相鄰交換成本為 B。

求花費最少為何？

Sample Input

1
2
3
4
5
6
2 1
BWWB
5 3
WBWWBWBWBWBBBWWBBB
1000000 0
W

Sample Output

1
2
3
2
27
0

Solution

很簡單地發現，隨意交換的時候，一定會去找相隔最遠的 W 和 B 進行交換。而相鄰交換的成本是推過去減少的逆序對數乘上 B。因此只要考慮 A 是否小於 B 乘上最遠兩端交換 減少的逆序對數 ，就一直使用隨意交換。直到不行，則全採用相鄰交換。

然而，我卡在 減少的逆序對數 ，不小心寫成總逆序對數。因此一直掛 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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    long long A, B;
    char s[8192];
    while (scanf("%lld %lld", &A, &B) == 2) {
        scanf("%s", s);
        B = A - B;
        int n = strlen(s);
        long long ret = 0;	
        long long inv = 0, w = 0, b = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'W')	w++;
            else				inv += w;
        }
        int fw = 0, fb = n;
        for (int i = 0; i < n; i++)
            if (s[i] == 'W')	fw = i, i = n;
        for (int i = n-1; i >= 0; i--)
            if (s[i] == 'B')	fb = i, i = -1;
        w = b = 0;
        for (int i = fw; i <= fb; i++)
            if (s[i] == 'W')	w++;
            else				b++;
        while (inv) {
            if ((w + b - 1) * B <= A) {
                ret += inv * B;
                inv = 0;
            } else {
                ret += A;
//				swap(s[fw], s[fb]);
                inv -= w + b - 1, w--, b--;
                fw++, fb--;
                while (fw <= fb && s[fw] != 'W')	fw++, b--;
                while (fb >= fw && s[fb] != 'B')	fb--, w--;
            }
        }
        printf("%lld\n", ret);
    } 
    return 0;
}
/*
2 1
BWWB
5 3
WBWWBWBWBWBBBWWBBB
1000000 0
W
5 5
BWBWBWBWBBWBWBWB
24 22
BWWWWBWWWWWBWWBBBBWBWBWWBWBWW
*/
Read More +
解題區/解題區 - UVa

UVa 12831 - Bob the Builder

Problem

一台機器，每一次能產出其 X 的子孫、子孫的子孫 … 類推。

不會產生重複的子孫，把所有可能性產生，請問使用機器的最少次數為何？

Sample Input

1
2
3
4
5
2
1 36
20
2 40
8 20

Sample Output

1
2
Case 1: 2
Case 2: 3

Solution

一開始誤解題目，以為一次可以將數個的子孫都產出來，實際上只能拿一個 X 進去，並且將其單一後代產出。

也就是說，會看到一個 DAG 圖中，用最少路徑覆蓋所有的節點。這題同時也需要非常快速的二分匹配，舊的模板大概沒辦法通過這一題，至於需不需要貪心預流？根據之前測試點數非常多的圖，貪心預流效果在這個二分匹配下沒有很好的反應？

  • 题意：
    有向无环图中，需要多少条简单路可以覆盖整个图。

  • 建模：
    构造二分图。把原图的每个顶点i拆分成二分图X，Y集合中的两个顶点Xi和Yi。对于原图的边(i, i)，连接(Xi, Yj)，值为1，然后把二分图最大匹配模型转化为网络留模型，求最大流。

  • 分析：

    对于一个路径覆盖，有如下性质：

    1、每个顶点属于且只属于一个路径。
    2、路径上除终点外，从每个顶点出发只有一条边指向路径上的另一顶点。

    所以我们可以把每个顶点理解成两个顶点，一个是出发，一个是目标，建立二分图模型。该二分图的任何一个匹配方案，都对应了一个路径覆盖方案。如果匹 配数为0，那么显然路径数=顶点数。每增加一条匹配边，那么路径覆盖数就减少一个，所以路径数=顶点数 - 匹配数。要想使路径数最少，则应最大化匹配数，所以要求二分图的最大匹配。

    注意，此建模方法求最小路径覆盖仅适用于有向无环图，如果有环或是无向图，那么有可能求出的一些环覆盖，而不是路径覆盖。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
#include <map>
using namespace std;
const int MAXV = 20010;
const int MAXE = MAXV * 300 * 2;
const int INF = 1<<29;
typedef struct Edge {
    int v, cap, flow;
    Edge *next, *re;
} Edge;
class MaxFlow {
    public:
    Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
    int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
    void Init(int x) {
        n = x, e = 0;
        for (int i = 0; i < n; ++i) adj[i] = NULL;
    }
    void Addedge(int x, int y, int flow){
        edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
        edge[e].re = &edge[e+1], adj[x] = &edge[e++];
        edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
        edge[e].re = &edge[e-1], adj[y] = &edge[e++];
        assert(x < MAXV && y < MAXV);
        assert(e < MAXE);
    }
    void Bfs(int v){
        int front = 0, rear = 0, r = 0, dis = 0;
        for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
        level[v] = 0, ++lvCnt[0];
        Q[rear++] = v;
        while (front != rear){
            if (front == r) ++dis, r = rear;
            v = Q[front++];
            for (Edge *i = adj[v]; i != NULL; i = i->next) {
                int t = i->v;
                if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
            }
        }
    }
    int Maxflow(int s, int t){
        int ret = 0, i, j;
        Bfs(t);
        for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
        for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
        i = s;
        while (level[s] < n){
            while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow)) 
                arc[i] = arc[i]->next;
            if (arc[i]){
                j = arc[i]->v;
                pre[j] = arc[i];
                i = j;
                if (i == t){
                    int update = INF;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        if (update > p->flow) update = p->flow;
                    ret += update;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        p->flow -= update, p->re->flow += update;
                    i = s;
                }
            }
            else{
                int depth = n-1;
                for (Edge *p = adj[i]; p != NULL; p = p->next)
                    if (p->flow && depth > level[p->v]) depth = level[p->v];
                if (--lvCnt[level[i]] == 0) return ret;
                level[i] = depth+1;
                ++lvCnt[level[i]];
                arc[i] = adj[i];
                if (i != s) i = pre[i]->re->v;
            }
        }
        return ret;
    }
} g;
int visited[32767], N, L;
vector<int> D;
void dfs(int u) {
    if (visited[u])	return ;
    visited[u] = 1, D.push_back(u);
    for (int i = 0; (1<<i) <= u; i++)	 {
        if ((u>>i)&1) {
            int v = u + (1<<i);
            if (v <= L) {
                dfs(v);
                g.Addedge(u, v + L, 1);
            }
        }
    }
}
int main() {
    int testcase, cases = 0;
    int x, y, u, v;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &L);
        assert(N > 0 && N <= 36);
        memset(visited, 0, sizeof(visited));
        D.clear();
        int A[10000 + 5];
        int source = 0, sink = 2 * L + 1;
        g.Init(2 * L + 5);
        for (int i = 0; i < N; i++) {
            scanf("%d", &A[i]);
            dfs(A[i]);
        }
        for (int i = 0; i < D.size(); i++) {
            g.Addedge(source, D[i], 1);
            g.Addedge(D[i] + L, sink, 1);
        }
        int ret = D.size() - g.Maxflow(source, sink);
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
} 
/*
99999
1 36
20
2 40
8 20
1 2
2
1 10
6
*/
Read More +
解題區/解題區 - UVa

UVa 12858 - Even distribution

Problem

帶小孩子出門旅遊，每到一個地方會得到指定個數的糖果，抵達時必須將糖果均分給每一個小孩才行，現在旅遊並沒有規劃路線，在所有的路線情況下，能攜帶的小孩子個數有多少種情況。

也就是在某些情況，例如攜帶質數個小孩出門，有可能怎麼走都沒辦法均分，而導致小孩之間爭奪糖果的情況。在同一種路線下，會盡可能攜帶最大量的小孩出門。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
2 1
1 9
1 2
4 2
1 2 3 4
1 3
1 2
4 3
30 42 105 70
2 4
1 2
2 3

Sample Output

1
2
3
2
4
11

Solution

Even distribution 均勻分布

對於每一個地方紀錄可以攜帶的小孩數量，用一個 set<int> 維護。

接著不斷地更新走到別的地點，路徑之間取 gcd 最大公因數，然後將所有地點的情況聯集起來即可。

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 <set>
#include <queue> 
#include <vector>
#include <algorithm>
using namespace std;
int C[65536];
vector<int> g[65536];
int search(int n) {
    set<int> S[65536], UNION;
    queue<int> Q, P;
    int u, v, p, gg;
    for (int i = 0; i < n; i++)
        Q.push(i), P.push(C[i]), S[i].insert(C[i]), UNION.insert(C[i]);
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        p = P.front(), P.pop();
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            gg = __gcd(p, C[v]);
            if (S[v].find(gg) == S[v].end()) {
                S[v].insert(gg), UNION.insert(gg);
                Q.push(v), P.push(gg);
            }
        }
    }
    int ret = UNION.size();
    return ret;
}
int main() {
    int n, m, x, y;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &C[i]);
            g[i].clear();
        }
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        printf("%d\n", search(n));
    }
    return 0;
}
/*
2 1
1 9
1 2
4 2
1 2 3 4
1 3
1 2
4 3
30 42 105 70
2 4
1 2
2 3
*/
Read More +
解題區/解題區 - UVa

UVa 12860 - Galaxy collision

Problem

給兩個星座，這兩個星座分別由很多個星星構成，並且在同一個星座的星星之間必須間隔至少大於 5 (歐幾里得距離)。

求其中一個星座最少有幾顆星星。保證輸入一定可以構成兩個星座。

Sample Input

1
2
3
4
5
6
7
8
9
10
6
1 3
9 1
11 7
5 7
13 5
4 4
2
10 10
50 30

Sample Output

1
2
2
0

Solution

看到兩個星座，就很像二分圖，把距離小於等於 5 的點之間連起來，接著二分圖黑白染色，對於每一個連通子圖會得到兩個集合。

根據貪心算法，將每一個連通圖的最小集合加總即可。

但是為了要快速建表，猜測輸入不會太集中，這會造成無法構成兩個星座，因此把圖根據 x 座標儲存，這麼一來只要搜索 [x-5, x+5] 之間的點集即可。

生測資也挺痛苦的。

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 <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
vector<int> g[65536];
vector< pair<int, int> > X[524288];
void buildGraph(int x) {
    int d;
    for (int i = X[x].size() - 1; i >= 0; i--) {
        int y = X[x][i].first, u = X[x][i].second;
        for (int j = x - 5; j <= x + 5; j++) {
            if (j < 0)	continue;
            int st = (int)(lower_bound(X[j].begin(), X[j].end(), make_pair(y - 5, -1)) - X[j].begin());
            for (int k = st; k < X[j].size(); k++) {
                if (X[j][k].first > y + 5)	break;
                d = (x-j) * (x-j) + (X[j][k].first - y) * (X[j][k].first - y);
//				d = abs(x-j) + abs(X[j][k].first - y);
                if (d <= 25) {
                    if (u != X[j][k].second) {
                        g[u].push_back(X[j][k].second);
//						printf("%d -> %d\n", u + 1, X[j][k].second + 1);
                    }
                }
            }
        }
    }
}
int visited[65536], dist[65536];
int bfs(int st) {
    queue<int> Q;
    int o[2] = {}, u, v;
    Q.push(st), dist[st] = 1, visited[st] = 1;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        o[dist[u]&1]++;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if (visited[v] == 0)  {
                dist[v] = dist[u] + 1;
                visited[v] = 1;
                Q.push(v);
            }
        }
    }
    return min(o[0], o[1]);
}
int main() {
    int n, x, y;
    while (scanf("%d", &n) == 1) {
        set<int> S;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            X[x].push_back(make_pair(y, i));
            S.insert(x);
            visited[i] = 0;
            g[i].clear();
        }
        for (set<int>::iterator it = S.begin();
            it != S.end(); it++)
            sort(X[*it].begin(), X[*it].end());
        for (set<int>::iterator it = S.begin();
            it != S.end(); it++)
            buildGraph(*it);
        int ret = 0;
        for (int i = 0; i < n; i++)
            if (visited[i] == 0)
                ret += bfs(i);
        printf("%d\n", ret);
        for (set<int>::iterator it = S.begin();
            it != S.end(); it++) {
            X[*it].clear();
        }
    }
    return 0;
}
/*
3
1 1
2 2
9 9
2
1 1
2 2
6
1 3
9 1
11 7
5 7
13 5
4 4
2
10 10
50 30
*/
Read More +
解題區/解題區 - UVa

UVa 12639 - Hexagonal Puzzle

Problem

每個六角形會有 1 ~ 6 的數字在每一條邊，可以旋轉六角形，但是相鄰的數字要相同。

請問是否可以拼出目標的形狀。

Sample Input

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

Sample Output

1
2
YES
NO

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
struct Hex {
    int v[6], m[7], rotate;
    int read() {
        for (int i = 0; i < 6; i++) {
            if (scanf("%d", &v[i]) == 1);
            else
                return 0;
        }
        return 1;
    }
    void normal() {
        int t[6], mnexp = 0;
        for (int i = 0; i < 6; i++)
            t[i] = v[i];
        for (int i = 1; i < 6; i++)
            if (t[i] == 1)	mnexp = i;
        for (int i = 0; i < 6; i++)
            v[i] = t[(mnexp + i)%6];
        for (int i = 0; i < 6; i++)
            m[v[i]] = i;
    }
    int getPos(int x) {
        return m[x];
    } 
    int next() {
        return v[(rotate+1)%6];
    }
    int prev() {
        return v[(rotate+5)%6];
    }
    void println() {
        for (int i = 0; i < 6; i++)
            printf("%d ", v[(rotate+i)%6]);
        puts("");
    }
};
int used[7], path[7];
Hex h[7];
int dfs(int idx) {
    if (idx == 7)
        return 1;
//	printf("%d\n", idx);
//	for (int i = 0; i < idx; i++) {
//		printf("%d : ", h[path[i]].rotate);
//		h[path[i]].println();
//	}
//	puts("--");
//	getchar();
    if (idx == 0) {
        for (int i = 0; i < 7; i++) {
            if (used[i] == 0) {
                used[i] = 1;
                path[idx] = i, h[i].rotate = 0;
                if (dfs(idx + 1))	return 1;
                used[i] = 0;
            }
        }
    } else {
        if (idx == 1) {
            for (int i = 0; i < 7; i++) {
                if (used[i] == 0) {
                    used[i] = 1;
                    path[idx] = i, h[i].rotate = h[i].getPos(h[path[0]].v[idx - 1]);
                    if (dfs(idx + 1))	return 1;
                    used[i] = 0;
                }
            }
        } else if (idx < 6) {
            for (int i = 0; i < 7; i++) {
                if (used[i] == 0) {
                    used[i] = 1;
                    path[idx] = i, h[i].rotate = h[i].getPos(h[path[0]].v[idx - 1]);
                    if (h[path[idx-1]].prev() == h[i].next())
                        if (dfs(idx + 1))	return 1;
                    used[i] = 0;
                }
            }
        } else {
            for (int i = 0; i < 7; i++) {
                if (used[i] == 0) {
                    used[i] = 1;
                    path[idx] = i, h[i].rotate = h[i].getPos(h[path[0]].v[idx - 1]);
                    if (h[path[idx-1]].prev() == h[i].next() && h[path[1]].next() == h[i].prev())
                        if (dfs(idx + 1))	return 1;
                    used[i] = 0;
                }
            }
        }
    }
    return 0;
}
int main() {
    while (true) {
        for (int i = 0; i < 7; i++) {
            if (!h[i].read())
                return 0;
            h[i].normal();
        }
        memset(used, 0, sizeof(used));
        int ret = dfs(0);
        puts(ret ? "YES" : "NO");
    }
    return 0;
}
/*
*/
Read More +
解題區/解題區 - UVa

UVa 11104 - Cousins

Problem

first cousin ：如果兩個字串可以藉由移除不多於一半的字符，可以變成相同的字串。

ex. abcdef、axcyd 分別移除 (b, e, f)、(x, y)，就可以變成 acd。

然而如果它們 string (A, B)要稱為 (n+1)th cousin，則存在一個媒介 C，A 和 C 是 first cousin 以及 B 和 C 是 nth cousin。

Sample Input

1
2
3
4
5
6
7
8
a
b
abb
baa
abcdef
axcyd
0
0

Sample Output

1
2
3
2
2
1

Solution

這題看題看得很痛苦，也就是說找兩個字串最短的關係 (請無視長的)。

然而要如何找到最短的，思考一下絕對跟 LCS 有點關係，想了一整個早上仍然沒有結果，後來看了大神代碼回溯想法：

1
2
3
4
5
6
7
8
9
10
11
12
condition of first cousin for string a, b
* LCS(a, b) = maximum length LCS.
=> check if LCS(a, b) * 2 > a.len && LCS(a, b) * 2 > b.len, then output first cousin.
=> if not, we know string a and string xa which length is LCS(a, b) + a.len.
xa : __LCS(a, b)__ + a.str
    ^^^^^^^^^^^^^ // any letters., LCS(a, xa) = a.len, LCS(a, b) <= a.len, so xa and a are first cousins.
and so on, make string x2a which length is LCS(a, b) + 3 * a.len
x2a : __LCS(a, b)__ + a.str + a.str + a.str
    ^^^^^^^^^^^^^^^^^^^^^ // any letters., LCS(a, xa) = 2 * a.len, so xa and x2a are first cousisn.
above xa, x2a shown by letter consist, not order.
when x?a can become string b first cousin ? => __LCS(a, b)__ + (? * a.str) = half of b.

仔細想想，這解法類似於貪心？而 LCS 存在的關係是起手用。增倍貪心，把不需要的地方直接填跟目標的內容。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    char a[128], b[128];
    while (scanf("%s %s", a, b) == 2 && a[0] != '0') {
        int dp[128][128] = {};
        int la = strlen(a), lb = strlen(b);
        for (int i = 0; i < la; i++)
            for (int j = 0; j < lb; j++)
                if (a[i] == b[j])
                    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1);
                else
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
        int lcs = dp[la][lb];
        int ret = 1, len = lcs;
        if (la > lb)	swap(la, lb);
        while (len + len < lb) {
            len += la, la <<= 1;
            ret++;
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
condition of first cousin for string a, b
* LCS(a, b) = maximum length LCS.
=> check if LCS(a, b) * 2 > a.len && LCS(a, b) * 2 > b.len, then output first cousin.
=> if not, we know string a and string xa which length is LCS(a, b) + a.len.
xa : __LCS(a, b)__ + a.str
	 ^^^^^^^^^^^^^ // any letters., LCS(a, xa) = a.len, LCS(a, b) <= a.len, so xa and a are first cousins.
and so on, make string x2a which length is LCS(a, b) + 3 * a.len
x2a : __LCS(a, b)__ + a.str + a.str + a.str
	  ^^^^^^^^^^^^^^^^^^^^^ // any letters., LCS(a, xa) = 2 * a.len, so xa and x2a are first cousisn.
above xa, x2a shown by letter consist, not order.
when x?a can become string b first cousin ? => __LCS(a, b)__ + (? * a.str) = half of b.
*/
Read More +
解題區/解題區 - UVa

UVa 10961 - Chasing After Don Giovanni

Problem

A 要追 B，結果 B 偽裝成 C，B 告訴 A，B 將會怎麼走並且沿路指導 A 該怎麼走，然而真正的 C 也會在地圖中某一個地方開始移動。

如果 A、C 相遇，則會發現 B 是偽裝的，給予兩個人的路線，請問 B 是否能安全抵達目的地，如果再目的地被抓到也相當於安全抵達，因為他已經抵達目的地。

假設 A、C 的移動速度相同。

Sample Input

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

Sample Output

1
2
3
No
Yes

Solution

這一題與 11796 - Dog Distance 很類似。找兩個路線的最接近距離。

  • 题目大意：
    两条狗匀速分别沿着折线跑，已知同时出发，同时到达，问你求相差最大的距离 与相差的最小的距离之间的差值。
  • 解题思路：
    如果两只狗都走1条线段的话，根据相对运动的理论，可以把其中一只狗看成静止不动，另一只狗相对运动，且线路为线段，那么立刻转化为点到线段的距离的问题。
http://blog.csdn.net/a1061747415/article/details/38682243

而這一題檢查最近距離是否為 0 即可。特別 case 終點碰到的情況，此外測資中兩個路線的距離長貌似相同，因為討論區的有幾組不同長的測資，雖然以下代碼沒有通過，但是還是 AC。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
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 <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
// similar 11796 - Dog Distance
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)	return x < a.x;
        return y < a.y;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
typedef Pt Vector;
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
double distProjection(Pt as, Pt at, Pt s) {
    double a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
double distToSeg(Pt sa, Pt sb, Pt a) {
    if(!(sa == sb) && between(sa, sb, a))
        return distProjection(sa, sb, a);
    return min(dist(sa, a), dist(sb, a));
}
int main() {
    int testcase, cases = 0, A, B;
    Pt DA[105], DB[105];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%lf %lf", &DB[0].x, &DB[0].y);
        scanf("%lf %lf", &DA[0].x, &DA[0].y);
        scanf("%d", &A);
        for(int i = 1; i <= A; i++)
            scanf("%lf %lf", &DA[i].x, &DA[i].y);
        scanf("%d", &B);
        for(int i = 1; i <= B; i++)
            scanf("%lf %lf", &DB[i].x, &DB[i].y);
        A++, B++;
        double speed_a = 1, speed_b = 1;
        
        int aIdx, bIdx;
        double sa, sb, run;
        Vector va, vb;
        Pt apos = DA[0], bpos = DB[0];
        aIdx = bIdx = 0;
        
        double mxDist = 0, mnDist = 1e+30;
        while(aIdx < A - 1 && bIdx < B - 1) {
            sa = dist(DA[aIdx+1], apos);
            sb = dist(DB[bIdx+1], bpos);
            run = min(sa/speed_a, sb/speed_b); // run time
            va = (DA[aIdx+1] - apos)/sa * run * speed_a;
            vb = (DB[bIdx+1] - bpos)/sb * run * speed_b;
            if (bpos + vb == DB[B - 1] && apos + va == DA[A - 1]) { // a route is safe even if the villagers meet Leporello at the destination.
                mnDist = min(mnDist, dist(bpos, apos));
                if (!(bpos == bpos+vb-va) && between(bpos, bpos+vb-va, apos) && !(apos == bpos+vb-va))
                    mnDist = min(mnDist, distProjection(bpos, bpos+vb-va, apos));
            } else
                mnDist = min(mnDist, distToSeg(bpos, bpos+vb-va, apos));
//			mxDist = max(mxDist, dist(apos, bpos));
//			mxDist = max(mxDist, dist(apos, bpos+vb-va));
            apos = apos + va;
            bpos = bpos + vb;
            if(apos == DA[aIdx+1])
                aIdx++;
            if(bpos == DB[bIdx+1])
                bIdx++;
        }
        if (cases++)	puts("");
        if (fabs(mnDist) < eps)
            puts("No");
        else
            puts("Yes");
    } 
    return 0;
}
/*
*/
Read More +
解題區/解題區 - UVa

UVa 10867 - Cutting a Polygon

Problem

給一個簡單多邊形，接著詢問許多通過兩點的直線，與多邊形的交集長度為何？

Sample Input

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

Sample Output

1
2
3
4
5
2.798
6.000
3.000
2.954
2.000

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-9
#define MAXN 131072
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);
    }
};
double dist(Pt a, Pt b) {
    return (a-b).length();
}
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;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if (cross(as, at, bs) * cross(as, at, bt) < -eps &&
        cross(at, as, bs) * cross(at, as, bt) < -eps &&
        cross(bs, bt, as) * cross(bs, bt, at) < -eps &&
        cross(bt, bs, as) * cross(bt, bs, at) < -eps)
        return 1;
    return 0;
}
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;
    }
};
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;
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(onSeg(p[i], p[j], q))
            return 1;
        if(p[i].y > q.y != p[j].y > q.y &&
           q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
           cnt++;
    }
    return cnt&1;
}
double solve(Pt D[], int n, Pt s, Pt e) {
    vector<Pt> p;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        if (cross(s, e, D[i]) * cross(s, e, D[j]) < -eps) {
            Pt t = getIntersect(Seg(D[i], D[j]), Seg(s, e));
            p.push_back(t);
        } else if (onSeg(s, e, D[i]) || fabs(cross(s, e, D[i])) < eps)
            p.push_back(D[i]);
    }
    p.push_back(s);
    p.push_back(e);
    sort(p.begin(), p.end());
    double ret = 0;
    for (int i = 0; i + 1 < p.size(); i++) {
        Pt mid = (p[i] + p[i+1]) * 0.5;
        if (inPolygon(D, n, mid))
            ret += dist(p[i], p[i+1]);
//		printf("%lf %lf ++++\n", p[i].x, p[i].y);
    }
    return ret;
}
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        Pt D[2048];
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &D[i].x, &D[i].y);
        Pt s, e;
        for (int i = 0; i < m; i++) {
            scanf("%lf %lf", &s.x, &s.y);
            scanf("%lf %lf", &e.x, &e.y);
            double ret = solve(D, n, s, e);
            printf("%.3f\n", ret);
        }
    }
    return 0;
}
/*
9 5
0 0
0 2
1 1
2 2
3 1
4 2
5 1
6 2
6 0
-1 2 7.5 1
0 1 6 1
0 1.5 6 1.5
0 2 6 1
0 0 0 2
4 9
0 0 
0 1
1 1
1 0
0 0 1 1
1 1 0 0
0 0 1 0
0 0 0.5 0
0 0.5 1 0.5
0 1 1 1
1 1 1 0
0.75 0.75 0.75 0.25
0 0.25 1 0.75
*/
Read More +