解題區►解題區 - UVa

UVa 12761 - Blue Chips

Problem

N 個人圍繞一圈，每一個回合自身的分數為相鄰距離小於 D (不包含自己) 的權重總和 mod N。

請問在 K 個回合後，最大分數和擁有最大分數的人分別為何？

Sample Input

1
2
3
1
3 3 1
1 2 2

Sample Output

1
2
1
2 3

Solution

由於 K 很大，明顯地是一道矩陣 D&C。

把遞迴公式建造出來，可以在 O(N^3 log 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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
int mod = 10000;
struct Matrix {
    int v[64][64];
    int row, col; // row x col
    Matrix(int n, int m, int a = 0) {
        memset(v, 0, sizeof(v));
        row = n, col = m;
        for(int i = 0; i < row && i < col; i++)
            v[i][i] = a;
    }
    Matrix operator*(const Matrix& x) const {
        Matrix ret(row, x.col);
        for(int i = 0; i < row; i++) {
            for(int k = 0; k < col; k++) {
                if (v[i][k])
                    for(int j = 0; j < x.col; j++) {
                        ret.v[i][j] += v[i][k] * x.v[k][j],
                        ret.v[i][j] %= mod;
                    }
            }
        }
        return ret;
    }
    Matrix operator+(const Matrix& x) const {
        Matrix ret(row, col);
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                ret.v[i][j] = v[i][j] + x.v[i][j];
            }
        }
        return ret;
    }
    Matrix operator^(const int& n) const {
        Matrix ret(row, col, 1), x = *this;
        int y = n;
        while(y) {
            if(y&1)	ret = ret * x;
            y = y>>1, x = x * x;
        }
        return ret;
    }
    Matrix powsum(int k) {
        if (k == 0) return Matrix(row, col, 0);
        Matrix vv = powsum(k/2);
        if (k&1) {
            return vv * (Matrix(row, col, 1) + vv) + vv;
        } else {
            return vv * (Matrix(row, col, 1) + vv);
        }
    }
};
int main() {	
	freopen("in.txt", "r+t", stdin);
	freopen("out.txt", "w+t", stdout); 
    int testcase, N, K, D;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &K, &D);
        mod = N;
        Matrix m(N, N), a(N, 1);
        for (int i = 0; i < N; i++)
            scanf("%d", &a.v[i][0]), a.v[i][0] %= N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if ((abs(i - j) <= D || N - abs(i - j) <= D) && i != j)
                    m.v[i][j] = 1;
            }
        }
        Matrix ret = (m ^ K);
        ret = ret * a;
        int mn = 0x3f3f3f3f;
        for (int i = 0; i < N; i++) {
            mn = min(mn, ret.v[i][0]);
        }
        printf("%d\n", mn);
        int f = 0;
        for (int i = 0; i < N; i++) {
            if (ret.v[i][0] == mn) {
                if (f)  putchar(' ');
                f = 1;
                printf("%d", i + 1);
            }
        }
        puts("");
    }
    return 0;
}
/*
 1
 3 3 1
 1 2 2
 */
Read More +
解題區►解題區 - UVa

UVa 12637 - 30 Minutes or Less

Problem

現在有 R 個 Pizza 店，同一個時間接收到 N 筆訂單，每一個店負責處理一筆訂單，發送的成本為店家到訂單的曼哈頓距離。

求所有訂單送達的總時間最小值為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2 2
1 5
2 1
4 2
4 3
3 2
2 1
4 3
7 4
4 5
5 -1

Sample Output

1
2
8
7

Solution

一開始以為是要求最後一個送達的時間最小化，二分下去才發現連範測都過不了。

