解題區/解題區 - UVa

UVa 10907 - Art Gallery

Problem

給一個簡單多邊形，內部放置一點求可視範圍的區域面積。

Sample Input

1
2
3
4
5
6
7
8
9
5
0 0
50 50
100 0
100 100
0 100
2
49 50
50 51

Sample Output

1
2
3
Gallery #1
6250.00
7500.00

Solution

一開始以為可視範圍可能保證是凸多邊形，後來發現其實不一定，有可能是簡單多邊形。

錯誤的思路－一開始想用半平面交計算，所以一直掛在特殊 case 下。

首先，對詢問點將每一個點拿來作極角排序，然後掃描相鄰的極角，對於每一個相鄰極角會與詢問點拉出一個小角度，兩邊的射線無限延伸，接著保證簡單多邊形的每一條邊要不橫跨這個張角、要不完全沒有，不會存在一小段於張角中。

因此會發現會有很多三角形，取交集拿到最靠近詢問點的三角形，兩條射線上取最靠近詢問點的座標，但是這樣的三角形不保證一定在三角形內部，把最後得到的三角形每條邊上的中點拿來做測試，使用射線法檢查是否在簡單多邊形內部。

抓思路 BUG 就花一個早上 Orz。

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
#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 {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    bool operator==(const Pt &a) const {
        return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    } 
};
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 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;
    }
};
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 intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if (onSeg(as, at, bs) || onSeg(as, at, bt) ||
        onSeg(bs, bt, as) || onSeg(bs, bt, at))
        return 1;
    if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
        cross(at, as, bs) * cross(at, as, bt) < 0 &&
        cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
        cross(bt, bs, as) * cross(bt, bs, at) < 0)
    return 1;
    return 0;
}
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;
}
const double pi = acos(-1);
double artGallery(Pt p[], int n, Pt q) { // polygon: anti-clockwise order
    vector< pair<double, Pt> > A;
    for (int i = 0; i < n; i++) {
        if (!(p[i] == q))
            A.push_back(make_pair(atan2(p[i].y - q.y, p[i].x - q.x), p[i]));
    }
    sort(A.begin(), A.end());
    double ret = 0;
    int m = A.size();
    for (int i = 0, j = m-1; i < m; j = i++) {
        if (fabs(A[i].first - A[j].first) > eps) {
            vector<Seg> segs;
            Pt a, b, ta, tb;
            a = q + (A[j].second - q) * 10000;
            b = q + (A[i].second - q) * 10000;
            for (int k = 0, l = n-1; k < n; l = k++) {
                if ((cross(q, A[j].second, p[k]) * cross(q, A[j].second, p[l]) < eps 
                    && cross(q, A[i].second, p[k]) * cross(q, A[i].second, p[l]) < eps)) {
                    if (p[l] == q || p[k] == q)	continue;
                    if (intersection(a, q, p[l], p[k]) && intersection(b, q, p[l], p[k]) && !onSeg(p[l], p[k], q))
                        segs.push_back(Seg(p[l], p[k]));
                }
            }
//			printf("base %lf %lf %lf %lf\n", A[i].second.x, A[i].second.y, A[j].second.x, A[j].second.y);
            for (int i = 0; i < segs.size(); i++) {
//				printf("%lf %lf %lf %lf\n", segs[i].s.x, segs[i].s.y, segs[i].e.x, segs[i].e.y);
                if (intersection(a, q, segs[i].s, segs[i].e)) {
                    ta = getIntersect(Seg(a, q), segs[i]);
                    tb = getIntersect(Seg(b, q), segs[i]);
                    if (dist(ta, q) < dist(a, q) && !(a == q))
                        a = ta;
                    if (dist(tb, q) < dist(b, q) && !(b == q))
                        b = tb;
                }
            }
            if (inPolygon(p, n, Pt((a.x + b.x)/2, (a.y + b.y)/2)) &&
                inPolygon(p, n, Pt((a.x + q.x)/2, (a.y + q.y)/2)) &&
                inPolygon(p, n, Pt((q.x + b.x)/2, (q.y + b.y)/2))) {
                ret += fabs(cross(q, a, b))/2;
//				puts("Y");
            }
//			printf("---- %lf %lf %lf %lf\n", a.x, a.y, b.x, b.y);
//			puts("--");
        }
    }
    return ret;
}
int main() {
    int testcase, cases = 0;
    int n, m;
    double x, y;
    Pt D[105];
    while(scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &D[i].x, &D[i].y);
        scanf("%d", &m);
        printf("Gallery #%d\n", ++cases);
        for (int i = 0; i < m; i++) {
            scanf("%lf %lf", &x, &y);
            double area = artGallery(D, n, Pt(x, y));
            printf("%.2lf\n", area);
        }
    } 
    return 0;
}
/*
5
0 0
50 50
100 0
100 100
0 100
2
49 50
50 51
7
0 5
5 0
10 7
15 0
20 5
15 10
5 10
7
0 5
5 0
10 7
15 0
20 5
15 10
5 10
*/
Read More +
解題區/解題區 - UVa