建圖之後，用 KM 算法找最大帶權匹配 (費用最小就取負號)，用最少費用流解也是可以。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
#include <map>
#include <vector>
using namespace std;
struct KM {
	int W[105][105], N;
	int mx[105], my[105]; // match arr
	int lx[105], ly[105]; // label arr
	int x[105], y[105]; // used arr
	int hungary(int nd) {
	    int i;
	    x[nd] = 1;
	    for(i = 0; i < N; i++) {
	        if(y[i] == 0 && W[nd][i] == lx[nd]+ly[i]) {
	            y[i] = 1;
	            if(my[i] == -1 || hungary(my[i])) {
	                my[i] = nd;
	                return 1;
	            }
	        }
	    }
	    return 0;
	}
	int run() {
	    int i, j, k, d;
	    memset(mx, -1, sizeof(mx));
	    memset(my, -1, sizeof(my));
	    for (int i = 0; i < N; i++)
	    	lx[i] = -0x3f3f3f3f, ly[i] = 0;
	    for(i = 0; i < N; i++)
	        for(j = 0; j < N; j++)
	            lx[i] = lx[i] > W[i][j] ? lx[i] : W[i][j];
	    for(i = 0; i < N; i++) {
	        while(1) {
	            memset(x, 0, sizeof(x));
	            memset(y, 0, sizeof(y));
	            if(hungary(i))  break;
	            d = 0x3f3f3f3f;
	            for(j = 0; j < N; j++) {
	                if(x[j]) {
	                    for(k = 0; k < N; k++)
	                        if(!y[k])
	                        d = d < lx[j]+ly[k]-W[j][k] ?
	                            d : lx[j]+ly[k]-W[j][k];
	                }
	            }
	            if(d == 0x3f3f3f3f)  break;
	            for(j = 0; j < N; j++) {
	                if(x[j])    lx[j] -= d;
	                if(y[j])    ly[j] += d;
	            }
	        }
	    }
	    int res = 0;
	    for(i = 0; i < N; i++) {
	        if(my[i] != -1)
	            res += W[my[i]][i];
	    }
	    return res;
	}
} km;
int dist(int x1, int y1, int x2, int y2) {
	return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
	int N, R;
	int x[256], y[256], cost[128][128];
	while (scanf("%d %d", &R, &N) == 2) {
		for (int i = 0; i < R; i++)
			scanf("%d %d", &x[i], &y[i]);
		for (int i = 0; i < N; i++)
			scanf("%d %d", &x[i+R], &y[i+R]);
		
		km.N = R;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < N; j++) {
				cost[i][j] = dist(x[i], y[i], x[j+R], y[j+R]);
				km.W[i][j] = -cost[i][j];
			}
			for (int j = N; j < R; j++)
				km.W[i][j] = 0;
		}
		int ret = km.run();
		printf("%d\n", -ret);
	}
	return 0;
} 
/*
2 2
1 5
2 1
4 2
4 3
3 2
2 1
4 3
7 4
4 5
5 -1
*/
Read More +
解題區►解題區 - UVa

UVa 12890 - Easy Peasy

Problem

給一串整數序列，請問有多少連續的區間，區間不包含重複的數字。

Sample Input

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

Sample Output

1
2
5
12

Solution

窮舉每一個點當作區間左端點，向左延伸的最遠的右端點必然非遞減。

掃描線計算右端點。效率 O(n log n)。

掛上輸入優化、HASH 會來得更快。

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
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
int main() {
	int testcase, n, x;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		map<int, int> R;
		int low = 0;
		long long ret = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%d", &x);
			int &y = R[x];
			if (y > low)	low = y;
			y = i;
			ret += i - low;
//			printf("[%d %d]\n", low + 1, i);
		}
		printf("%lld\n", ret);
	}
	return 0;
}
/*
9
3
1 2 1
5
1 2 3 1 2
4
1 2 2 1
*/
Read More +
解題區►解題區 - UVa

UVa 11123 - Counting Trapizoid

Problem

給平面上 N 個不重複的點，有多少梯形可以由這幾個點構成？

  • 有四條邊
  • 一對平行、一對不平行
  • 面積為正

Sample Input

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

Sample Output

1
2
Case 1: 0
Case 2: 1

Solution

先窮舉任兩個點拉起的線段 (let N = n*(n-1)/2)。

針對線段斜率排序，接著將相同斜率放置在同一個 group。

對於每一個 group 的每一個元素計算有多少可以配對成梯形。

  • 防止共線
  • 防止線段具有相同長度 (防止兩對邊平行)