UVa 12865 - Volume Control

Problem

1, 2, 4, 7, 10, 15, 19, 26, 31, 37, 43, 54, 60, 73

A027384 Number of distinct products ij with 0 <= i, j <= n.

詢問 0 到 N 的連續整數，任兩個挑出來相乘，有多少不同的整數。

Sample Input

1
2
3
2
3
4

Sample Output

1
2
7
10

Solution

聽說當下比賽很多人直接本地建表，不過這一題還真的不知道該怎麼解比較好。

用了窮舉的方式，加入第 i 個整數，將與 0 ~ i 相乘，這時候增加多少不同整數？

  1. 找到 i * j == p * q 其中滿足 p, q < i，要忽略所有可能的 j，剩餘的結果就是增加的數量。
  2. 假設 i = a * b, p = a * ?1, q = b * ?2。
  3. 得到 j = ?1 * ?2、?2 < a, ?1 < b。

用嚴格增加的趨勢，依序窮舉 i 的因數 a (小到大)，?2 可以帶入的數字會遞增，而 ?1 會遞減，而中間會有一段重複的窮舉，只考慮 ?2 進行遞增即可。將不好的 j 給篩掉。

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 <set>
#include <math.h>
#include <vector>
using namespace std;
int main() {
    int ret[65536] = {1}, sum = 1;
    int nop[32767] = {}, cases = 0;
    for (int i = 1; i <= 30000; i++) {
        vector<int> f;
        int first_prime;
        for (int j = 2; j * j <= i; j++) {
            if (i%j == 0) {
                f.push_back(j);
            }
        }
        // i * j == p * q (p, q < i)
        // i = a * b, p = a * ?1, q = b * ?2
        // j = ?1 * ?2
        cases++;
        first_prime = f.size() ? f[0] : i;
        for (int j = 0, q1, q2 = 2; j < f.size(); j++) { // f[j] x (i / f[j])
            for (; q2 < f[j]; q2++) { // ?2 < a, ?1 < b
                for (q1 = i/ f[j] - 1; q1 >= 1; q1--)
                    nop[q1 * q2] = cases;
            }
        }
        for (int j = i / first_prime; j <= i; j++)
            sum += nop[j] != cases;
        ret[i] = sum;
    }
    int testcase, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        printf("%d\n", ret[n]);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12863 - Journey through the kingdom

Problem

對於每一個點 (i, j) 可以護送人的範圍為中間張開矩形 [i-r: i+r] x [j - c: j+c]，可以傳送到矩形任何一點花費為 V(i, j)。每個點的花費和矩形大小都可以不同。

Sample Input

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

Sample Output

1
3 -1 1 0

Solution

什麼，居然有 range tree 配上 dijkstra？

很明顯是一題最短路徑。所有點都分配在 N x M 上，最慘為 25 萬個點，同時邊最慘邊數量也就是 25 萬 x 25 萬，因此在 O(E log V) 肯定是過不去的。

但是後來發現到，花費是在點上，因此可以換個角度想，每次更新離開該點花費最小的，也就是說每 pop 一個點，就能知道有一個矩形內保證是最短路，不會再進行任何更新。因此只要不斷地找到區域內尚未走訪的點，將其移除即可。

為了能夠快速找到矩形內尚未走訪的點，最好的方式是使用 range tree，但是找到區域內所有點的成本是 O(log^2 n + k)，用一堆 set<int> 串 list 起來也要 O(r log n + k)，這種作法會 TLE。而標程中使用 BIT 完成 range tree 的概念，BIT 查找速度是挺快的，但是看起來比較接近 O(k log^2 n)，只能說點移除的速度很快，所以 k 小很多。

用 2D BIT 作為 range tree 的基底，也要確保每一個點很緊密地在 R x C 的每一格，range tree 找到區域內所有尚未走訪的點，進行 dijkstra 更新。

自己寫一個樹套樹的作法嘗試輾輾看，但是在建表上就已經快崩，記憶體飛漲得相當快，導致速度被拉下。之後改用一個 list 串出一堆一條一條的 set，這樣的速度，隨後用二分處理，比用 2D BIT 建造的 range tree 還要快，至少在隨機測資中速度是兩三倍以上，上傳 TLE。

看來只能乖乖地標程給的 … WTF，居然就這樣屈服了，都寫了好幾個版本。就不能讓我混過嗎。QAQ

當前使用優化策略： 建立於 dijkstra

  • 方案 1：
    (1) 啟發式搜索，相同花費下鄰近目標地的優先擴充，沒有好的估價。
    (2) 對於矩形，每個 row 當作一條，建立 list，把不可能需要更新的點移除，實作由 set row[MAXN] 完成。
  • 方案 2：
    (1) 啟發式搜索，相同花費下鄰近目標地的優先擴充，沒有好的估價。
    (2) 對於矩形，random 矩形內部 K 個點。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
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 <stdlib.h>
#include <string.h>
#include <queue>
#include <set>
#include <algorithm> 
using namespace std;
#define MAXN 512
int V[MAXN][MAXN], R[MAXN][MAXN], C[MAXN][MAXN];
int TX, TY;
struct Node {
    int r, c, v, h;
    Node(int a=0, int b=0, int d=0, int e=0):
    r(a), c(b), v(d), h(e) {}
    bool operator<(const Node &x) const {
        if (v != x.v)
            return v > x.v;
        return h > x.h;
    }
};
priority_queue<Node> pQ; // dijkstra
struct RangeTree { // 2D binary indexed tree
    int A[MAXN][MAXN];
    int R, C;
    void init(int R, int C) {
        this->R = R, this->C = C;
        memset(A, 0, sizeof(A));
        for (int i = 1; i <= R; i++)
            for (int j = 1; j <= C; j++)
                modify(i, j, 1);
    }
    
    void modify(int x, int y, int val) {
        for (; x <= R; x += x&(-x)) {
            for (int i = y; i <= C; i += i&(-i)) 
                A[x][i] += val;
        }
    }
    int query(int x, int y) {
        int ret = 0;
        for (; x > 0; x -= x&-x)
            for (int i = y; i > 0; i -= i&(-i))
                ret += A[x][i];
        return ret;
    }
    int rectSum(int lx, int rx, int ly, int ry) {
        return query(rx, ry) - query(lx-1, ry) - query(rx, ly-1) + query(lx-1, ly-1);
    }
    void update(int lx, int rx, int ly, int ry, int val, int tot) { // {val: update cost, tot: #unvisited point in area.}
        if (tot == -1) 	
            tot = rectSum(lx, rx, ly, ry);
        if (tot == 0) 	return;
        if (lx == rx) {
            if (ly == ry) {
                pQ.push(Node(lx, ly, val + V[lx][ly], abs(lx-TX) + abs(ly-TY)));
                modify(lx, ly, -1);
                return;
            }
            int cnt = rectSum(lx, rx, ly, (ly + ry)/2);
            if (cnt) 
                update(lx, rx, ly, (ly + ry)/2, val, cnt);
            if (cnt < tot) 
                update(lx, rx, (ly + ry)/2 + 1, ry, val, tot - cnt);
        }
        else {
            int cnt = rectSum(lx, (lx + rx)/2, ly, ry);
            if (cnt) 
                update(lx, (lx + rx)/2, ly, ry, val, cnt);
            if (cnt < tot)
                update((lx + rx)/2 + 1, rx, ly, ry, val, tot - cnt);
        }
    }
} rangeTree;
int findPath(int n, int m, int sx, int sy, int ex, int ey) {
    if (sx == ex && sy == ey)	return 0;
    TX = ex, TY = ey;
    rangeTree.init(n, m);
    rangeTree.modify(sx, sy, -1);
        
    while (!pQ.empty())	pQ.pop();
    pQ.push(Node(sx, sy, V[sx][sy], abs(sx-ex) + abs(sy-ey)));
    
    Node u;
    int lr, rr, lc, rc;
    while (!pQ.empty()) {
        u = pQ.top(), pQ.pop();
        
        if (abs(u.r - ex) <= R[u.r][u.c] && abs(u.c - ey) <= C[u.r][u.c])
            return u.v;
            
        lr = max(1, u.r - R[u.r][u.c]), rr = min(n, u.r + R[u.r][u.c]);
        lc = max(1, u.c - C[u.r][u.c]), rc = min(m, u.c + C[u.r][u.c]);
        rangeTree.update(lr, rr, lc, rc, u.v, -1);
    }
    return -1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
    int n, m, q, X[16], Y[16];
    while (scanf("%d %d %d", &n, &m, &q) == 3) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &V[i][j]);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &R[i][j]);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &C[i][j]);
        for (int i = 0; i < q; i++)
            scanf("%d %d", &X[i], &Y[i]);
            
        for (int i = 1; i < q; i++) {
            int r = findPath(n, m, X[i-1], Y[i-1], X[i], Y[i]);
            printf("%d%c", r, i == q - 1 ? '\n' : ' ');
        }
    }
    return 0;
}
/*
 3 4 5
 1 2 1 1
 1 5 3 4
 1 1 6 3
 1 2 3 3
 3 3 1 2
 0 0 0 1
 1 4 0 1
 2 3 0 1
 4 1 3 1
 1 1
 3 4
 1 1
 2 2
 2 2
 */