斜率相同，按照交 y 軸的大小由小到大排序。(左側到右側)，由左側掃描到右側，依序把非共線的線段丟入，並且紀錄線段長度資訊。每一個能匹配的組合為 當前線段數 - 相同長度線段數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <assert.h>
using namespace std;
#define eps 1e-9
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);
    }
    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 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);
}
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;
	}
};
struct DOUBLE {
	double v;
	DOUBLE(double a = 0):
		v(a) {}
	bool operator<(const DOUBLE &other) const {
		if (fabs(v - other.v) > eps)
			return v < other.v;
		return false;
	}
};
Pt D[256];
Seg segs[65536], buf[65536];
int main() {
	int cases = 0;
	int n, m;
	while (scanf("%d", &n) == 1 && n) {
		for (int i = 0; i < n; i++)
			scanf("%lf %lf", &D[i].x, &D[i].y);
		sort(D, D + n);
		
		m = 0;
		for (int i = 0; i < n; i++)
			for (int j = i+1; j < n; j++)
				segs[m++] = Seg(D[i], D[j]);
		
		sort(segs, segs + m);
		long long ret = 0;
		for (int i = 0; i < m; ) {
			int j = i, tn = 0;
			while (j < m && fabs(segs[i].angle - segs[j].angle) < eps)
				buf[tn++] = segs[j], j++;
			i = j;
			
			map<DOUBLE, int> LEN; // LEN[len] = count.
			queue<Seg> Q;
			int tmp = 0;
//			for (int k = 0; k < tn; k++)
//				printf("(%lf %lf) - (%lf %lf)\n", buf[k].s.x, buf[k].s.y, buf[k].e.x, buf[k].e.y);
//			puts("--- same slope");
			for (int k = 0; k < tn; k++) {
				while (!Q.empty() && fabs(cross(buf[k].s, buf[k].e, Q.front().s)) > eps) {
					Seg t = Q.front();
					Q.pop();
					tmp++, LEN[DOUBLE(dist(t.s, t.e))]++;
				}
				int comb = tmp - LEN[DOUBLE(dist(buf[k].s, buf[k].e))]; // remove same length
				ret += comb;
				Q.push(buf[k]);
			}
		}
		printf("Case %d: %lld\n", ++cases, ret);
	}
	return 0;
}
/*
4
0 0
1 0
0 1
1 1
4
0 0
1 1
2 0
0 1
6
5 1
3 1
5 0
3 3
2 4
0 8
0
*/
Read More +
解題區►解題區 - UVa

UVa 12452 - Plants vs. Zombies HD SP

Problem

給一個 N 個點的樹圖，在點上放置植物保護所有的邊，每個點上最多放置一個植物，請問最少花費為何？

  • 綠豆槍手：花費 100 元，保護相鄰一條邊。
  • 分裂碗豆：花費 175 元，保護相鄰兩條邊。
  • 楊桃：花費 500 元，保護相鄰所有邊。

Sample Input

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

Sample Output

1
2
$100
$175

Solution

將樹轉換成有根樹，對於每一個 node 當成 tree 去做考慮。

狀態 dp[node][1:protect edge from parent, 0:none]

以 node 以下作為一個 subtree 的最少花費，並且是否已經保護通往父親的邊。