Read More +
解題區/解題區 - UVa

UVa 10154 - Weights and Measures

曾經紅及一時的的烏龜塔問題，討論相當多。最近學弟因為 2014 年資訊奧林匹亞研習營初選中的一題，跑來問我怎麼解比較好。但是想一想之前都是用 dp 過去的。速度 O(n^2)，優化也只會是 O(k n)，k 是答案，還是還用了貪心去解決，但是後來才挖到這個化石，想法是挺簡單的，人生白活了。

l大所寫的演算法是有來源的。
寄信詢問l大之後，得到的回覆，整理於下。

最早出現的文獻

Moore, J.M.(1968) An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science. 15(1):102-109.

現在的演算法名稱 Moore-Hodgson Algorithm 時間複雜度 O(N * log(N)) 演算法證明

  1. 先證至少有一最佳解工作順序是依完工期限由小到大排

  2. 證明拿掉最大執行時間的工作不會比最佳解差 問題轉換方式

Instance:

  • 有n個工作要完成 <—> 有n個箱子要疊
  • 每個工作有不同的處理時間 <—> 不同的重量
  • 每個工作有不同的完工期限 <—> 不同的載重量(要包含自己重量)

Question: 讓無法如期完工的工作越少越好 <—> 箱子疊越多越好 C++實作 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Job {int time, due;} job[10]; 
bool cmp(const Job& j1, const Job& j2) { 
    return j1.due < j2.due;
} 
void Moore_Hodgson() {
    sort(job, job+10, cmp); 
    int t = 0;
    priority_queue<int> pq; 
    for (int i=0; i<10; ++i) {
        pq.push(job[i].time); 
        t += job[i].time; 
        if (t > job[i].due) t -= pq.top(), pq.pop();
    } 
    cout << "如期完成的工作(箱子)數目，最多為" << pq.size();
}
Read More +
解題區/解題區 - 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 +