效率 O(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
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 32767
vector<int> g[MAXN];
long long dp[MAXN][2]; // [node][1:protect edge from parent, 0:none]
#define INF (1LL<<50)
void dfs(int u, int p) {
	
	dp[u][0] = dp[u][1] = INF;
	
	long long cost[3] = {};
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (v == p)	continue;
		dfs(v, u);
		cost[0] += dp[v][0];
		cost[1] += dp[v][1];
		cost[2] += min(dp[v][0], dp[v][1]);
	}
	dp[u][0] = min(dp[u][0], cost[1]);
	dp[u][1] = min(dp[u][1], cost[1] + 100);
	dp[u][1] = min(dp[u][1], cost[2] + 500);
	
	long long c[2] = {INF, INF};
	for (int i = 0; i < g[u].size(); i++) {// two edge with subnode and parent.
		int v = g[u][i];
		if (v == p)	continue;
		dp[u][1] = min(dp[u][1], cost[1] - dp[v][1] + dp[v][0] + 175);
		if (-dp[v][1] + dp[v][0] < c[1]) {
			c[1] = -dp[v][1] + dp[v][0];
			if (c[0] > c[1])	swap(c[0], c[1]);
		}
	}
	// two two edge with two subnodes
	dp[u][0] = min(dp[u][0], cost[1] + c[0] + c[1] + 175);
}
int main() {
	int testcase, n;
	int u, v;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			g[i].clear();
		for (int i = 1; i < n; i++) {
			scanf("%d %d", &u, &v);
			g[u].push_back(v);
			g[v].push_back(u);
		}
		dfs(0, -1);
		printf("$%lld\n", min(dp[0][0], dp[0][1]));
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12440 - Save the Trees

Problem

有一排樹，每個樹分別有 type 和 height，現在要將其分團，

  • 每一團內不允許有相同的 type
  • 每一團的花費是最高的 height

計算總花費最小為何？

Sample Input

1
2
3
4
5
6
7
1
5
3 11
2 13
1 12
2 9
3 13

Sample Output

1
Case 1: 26

Solution

藉由掃描線的思路，可以得知每一個樹的位置 i，往左延伸最大多少內不會有重複的 type。詳見 12890 - Easy Peasy 的技巧。

因此會得到公式 $dp([i]) = min(dp[j - 1] + max(height[k])), j \geq f(i), j \le k \le i$

dp[i]：將前 i 個樹分團的最少費用。

計算這個公式需要 O(n^2)，由於 n 很大，必須找一個優化將其降下來。

首先知道 f(i) 是非遞減函數 (會一直增加)，單純看 i 時，dp[j - 1] 是固定的，但
max(height[k]) 會逐漸增加，如果能在 O(log n) 時間進行更新、詢問，複雜度將可以降至 O(n log n)。

每個元素有兩個屬性 (a, b)

  • query(f(i), i) : return min(A[k].a + A[k].b), f(i) <= k <= i
  • update(f(i), i, height[i]) : A[k].b = max(A[k].b, height[i])

左思右想仍然沒有辦法用線段樹完成它，至少是一個很 tricky 的花費計算。

有一個貪心的思路，考慮區間內的計算時，只需要找到嚴格遞減的高度進行更新即可，並非所有的可能進行嘗試。用一個單調隊列，只記錄 [f(i), i] 之間的嚴格遞減的高度資訊，接著每次需要窮舉單調隊列內的所有元素。

複雜度最慘還是 O(n^2)，隨機測資下速度是快非常多的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 131072
int type[MAXN], height[MAXN];
long long dp[MAXN];
int dQ[MAXN];
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	int testcase, cases = 0;
	int n;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
			scanf("%d %d", &type[i], &height[i]);
		map<int, int> R;
		int L = 0;
		dp[0] = 0;
		int head = 0, rear = -1;
		for (int i = 1; i <= n; i++) {
			int &y = R[type[i]];
			L = max(L, y);
			y = i;
			while (head <= rear && dQ[head] <= L)
				head++;
			while (head <= rear && height[dQ[rear]] <= height[i])
				rear--;
			dQ[++rear] = i;
			
			dp[i] = 1LL<<60;
			for (int j = head; j <= rear; j++) {
				if (j != head)
					dp[i] = min(dp[i], dp[dQ[j-1]] + height[dQ[j]]);
				else
					dp[i] = min(dp[i], dp[L] + height[dQ[j]]);
			}
		}
		printf("Case %d: %lld\n", ++cases, dp[n]);
	}
	return 0;
}
/*
1
5
3 11
2 13
1 12
2 9
3 13
30
10
4 13
2 18
7 20
1 16
1 14
10 5
5 11
7 19
8 12
2 16
9999
10
10 16
3 5
8 11
8 2
5 3
6 2
10 19
6 10
6 16
6 4
9999
10
3 6
10 5
2 9
5 2
9 3
3 8
6 10
4 17
7 10
6 11
*/
Read More +
解題區►解題區 - UVa

UVa 1382 - Distant Galaxy

Problem

給平面上 N 個點，找一個最大矩形，使得矩形邊上有最多點個數。

Sample Input

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

Sample Output

1
Case 1: 7

Solution

UVa 1382

先離散化處理，將所有點放置在 grid[100][100] 內。

接著窮舉上下兩條平行線，由左而右開始掃描，邊緣的個數為 V[U1] + V[U2] + H[R] - V[U3] + V[U4] + H[L]，掃描時維護 V[U3] + V[U4] - H[L] 的最小值。

特別小心矩形的四個頂點的排容，上述的公式仍然不太夠。由於題目沒有特別要求正面積矩形，必須考慮共線上最多的點個數。

效率 O(n^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h> 
#include <map>
#include <algorithm>
using namespace std;
int main() {
	int n, x[128], y[128];
	int cases = 0;
	while (scanf("%d", &n) == 1 && n) {
		map<int, int> Rx, Ry;
		for (int i = 0; i < n; i++) {
			scanf("%d %d", &x[i], &y[i]);
			Rx[x[i]] = 0, Ry[y[i]] = 0;
		}
		
		int size, R, C;
		size = 0;
		for (map<int, int>::iterator it = Rx.begin();
			it != Rx.end(); it++) {
			it->second = size++;
		}
		R = size;
		size = 0;
		for (map<int, int>::iterator it = Ry.begin();
			it != Ry.end(); it++) {
			it->second = size++;
		}
		C = size;
		
		int g[128][128] = {}, ret = 0;
		for (int i = 0; i < n; i++) {
			int r, c;
			r = Rx[x[i]], c = Ry[y[i]];
			g[r][c]++;
		}
		
		for (int i = 0; i < R; i++) {
			int sum[128] = {}, s1, s2, mn;
			for (int j = i; j < R; j++) {
				s1 = s2 = 0, mn = 0;
				for (int k = 0; k < C; k++) {
//					printf("[%d %d] %d\n", i, j, k);
					sum[k] += g[j][k];
					s1 += g[i][k], s2 += g[j][k];
					if (i != j) {
//						printf("%d %d %d %d = %d\n", s1, s2, mn, sum[k], s1 + s2 - mn + sum[k]);
						ret = max(ret, s1 + s2 - mn + sum[k] - g[i][k] - g[j][k]);
						mn = min(mn, s1 + s2 - sum[k]);
					}
				}
			}
		}
		
		for (int i = 0; i < R; i++) {
			int sum = 0;
			for (int j = 0; j < C; j++)
				sum += g[i][j];
			ret = max(ret, sum);
		}
		
		for (int i = 0; i < C; i++) {
			int sum = 0;
			for (int j = 0; j < R; j++)
				sum += g[j][i];
			ret = max(ret, sum);
		}
		printf("Case %d: %d\n", ++cases, ret);
	}
	return 0;
}
/*
10 
2 3 
9 2 
7 4 
3 4 
5 7 
1 5 
10 4 
10 6 
11 4 
4 6 
3
1 1
2 1
3 1
3
1 1
1 2
1 3
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
*/
Read More +
解題區►解題區 - UVa

UVa 12873 - The Programmers

Problem

給 P 個隊伍、S 個賽區，每隊分別都有可以去的賽區，而每一個賽區最多容納 C 個隊伍。

請問參加的總隊伍數量最大為何？

Sample Input

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

Sample Output

1
2
2
3

Solution

建造 maxflow 模型，source - team - site - sink 即可完成。

不是說好 maxflow 不太會考的嗎？結果還是在泰國賽區出來了，雖然之前也噴過 mincost 最少費用流 …

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
using namespace std;
const int MAXV = 40010;
const int MAXE = MAXV * 200 * 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++];
    }
    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 main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        int P, S, C, m, x, y;
        scanf("%d %d %d %d", &P, &S, &C, &m);
        g.Init(P + S + 2);
        int source = 0, sink = P + S + 1;
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            g.Addedge(x, P + y, 1);
        }
        for (int i = 1; i <= P; i++)
            g.Addedge(source, i, 1);
        for (int i = 1; i <= S; i++)
            g.Addedge(P + i, sink, C);
        int ret = g.Maxflow(source, sink);
        printf("%d\n", ret);
    }
    return 0;
}
/*
 2
 2 2 1 4
 1 1
 1 2
 2 1
 2 2
 4 3 1 12
 1 1
 1 2
 1 3
 2 1
 2 2
 2 3
 3 1
 3 2
 3 3
 4 1
 4 2
 4 3
*/
Read More +
解題區►解題區 - UVa

UVa 12872 - Hidden Plus Signs

Problem

盤面上放置許多 + 展開，保證寬高相同並且不會超出格子外部，同時每一個大小不超過 11。而十字中心不會被其他十字覆蓋，每一格會顯示被覆蓋幾次。

找到一種放置方法，復原盤面結果，如果有種放置方法，選擇一種字典順序最小的輸出。

Sample Input

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

Sample Output

1
2
3
4
2
3 3
9
8 10

Solution

論窮舉順序的重要性，將會導致速度的快慢。

原則上先把所有 1 的位置挑出，依序窮舉每一個 1 是否可以進行放置。每一次選擇放置時，先從最大的寬高開始嘗試，先塞掉大多數的盤面結果，否則速度會被拉下。

不確定這一題是否有很正統的作法，求指導。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int g[32][32], n, m;
int A[900][2], N, SUM = 0;
int isEmpty() {
	return SUM == 0;
}
void remove(int x, int y, int w) {
	for (int i = x - w; i <= x + w; i++)
		g[i][y]--, SUM--;
	for (int i = y - w; i <= y + w; i++)
		g[x][i]--, SUM--;
	g[x][y]++, SUM++;
}
void resume(int x, int y, int w) {
	for (int i = x - w; i <= x + w; i++)
		g[i][y]++, SUM++;
	for (int i = y - w; i <= y + w; i++)
		g[x][i]++, SUM++;
	g[x][y]--, SUM--;
}
int place(int x, int y, int w) {
	for (int i = x - w; i <= x + w; i++)
		if (!g[i][y])
			return 0;
	for (int i = y - w; i <= y + w; i++)
		if (!g[x][i])
			return 0;
	return 1;
}
int dfs(int idx, int used, int LX, int LY) {
	if (isEmpty()) {
		printf("%d\n%d %d\n", used, LX + 1, LY + 1);
		return 1;
	}
	if (idx == N)
		return 0;
	int t = min(min(A[idx][0], A[idx][1]), min(n - 1 - A[idx][0], m - 1 - A[idx][1]));
	for (int i = t; i >= 1; i--) {
		if (place(A[idx][0], A[idx][1], i)) {
			remove(A[idx][0], A[idx][1], i);
			if (dfs(idx+1, used + 1, A[idx][0], A[idx][1]))
				return 1;
			resume(A[idx][0], A[idx][1], i);
		}
	}
	if (dfs(idx+1, used, LX, LY))
		return 1;
	return 0;
}
int main() {
	int testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &m);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				scanf("%d", &g[i][j]), SUM += g[i][j];
		N = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (g[i][j] == 1)
					A[N][0] = i, A[N][1] = j, N++;
		dfs(0, 0, -1, -1);
	}
	return 0;
}
/*
2
5 5
0 1 1 0 0
1 1 2 0 0
1 2 1 1 1
0 0 1 0 0
0 0 1 0 0
10 11
0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 1 1 0 1 0 0 0
0 0 1 1 1 2 2 1 1 0 0
0 0 1 2 2 1 1 2 2 0 0
0 0 1 1 3 1 0 0 1 0 0
0 0 0 2 1 2 2 1 1 1 1
0 1 0 0 1 1 1 0 1 1 0
1 1 1 0 1 1 1 1 3 1 1
0 1 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0 0 0 0
*/
Read More +
解題區►解題區 - UVa

UVa 12871 - Landmine Cleaner

Problem

給予每一個格子的得分，分數為鄰近九格的 L 個數 (1 個 1 分) 加上自己是否為 L (3 分)，因此最低 0 分，最高 12 分。

保證只有唯一解。

Sample Input

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

Sample Output

1
2
3
-L--
L-LL
LL--

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXN 1024
int A[MAXN][MAXN], solv[MAXN][MAXN];
int g[MAXN][MAXN];
const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[] = {1, -1, 0, 1, -1, 0, 1, -1};
int n, m;
int isplace(int x, int y) {
	int v = A[x][y], tx, ty;
	int unknown = 0, score = 0;
	for (int i = 0; i < 8; i++) {
		tx = x + dx[i], ty = y + dy[i];
		if (tx < 0 || ty < 0 || tx >= n || ty >= m)
			continue;
		if (solv[tx][ty])	score += g[tx][ty];
		else				unknown++;
	}
	if (v < 3)					return -1;
	if (v > 8)					return 1;
	if (score + unknown < v)	return 1;
	if (score + 4 > v)			return -1;
	return 0; // not sure.
}
int main() {
	int testcase;
	int t;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &m);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				scanf("%d", &A[i][j]);
			}
		}
		memset(solv, 0, sizeof(solv));
		int test = n * m;
		while (test) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (solv[i][j])	continue;
					int t = isplace(i, j);
					if (t) {
						test--;
						g[i][j] = t > 0;
						solv[i][j] = 1;
					}
				}
			}
			
		}
		for (int i = 0; i < n; i++, puts("")) {
			for (int j = 0; j < m; j++) {
				if (solv[i][j])
					putchar(g[i][j] ? 'L' : '-');
				else {
					assert(false);
				}
			}
		}
	}
	return 0;
}
/*
9999
3 4
2 6 3 2
7 5 7 5
6 7 3 2
3 3
7 9 7
9 12 9
7 9 7
3 1
0
0
0
*/
Read More +