解題區►解題區 - UVa

UVa 1084 - Deer-Proof Fence

Problem

給 N 個點，用圍籬將這 N 個點包裹起來，並且每一個點距離圍籬距離至少為 M。

求圍籬總長最少為何。

Sample Input

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

Sample Output

1
2
Case 1: length = 29.13 
Case 2: length = 45.13

Solution

可以將點拆分成好幾個元件，分開進行圍籬。利用高速求出子集的方式，窮舉所有的拆分方式。

dp[s] 表示點 s 所需要的最少圍籬長度，dp[s] = min(dp[u] + cost(s-u))。

圍籬長度為凸包總長加上一個圓的周長 (多邊形外角總和為 360 度)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <algorithm>
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);
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m-1;
}
const double pi = acos(-1);
double computeFenceLen(Pt ch[], int n, double r) {
	if (n == 1)
		return r * pi * 2;
	if (n == 2)
		return r * pi * 2 + (ch[0] - ch[1]).length() * 2;
	double ret = 0;
	for (int i = 0, j = n-1; i < n; j = i++)
		ret += (ch[i] - ch[j]).length();
	ret += r * pi * 2;
	return ret;
}
int main() {
    int n, R, cases = 0;
    while (scanf("%d %d", &n, &R) == 2 && n) {
    	Pt D[32], ch[32];
    	for (int i = 0; i < n; i++)
    		scanf("%lf %lf", &D[i].x, &D[i].y);
    	double dp[1024] = {};
    	for (int i = 1; i < (1<<n); i++) {
    		double &val = dp[i];
    		val = 1e+30;
    		for (int j = (i-1)&i; j; j = (j-1)&i)
    			val = min(val, dp[j] + dp[i-j]);
    		
    		int m = 0;
    		Pt A[32];
    		for (int j = 0; j < n; j++) {
    			if ((i>>j)&1)
    				A[m++] = D[j];
    		}
    		
    		int cn = monotone(m, A, ch);
    		double len = computeFenceLen(ch, cn, R);
//    		for (int j = 0; j < cn; j++)
//    			printf("%lf %lf\n", ch[j].x, ch[j].y);
//    		printf("length - %lf\n", len);
    		val = min(val, len);
    	}
    	printf("Case %d: length = %.2lf\n", ++cases, dp[(1<<n)-1]);
    }
    return 0;
}
/*
3 2 
0 0 
2 0 
10 0 
5 3
7 8
9 9
9 9
9 9
2 2
3 3
7 8
9 9
2 2
5 0
4 2
1 5
8 5
2 2
4 9
 */
Read More +
解題區►解題區 - UVa

UVa 1080 - My Bad

Problem

給一個電路圖，有四種閘 AND, OR, XOR, NOT，接著給定閘的輸入端、輸出端，以及預期的輸入和輸出。

請問是否存在電路故障。若只有一個電路故障，輸出故障的情況，否則輸出無法判斷。

故障情況有反向、全為 1、全為 0。

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
29
30
31
32
33
34
35
36
2 2 1 
o i1 i2 
n g1 
2 
2 
1 0 0 
0 0 1 
2 1 1 
a i1 i2 
1 
1 
1 0 1 
2 1 1 
a i1 i2 
1 
2 
1 0 1 
1 1 1 
1 1 1 
n i1 
1 
2 
1 1 
0 0 
3 4 4 
n g4 
a i1 i2 
o i2 i3 
x i3 i1 
2 3 4 1 
4 
0 1 0 0 1 0 1
0 1 1 0 1 1 0
1 1 1 0 1 0 1
0 0 0 0 0 0 1
0 0 0

Sample Output

1
2
3
4
5
Case 1: No faults detected 
Case 2: Unable to totally classify the failure 
Case 3: Gate 1 is failing; output stuck at 1 
Case 4: Gate 1 is failing; output inverted 
Case 5: Gate 2 is failing; output stuck at 0

Solution

如何橋接電路會比較難寫，這裡用 OO 的方式去撰寫，為了方便起見，設計輸入端口只會在 div ~ 512，剩餘在 0 ~ div。

接著窮舉損壞情況，對於每次窮舉，跑一次電路架構。

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
#include <stdio.h> 
#include <vector>
#include <assert.h>
#include <string.h>
#include <algorithm>
using namespace std;
class Circuit {
public:
	enum LOGIC {AND, OR, XOR, NOT, FV, F0, F1};
	struct Gate {
		LOGIC type;
		int p1, p2;
	} gates[1024];
	int inVal[512], outVal[512];
	int visited[512], sick[512];
	LOGIC sickType[512];
	int div = 256;
	void addGate(int id, LOGIC t, int in1, int in2 = 0) {
		gates[id].type = t;
		gates[id].p1 = in1, gates[id].p2 = in2;
	}
	int getInId(int x) {
		return div + x;
	}
	int getId(char s[]) {
		int x;
		sscanf(s+1, "%d", &x);
		return (s[0] == 'i') ? getInId(x) : x;
	}
	int getOutput(int id) {
		if (id > div)		return inVal[id - div];
		if (visited[id])	return outVal[id];
		visited[id] = 1;
		int &val = outVal[id];
		val = 0;
		if (gates[id].type == AND)
			val = (getOutput(gates[id].p1) & getOutput(gates[id].p2));
		if (gates[id].type == OR)
			val = (getOutput(gates[id].p1) | getOutput(gates[id].p2));
		if (gates[id].type == XOR)
			val = (getOutput(gates[id].p1) ^ getOutput(gates[id].p2));
		if (gates[id].type == NOT)
			val = !(getOutput(gates[id].p1));
		if (!sick[id])
			return val;
		if (sickType[id] == FV)
			return val = !val;
		else if (sickType[id] == F0)
			return val = 0;
		else
			return val = 1;
	}
	void clearSick()  {
		memset(sick, 0, sizeof(sick));
	}
	void clear() {
		memset(visited, 0, sizeof(visited));
	}
} g;
int N, G, U, B;
int outGate[128], IN[1024][128], OUT[1024][128];
char s[128], s1[128], s2[128];
int singleTest() {
	int ok = 1;
	for (int i = 0; i < B && ok; i++) {
		g.clear();
		for (int j = 1; j <= N; j++)
			g.inVal[j] = IN[i][j];
		for (int j = 1; j <= U; j++) {
			int v = g.getOutput(outGate[j]);
			ok &= v == OUT[i][j];
		}
	} 
	return ok;
}
void test() {
	g.clearSick();
	if (singleTest()) {
		puts("No faults detected");
		return;
	} 
	
	vector< pair<int, int> > err;
	for (int i = 1; i <= G; i++) {
		g.clearSick();
		g.sick[i] = 1, g.sickType[i] = Circuit::FV;
		if (singleTest())
			err.push_back(pair<int, int>(i, 0));
		g.sick[i] = 1, g.sickType[i] = Circuit::F0;
		if (singleTest())
			err.push_back(pair<int, int>(i, 1));	
		g.sick[i] = 1, g.sickType[i] = Circuit::F1;
		if (singleTest())
			err.push_back(pair<int, int>(i, 2));
		if (err.size() > 1)
			break;
	}
	if (err.size() > 1)
		puts("Unable to totally classify the failure");
	else {
		if (err[0].second == 0)
			printf("Gate %d is failing; output inverted\n", err[0].first);
		else if (err[0].second == 1)
			printf("Gate %d is failing; output stuck at 0\n", err[0].first);
		else if (err[0].second == 2)
			printf("Gate %d is failing; output stuck at 1\n", err[0].first);
	}
}
int main() {
	int cases = 0;
	while (scanf("%d %d %d", &N, &G, &U) == 3 && N) {
		for (int i = 1; i <= G; i++) {
			scanf("%s", s);
			if (s[0] == 'a') {
				scanf("%s %s", s1, s2);
				g.addGate(i, Circuit::AND, g.getId(s1), g.getId(s2));
			} else if (s[0] == 'o') {
				scanf("%s %s", s1, s2);
				g.addGate(i, Circuit::OR, g.getId(s1), g.getId(s2));
			} else if (s[0] == 'x') {
				scanf("%s %s", s1, s2);
				g.addGate(i, Circuit::XOR, g.getId(s1), g.getId(s2));
			} else {
				scanf("%s", s1);
				g.addGate(i, Circuit::NOT, g.getId(s1));
			}
		}
		
		for (int i = 1; i <= U; i++)
			scanf("%d", &outGate[i]);
		scanf("%d", &B);
		assert(B < 1024);
		for (int i = 0; i < B; i++) {
			for (int j = 1; j <= N; j++)
				scanf("%d", &IN[i][j]);
			for (int j = 1; j <= U; j++)
				scanf("%d", &OUT[i][j]);
		}
		
		printf("Case %d: ", ++cases);
		test();
	}
	return 0;
}
/*
2 2 1 
o i1 i2 
n g1 
2 
2 
1 0 0 
0 0 1 
2 1 1 
a i1 i2 
1 
1 
1 0 1 
2 1 1 
a i1 i2 
1 
2 
1 0 1 
1 1 1 
1 1 1 
n i1 
1 
2 
1 1 
0 0 
3 4 4 
n g4 
a i1 i2 
o i2 i3 
x i3 i1 
2 3 4 1 
4 
0 1 0 0 1 0 1
0 1 1 0 1 1 0
1 1 1 0 1 0 1
0 0 0 0 0 0 1
0 0 0
*/
Read More +
解題區►解題區 - UVa

UVa 1078 - Steam Roller

Problem

駕駛蒸氣機在道路上，啟動蒸汽機通過道路需要時間。當要進行轉彎時，必須在轉彎口前進行煞車、出了轉彎口後開始加速，煞車和加速會造成所需時間變成兩倍，在起點出發必須加速、抵達終點時必須減速。

請問最少花費時間需要多少。

Sample Input

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

Sample Output

1
2
Case 1: 100 
Case 2: Impossible

Solution

定義狀態 dist[i][j][dir][k] 在轉彎口 (i, j)，前一次進入轉彎口的方向為 dir，在此之前是否有煞車 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
145
146
147
148
149
#include <stdio.h> 
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
const int MAXN = 128;
int cg[MAXN][MAXN][4];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int dist[MAXN][MAXN][4][2], inq[MAXN][MAXN][4][2];
int spfa(int r1, int c1, int r2, int c2) {
	if (r1 == r2 && c1 == c2)
		return 0;
	queue<int> X, Y, D, F;
	int d1, f1, x, y, w;
	memset(dist, 63, sizeof(dist));
	memset(inq, 0, sizeof(inq));
	for (int i = 0; i < 4; i++) {
		if (!cg[r1][c1][i])	continue;
		x = r1 + dx[i], y = c1 + dy[i];
		dist[x][y][i][1] = 2 * cg[r1][c1][i];
		inq[x][y][i][1] = 1;
		X.push(x), Y.push(y), D.push(i), F.push(1);
	}
	
	while (!X.empty()) {
		r1 = X.front(), X.pop();
		c1 = Y.front(), Y.pop();
		d1 = D.front(), D.pop();
		f1 = F.front(), F.pop();
		inq[r1][c1][d1][f1] = 0;
//		printf("%d %d %d %d - %d\n", r1, c1, d1, f1, dist[r1][c1][d1][f1]); 
		for (int i = 0; i < 4; i++) {
			if (!cg[r1][c1][i])	continue;
			x = r1 + dx[i], y = c1 + dy[i];
//			printf("-> %d %d\n", x, y);
			if (f1 == 1) {
				if (i == d1) {
					w = cg[r1][c1][i] + dist[r1][c1][d1][f1];
					if (dist[x][y][i][0] > w) {
						dist[x][y][i][0] = w;
						if (!inq[x][y][i][0]) {
							inq[x][y][i][0] = 1;
							X.push(x), Y.push(y), D.push(i), F.push(0);
						}
					}
				}
				w = 2 * cg[r1][c1][i] + dist[r1][c1][d1][f1];					
				if (dist[x][y][i][1] > w) {
					dist[x][y][i][1] = w;
					if (!inq[x][y][i][1]) {
						inq[x][y][i][1] = 1;
						X.push(x), Y.push(y), D.push(i), F.push(1);
					}
				}
			} else {
				if (i != d1)	continue;
				w = cg[r1][c1][i] + dist[r1][c1][d1][f1];
				if (dist[x][y][i][0] > w) {
					dist[x][y][i][0] = w;
					if (!inq[x][y][i][0]) {
						inq[x][y][i][0] = 1;
						X.push(x), Y.push(y), D.push(i), F.push(0);
					}
				}
				
				w = 2 * cg[r1][c1][i] + dist[r1][c1][d1][f1];					
				if (dist[x][y][i][1] > w) {
					dist[x][y][i][1] = w;
					if (!inq[x][y][i][1]) {
						inq[x][y][i][1] = 1;
						X.push(x), Y.push(y), D.push(i), F.push(1);
					}
				}
			}
		}
	}
	
	int ret = 0x3f3f3f3f;
	for (int i = 0; i < 4; i++)
		ret = min(ret, dist[r2][c2][i][1]);
	return ret == 0x3f3f3f3f ? -1 : ret;
}
int main() {
	int R, C, r1, c1, r2, c2;
	int x, cases = 0;
	while (scanf("%d %d %d %d %d %d", &R, &C, &r1, &c1, &r2, &c2) == 6 && R) {
		memset(cg, 0, sizeof(cg));
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C - 1; j++) {
				scanf("%d", &x);
				cg[i][j][0] = cg[i][j+1][1] = x;
			}
			if (i != R - 1) {
				for (int j = 0; j < C; j++) {
					scanf("%d", &x);
					cg[i][j][2] = cg[i+1][j][3] = x;
				}
			}
		}
		
		r1--, c1--, r2--, c2--;
		int d = spfa(r1, c1, r2, c2);
		printf("Case %d: ", ++cases);
		if (d >= 0)
			printf("%d\n", d);
		else
			printf("Impossible\n");
	}
	return 0;
}
/*
4 4 4 3 2 4
 7 6 2 
4 5 0 4 
 6 4 1 
4 4 2 2 
 9 4 4 
5 5 3 2 
 9 6 9 
4 4 1 1 4 4 
 10  10  10 
9  0  0  10 
  0  0  0 
9  0  0  10 
  9  0  0 
0  9  0  10 
  0  9  9 
4 4 1 1 1 2
 10  10  10 
9  0  0  10 
  0  0  0 
9  0  0  10 
  9  0  0 
0  9  0  10 
  0  9  9 
  
4 4 1 1 4 4
 10  10  10 
9  0  0  10 
  0  0  0 
9  0  0  10 
  9  0  0 
0  9  0  0 
  0  9  9 
*/
Read More +
解題區►解題區 - UVa

UVa 1076 - Password Suspects

Problem

給定 N 個單字，請問在長度為 M 的密碼中，密碼符合出現這 N 個單詞的情況有多少種。

在密碼個數少於 42 種時，將所有密碼輸出。

Sample Input

1
2
3
4
5
6
7
10 2 
hello 
world 
10 0 
4 1 
icpc 
0 0

Sample Output

1
2
3
4
5
6
Case 1: 2 suspects 
helloworld 
worldhello 
Case 2: 141167095653376 suspects 
Case 3: 1 suspects 
icpc

Solution

建立 AC 自動機，使用 AC 自動機上的 dp，對於每一個 node 將單字用 2^N 來表示 dp 狀態，因此每一個 node 的狀態為 dp[len][1<<N] 表示匹配長度 len，並且已經 match 到的狀態。

由於要輸出 42 以內的密碼可能，在輸出答案前，進行回溯標記，確保下一步可以抵達到可行解，接著進行 dfs 搜索。

1
2
3
4
5
6
7
8
9
1 2
a
a
1 0
2 2
b
ab

特別小心測資存在兩個單詞相同、一個單詞是另一個單詞的 substring。

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
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#include <algorithm>
#include <assert.h>
#define MAXCHAR 26
#define MAXS (1024)
#define MAXNODE 256
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
class ACmachine {
public:
    struct Node {
        Node *next[MAXCHAR], *fail;
        int cnt, val, id;
        long long dp[30][1024];
		int dpable[30][1024];
        void init() {
            fail = NULL;
            cnt = val = 0;
            id = 0;
            memset(next, 0, sizeof(next));
            memset(dp, 0, sizeof(dp));
            memset(dpable, 0, sizeof(dp));
        }
    } nodes[MAXNODE];
    Node *root;
    int size;
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = 0;
        root = getNode();
    }
    int toIndex(char c) {
        return c - 'a';
    }
    void dfs(Node *p, Node *q) {
        for (int i = 0; i < MAXCHAR; i++) {
            if (q->next[i]) {
                Node *u = p->next[i], *v = q->next[i];
                if (u == NULL)
                    p->next[i] = getNode(), u = p->next[i];
                u->cnt |= v->cnt;
                dfs(u, v);
            }
        }
    }
    void merge(const ACmachine &other) {
        dfs(root, other.root);
    }
    void insert(const char str[], int sid) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        p->cnt = 1;
        if (sid >= 0)	p->id |= 1<<sid;
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
    void build() { // AC automation
        queue<Node*> Q;
        Node *u, *p;
        Q.push(root), root->fail = NULL;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] == NULL)
                    continue;
                Q.push(u->next[i]);
                p = u->fail;
                while (p != NULL && p->next[i] == NULL)
                    p = p->fail;
                if (p == NULL)
                    u->next[i]->fail = root;
                else
                    u->next[i]->fail = p->next[i];
                u->next[i]->val = u->next[i]->fail->val + u->next[i]->cnt;
                u->next[i]->id = u->next[i]->fail->id | u->next[i]->id;
            }
        }
    }
    int query(const char str[]) {
        Node *u = root, *p;
        int matched = 0;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            while (u->next[idx] == NULL && u != root)
                u = u->fail;
            u = u->next[idx];
            u = (u == NULL) ? root : u;
            p = u;
            matched += p->val;
        }
        return matched;
    }
    long long dp(int len, int N) {
    	queue<Node*> Q;
    	Node *u, *p;
    	root->dp[0][0] = 1;
    	long long ret = 0;
    	for (int k = 0; k <= len; k++) {
    		Q.push(root), ret = 0;
    		while (!Q.empty()) {
    			u = Q.front(), Q.pop();
    			ret += u->dp[len][(1<<N)-1];
    			if (u->dp[len][(1<<N)-1])
    				u->dpable[len][(1<<N)-1] = 1;
    			for (int i = 0; i < (1<<N); i++) {
    				if (i && u->dp[k][i] == 0) 
    					continue;
    				for (int j = 0; j < MAXCHAR; j++) {
    					if (u->next[j] != NULL)
    						if (i == 0)	Q.push(u->next[j]);
    					if (u->dp[k][i] == 0)
    						continue;
    					p = u;
						while (p != root && p->next[j] == NULL)
							p = p->fail;
						p = p->next[j];
						if (p == NULL)	continue;
						if (p->id)
    						p->dp[k+1][i|p->id] += u->dp[k][i];
    					else
    						p->dp[k+1][i] += u->dp[k][i];
    				}
    			}
    		} // <end queue>
    	}
    	
    	// backtrack
    	for (int k = len-1; k >= 0; k--) {
    		Q.push(root);
    		while (!Q.empty()) {
    			u = Q.front(), Q.pop();
    			for (int i = 0; i < (1<<N); i++) {
    				if (i && u->dp[k][i] == 0) 
    					continue;
    				for (int j = 0; j < MAXCHAR; j++) {
    					if (u->next[j] != NULL)
    						if (i == 0)	Q.push(u->next[j]);	
    					if (u->dp[k][i] == 0)
    						continue;
    					p = u;
						while (p != root && p->next[j] == NULL)
							p = p->fail;
						p = p->next[j];
						if (p == NULL)	continue;
						if (p->id >= 0) {
    						if (p->dpable[k+1][i|p->id])
    							u->dpable[k][i] = 1;
    					} else {
    						if (p->dpable[k+1][i])
    							u->dpable[k][i] = 1;
    					}
    				}
    			}
    		} // <end queue>
    	}
    	return ret;
    }
    void dpSearch(Node *u, int s, int len, int N, string str, vector<string> &ret) {
    	if (str.length() == len) {
    		if (s == (1<<N)-1)
    			ret.push_back(str);
    		return ;
    	}
    	if (u->dpable[str.length()][s] == 0)
    		return ;
    	Node *p; 
    	for (int i = 0; i < MAXCHAR; i++) {
			p = u;
			while (p != root && p->next[i] == NULL)
				p = p->fail;
			p = p->next[i];
			if (p == NULL)	continue;
    		int ns = s;
    		if (p->id >= 0)	
				ns = s|p->id;
    		dpSearch(p, ns, len, N, str + (char) (i + 'a'), ret);
    	}
    	
    }
    void free() {
        return ;
        // owner memory pool version
        queue<Node*> Q;
        Q.push(root);
        Node *u;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] != NULL) {
                    Q.push(u->next[i]);
                }
            }
            delete u;
        }
    }
};
ACmachine g;
int main() {
	int M, N, cases = 0;
	char s[1024];
    while (scanf("%d %d", &M, &N) == 2 && M+N) {
       	g.init();
       	for (int i = 0; i < N; i++) {
       		scanf("%s", s);
       		g.insert(s, i);
       	}
       	
       	for (int i = 'a'; i <= 'z'; i++) {
       		s[0] = i, s[1] = '\0';
       		g.insert(s, -1);
       	}
       	g.build();
       	long long way = g.dp(M, N);
       	printf("Case %d: %lld suspects\n", ++cases, way);
       	if (way <= 42) {
       		vector<string> pwd;
       		g.dpSearch(g.root, 0, M, N, "", pwd);
       		sort(pwd.begin(), pwd.end());
       		for (int i = 0; i < pwd.size(); i++)
       			printf("%s\n", pwd[i].c_str());
       	}
        g.free();
    }
    return 0;
}
/*
10 2 
hello 
world 
10 0 
4 1 
icpc 
10 3
mo
mom
omsi
4 4
a
b
c
d
4 3
ab
bc
ca
1 2
a
a
1 0
2 2
b
ab
0 0
 */
Read More +
解題區►解題區 - UVa

UVa 1063 - Marble Game

Problem

旋轉盤面，讓每顆球落入屬於自己的洞，請問至少需要幾次旋轉。

  • 球不能翻過牆壁、不能跨越其他球、不能飛過空洞。
  • 球不能離開盤面
  • 每一格最多只有一顆球
  • 當球落入空洞時，這個空洞相當於被填滿，其他的球可以經過這個被填滿的洞，但無法再次落入該洞。

Sample Input

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

Sample Output

1
2
3
Case 1: 5 moves 
Case 2: impossible

Solution

首先有可能落錯空洞，模擬時必須特別小心這種非法的旋轉。在一次操作中，有可能在落入空洞的瞬間，下一個球剛好可以通過這個填滿的洞。

將每個球的座標壓成狀態，進行 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
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 <queue>
#include <map>
#include <string.h>
#include <algorithm>
using namespace std;
int N, W;
struct state {
	vector< pair<int, int> > xy;
	bool operator<(const state &a) const {
		for (int i = 0; i < xy.size(); i++)
			if (xy[i] != a.xy[i])
				return xy[i] < a.xy[i];
		return false;
	}
	int isComplete() {
		int ok = 1;
		for (int i = 0; i < xy.size() && ok; i++)
			ok &= xy[i].first < 0;
		return ok;
	} 
};
int g[4][4][4];
pair<int, int> goal[64];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int isValid(int x, int y) {
	return x >= 0 && y >= 0 && x < W && y < W;
}
state eraseGoal(state u) {
	for (int i = 0; i < u.xy.size(); i++) {
		if (u.xy[i] == goal[i])
			u.xy[i] = pair<int, int>(-1, -1);
	}
	return u;
}
state rotateMap(state u, int dir, int& ok) {
	ok = 1;
	int update = 1, tx, ty, x, y;
	int used[4][4] = {}, usedg[4][4] = {};
	for (int i = 0; i < u.xy.size(); i++) {
		x = u.xy[i].first, y = u.xy[i].second;
		if (x == -1)	continue;
		used[x][y] = 1;
		x = goal[i].first, y = goal[i].second;
		usedg[x][y] = i+1;
	}
	do {
		update = 0;
		for (int i = 0; i < u.xy.size(); i++) {
			while (u.xy[i].first >= 0) {
				x = u.xy[i].first, y = u.xy[i].second;
				tx = x + dx[dir], ty = y + dy[dir];
				if (isValid(tx, ty) && !g[x][y][dir] && usedg[tx][ty] && usedg[tx][ty] != i+1)
					ok = 0;
				if (isValid(tx, ty) && !g[x][y][dir] && (!used[tx][ty] || goal[i] == make_pair(tx, ty))) {
					used[x][y] = 0, used[tx][ty] = 1;
					u.xy[i] = pair<int, int>(tx, ty);
					update = 1;
					if (goal[i] == pair<int, int>(tx, ty)) {
						u.xy[i] = pair<int, int>(-1, -1);
						used[tx][ty] = 0, usedg[tx][ty] = 0;
					}
				} else {
					break;
				}
			}
		} 
	} while (update);
	return u;
}
void print(state u) {
	int used[4][4] = {}, x, y;
	for (int i = 0; i < u.xy.size(); i++) {
		x = u.xy[i].first, y = u.xy[i].second;
		if (x == -1)
			continue;
		used[x][y] = i+1;
	}
	for (int i = 0; i < W; i++) {
		for (int j = 0; j < W; j++)
			printf("%d ", used[i][j]);
		puts("");
	}
	puts("--");
}
int bfs(state init) {
	state u, v;
	queue<state> Q;
	map<state, int> R;
	int f;
	
	init = eraseGoal(init);
	Q.push(init), R[init] = 0;
//	print(init);
	if (init.isComplete())
		return 0;
	
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		int step = R[u];
		
//		print(u);
//		printf("step %d\n", step);
		for (int i = 0; i < 4; i++) {
			v = rotateMap(u, i, f);
			v = eraseGoal(v);
			if (!f || R.count(v))		continue;
			if (v.isComplete())
				return step + 1;
			R[v] = step + 1;
//			print(v);
			Q.push(v);
		}
//		puts("--------------");
//		getchar();
	}
	return -1;
}
int main() {
	int x, y, tx, ty, M;
	int sx, sy, ex, ey;
	int cases = 0;
	while (scanf("%d %d %d", &W, &N, &M) == 3 && N+W+M) {
		state init;
		memset(g, 0, sizeof(g));
		
		for (int i = 0; i < N; i++) {
			scanf("%d %d", &x, &y);
			init.xy.push_back(pair<int, int>(x, y));
		}
		for (int i = 0; i < N; i++) {
			scanf("%d %d", &x, &y);
			goal[i] = pair<int, int>(x, y);
		}
		for (int i = 0; i < M; i++) {
			scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
			for (int j = 0; j < 4; j++) {
				tx = sx + dx[j], ty = sy + dy[j];
				if (tx == ex && ty == ey)
					g[sx][sy][j] = 1;
				tx = ex + dx[j], ty = ey + dy[j];
				if (tx == sx && ty == sy)
					g[ex][ey][j] = 1;
			}
		}
		
		int step = bfs(init);
		
		printf("Case %d: ", ++cases);
		if (step < 0)
			puts("impossible");
		else
			printf("%d moves\n", step);
		puts("");
	}
	return 0;
}
/*
3 1 5
1 2
1 0
2 1 2 2
0 0 1 0
0 1 1 1
0 2 1 2
1 1 2 1
4 3 1
0 1 
1 0 
1 2 
2 3 
2 1 
3 2 
1 1 1 2
3 2 2
0 0 
0 1 
0 2 
2 0 
2 0 1 0
2 0 2 1
*/
Read More +
解題區►解題區 - UVa

UVa 1049 - Remember the A La Mode

Problem

販售冰淇淋。

已知每一種口味的冰淇淋、不同種的冰淇淋脆皮的庫存量，也已知冰淇淋口味與脆皮之間搭配獲得的利益。

求出在兜售完畢的情況下，最大獲益、最小獲益分別為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2 3 
40 50 
27 30 33 
1.11 1.27 0.70 
-1 2 0.34 
4 4 
10 10 10 10 
10 10 10 10 
1.01 -1 -1 -1 
-1 1.01 -1 -1 
-1 -1 1.01 -1 
-1 -1 -1 1.01 
0 0

Sample Output

1
2
Problem 1: 91.70 to 105.87 
Problem 2: 40.40 to 40.40

Solution

保證在兜售完畢的情況下，相當於 maxflow 流滿，那麼可以套用最少費用流來找到最少利益。為了解決最大獲益，取個補數來套用最少費用流模型。

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <functional>
#include <deque>
#include <algorithm>
using namespace std;
#define MAXN 2048
#define MAXM 1048576
struct Node {
    int x, y, cap;
	double cost;// x->y, v
    int next;
} edge[MAXM];
class MinCost {
public:
    int e, head[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
    int dis[MAXN];
    int n;
    const int INF = 0x3f3f3f3f;
    void Addedge(int x, int y, int cap, int cost) {
        edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
        edge[e].next = head[x], head[x] = e++;
        edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
        edge[e].next = head[y], head[y] = e++;
    }
    pair<int, int> mincost(int s, int t) {
        int mncost = 0;
		int flow, totflow = 0;
        int i, x, y;
        while(1) {
        	for (int i = 0; i < n; i++)
        		dis[i] = INF;
            int oo = dis[0];
            dis[s] = 0;
            deque<int> Q;
            Q.push_front(s);
            while(!Q.empty()) {
                x = Q.front(), Q.pop_front();
                inq[x] = 0;
                for(i = head[x]; i != -1; i = edge[i].next) {
                    y = edge[i].y;
                    if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                        dis[y] = dis[x] + edge[i].cost;
                        pre[y] = x, record[y] = i;
                        if(inq[y] == 0) {
                            inq[y] = 1;
                            if(Q.size() && dis[Q.front()] > dis[y])
                                Q.push_front(y);
                            else
                                Q.push_back(y);
                        }
                    }
                }
            }
            if(dis[t] == oo)
                break;
            flow = 0x3f3f3f3f;
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                flow = min(flow, edge[ri].cap);
            }
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                edge[ri].cap -= flow;
                edge[ri^1].cap += flow;
                edge[ri^1].cost = -edge[ri].cost;
            }
            totflow += flow;
            mncost += dis[t] * flow;
        }
        return make_pair(mncost, totflow);
    }
    void init(int n) {
    	this->n = n;
        e = 0;
        for (int i = 0; i <= n; i++)
            head[i] = -1;
    }
} g;
int readDouble() {
	static char s[16];
	scanf("%s", s);
	if (s[0] == '-')	return -1;
	int i, x = 0;
	for (i = 0; s[i] && s[i] != '.'; i++)
		x = x * 10 + s[i] - '0';
	if (!s[i])	return x * 100;
	i++;
	x = x * 10 + s[i] - '0';
	if(!s[i+1]) return x * 10;
	i++;
	x = x * 10 + s[i] - '0';
	return x;
}
int main() {
    int N, M, Nsz[64], Msz[64], cases = 0;
    int NMp[64][64];
    while (scanf("%d %d", &N, &M) == 2 && N) {
    	
  		for (int i = 0; i < N; i++)
            scanf("%d", &Nsz[i]);
        for (int i = 0; i < M; i++)
        	scanf("%d", &Msz[i]);
        for (int i = 0; i < N; i++)
        	for (int j = 0; j < M; j++)
        		NMp[i][j] = readDouble();
        	
        int source = N + M, sink = N + M + 1;
        g.init(N + M + 2);
        for (int i = 0; i < N; i++) 
        	g.Addedge(source, i, Nsz[i], 0);
        for (int i = 0; i < M; i++) 
        	g.Addedge(i + N, sink, Msz[i], 0);
        for (int i = 0; i < N; i++) {
        	for (int j = 0; j < M; j++) {
        		if (NMp[i][j] < 0) 	continue;
        		g.Addedge(i, j + N, 0x3f3f3f3f, NMp[i][j]);
        	}
        }
        pair<int, int> ret1 = g.mincost(source, sink);
        
        g.init(N + M + 2);
        for (int i = 0; i < N; i++) 
        	g.Addedge(source, i, Nsz[i], 0);
        for (int i = 0; i < M; i++) 
        	g.Addedge(i + N, sink, Msz[i], 0);
        	
        const int ADD = 50 * 100 * 2000;
        for (int i = 0; i < N; i++) {
        	for (int j = 0; j < M; j++) {
        		if (NMp[i][j] < 0) 	continue;
        		g.Addedge(i, j + N, 0x3f3f3f3f, ADD - NMp[i][j]);
        	}
        }
        pair<int, int> ret2 = g.mincost(source, sink);
        double r1, r2;
        r1 = ret1.first / 100.0;
        r2 = (ret2.second * ADD - ret2.first) / 100.0;
        printf("Problem %d: ", ++cases);
 		printf("%.2lf to %.2lf\n", r1, r2);
    }
    return 0;
}
Read More +
解題區►解題區 - UVa

UVa 1048 - Low Cost Air Travel

Problem

給定多組組合票價的方案，以及目標的通行順序，請問最少花費需要多少。

組合票必須按照順序使用，當沒有使用完時，選擇將組合票拋棄。組合票之間，不會發生交替使用剩餘的部分，意即手上只能持有一張組合票，之前用到一半的組合票都必須拋棄。

目標的行程順序，走訪時中間可能會多繞路，但必須依序走訪目的地。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
3 
225 3 1 3 4 
200 2 1 2 
50 2 2 3 
1 
2 1 3 
3 
100 2 2 4 
100 3 1 4 3 
200 3 1 2 3 
2 
3 1 4 3 
3 1 2 4 
0

Sample Output

1
2
3
4
5
6
Case 1, Trip 1: Cost = 225
  Tickets used: 1
Case 2, Trip 1: Cost = 100
  Tickets used: 2
Case 2, Trip 2: Cost = 300
  Tickets used: 3 1

Solution

建圖方面相當麻煩，特別小心，有可能會在行程外的地點換組合票使用。

每個點的狀態為 (i, j)，表示完成行程中第 i 個目的地，當前位置在地圖編號 j。因此針對每一個組合票，嘗試建造從行程中的第 i 個目的地，到下一個目的地。

隨後求最短路徑。

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
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <queue>
#include <map>
using namespace std;
const int MAXNT = 32767;
vector<int> route[MAXNT];
int NTc[MAXNT], NT;
struct Edge {
	int to, w, label;
	Edge(int a = 0, int b = 0, int c = 0):
		to(a), w(b), label(c) {}
};
vector<Edge> g[MAXNT];
map< pair<int, int>, int> Rid;
int getId(pair<int, int> x) {
	if (Rid.count(x))
		return Rid[x];
	int &r = Rid[x];
	return r = Rid.size();
}
pair<int, int> dist[MAXNT];
int pre[MAXNT][2], inq[MAXNT];
void spfa(int st) {
	memset(dist, 63, sizeof(dist));
	memset(pre, -1, sizeof(pre));
	memset(inq, 0, sizeof(inq));
	
	int u, v;
	queue<int> Q;
	
	Q.push(st), dist[st] = pair<int, int>(0, 0);
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		inq[u] = 0;
		for (int i = 0; i < g[u].size(); i++) {
			v = g[u][i].to;
			if (dist[v] > pair<int, int>(dist[u].first + g[u][i].w, dist[u].second+1)) {
				dist[v] = pair<int, int>(dist[u].first + g[u][i].w, dist[u].second+1);
				pre[v][0] = u, pre[v][1] = g[u][i].label;
				if (!inq[v]) {
					inq[v] = 1, Q.push(v);
				}
			}
		}
	}
}
void solve(int N, int A[]) {
	for (int i = 0; i < MAXNT; i++) 
		g[i].clear();
	Rid.clear();
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < NT; j++) {
			int st = i, ed = i;
			for (int k = 0; k < route[j].size(); k++) {
				if (ed+1 < N && route[j][k] == A[ed+1])
					ed++;
				int u = getId(pair<int, int>(st, route[j][0]));
				int v = getId(pair<int, int>(ed, route[j][k]));
				g[u].push_back(Edge(v, NTc[j], j));
//				printf("[%d] %d -> %d\n", j, u, v);
				if (ed == N)
					break;
			}
		}
	}
	
	int st = getId(pair<int, int>(0, A[0]));
	int ed = getId(pair<int, int>(N-1, A[N-1]));
	spfa(st);
	
	vector<int> buy;
	for (int i = ed; i >= 0; i = pre[i][0])
		buy.push_back(pre[i][1]);
	printf("Cost = %d\n", dist[ed].first);
	printf("  Tickets used:");
	for (int i = (int) buy.size() - 2; i >= 0; i--)
		printf(" %d", buy[i]+1);
	puts("");
}
int main() {
	int N, Q, cases = 0;
	int A[MAXNT];
	while (scanf("%d", &NT) == 1 && NT) {
		for (int i = 0; i < NT; i++) {
			int m, x;
			scanf("%d %d", &NTc[i], &m);
			route[i].clear();
			for (int j = 0; j < m; j++) {
				scanf("%d", &x);
				route[i].push_back(x);
			}
		}
		
		scanf("%d", &Q), ++cases;
		for (int i = 0; i < Q; i++) {
			scanf("%d", &N);
			for (int j = 0; j < N; j++)
				scanf("%d", &A[j]);
			printf("Case %d, Trip %d: ", cases, i+1);
			solve(N, A);
		}
	}
	return 0;
} 
/*
3 
225 3 1 3 4 
200 2 1 2 
50 2 2 3 
3
2 1 3 
1 1
0
3 
100 2 2 4 
100 3 1 4 3 
200 3 1 2 3 
2 
3 1 4 3 
3 1 2 4 
0
*/
Read More +
解題區►解題區 - UVa

UVa 1555 - Garland

Problem

給定 N 盞燈，第一盞燈的所在高度 A。

  • Hi = (Hi-1 + Hi+1)/2 - 1

在 Hi 不低於地面高度 0 的條件下，請問最後一盞燈的高度最低為何。

Sample Input

1
692 532.81

Sample Output

1
446113.34

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
#include <stdio.h>
double isValid(int N, double H1, double H2) {
	double H = 0;
	for (int i = 3; i <= N; i++) {
		H = 2 * H2 + 2 - H1;
		if (H < 0)	return -1;
		H1 = H2;
		H2 = H;
	}
	return H;
}
int main() {
	int N;
	double A;
	while (scanf("%d %lf", &N, &A) == 2) {
		double l = 0, r = A, mid, ret = 0, t;
		for (int it = 0; it < 50; it++) {
			mid = (l + r)/2;
			if ((t = isValid(N, A, mid)) >= 0)
				r = mid, ret = t;
			else
				l = mid;
		}
		printf("%.2lf\n", ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12477 - Good Measures of Dispersion

Problem

詢問區間最大值、最小值、標準差

  • 修改區間內所有元素 A[l, r] = val。
  • 增加區間內所有元素 A[l, r] += val。

Sample Input

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

Sample Output

1
2
3
4
5
Case 1:
13/1 10
6/1 6
8/1 8
0/1 0

Solution

利用線段樹的懶操作，解決區間修改問題。

特別注意到區間的 assign 優先權高於 add，當懶操作 assign 被指派時，取消 add。將懶操作標記在節點 x 上，其 x 已經統計好結果，若發生要走訪 x 的子樹，將標記傳遞給子樹。

標準差的部分，可以利用 平方和 和 總和 計算之，因此紀錄總共需要四項 sum, sqr, mx, mn 來完成此題。

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
#include <stdio.h> 
#include <algorithm>
using namespace std;
const int MAXN = 524288;
class SegmentTree {
public:
	struct Node {
		long long sum, sqr, mx, mn;
		pair<int, long long> label[2];
		void init() {
			sum = sqr = 0;
			mx = -1LL<<60, mn = 1LL<<60;
			label[0] = label[1] = make_pair(0, 0);
		}
	} nodes[MAXN];
	long long A[MAXN];
	void pushDown(int k, int l, int r) {
		int mid = (l + r)/2;
		if (nodes[k].label[0].first) {
			assignUpdate(k<<1, l, mid, nodes[k].label[0].second);
			assignUpdate(k<<1|1, mid+1, r, nodes[k].label[0].second);
			nodes[k].label[0] = make_pair(0, 0); // cancel
		}
		if (nodes[k].label[1].first) {
			addUpdate(k<<1, l, mid, nodes[k].label[1].second);
			addUpdate(k<<1|1, mid+1, r, nodes[k].label[1].second);
			nodes[k].label[1] = make_pair(0, 0); // cancel
		}
	}
	void pushUp(int k) {
		nodes[k].sum = nodes[k<<1].sum + nodes[k<<1|1].sum;
		nodes[k].sqr = nodes[k<<1].sqr + nodes[k<<1|1].sqr;
		nodes[k].mx = max(nodes[k<<1].mx, nodes[k<<1|1].mx);
		nodes[k].mn = min(nodes[k<<1].mn, nodes[k<<1|1].mn);
	}
	void build(int k, int l, int r) { 
		nodes[k].init();
		if (l == r) {
			nodes[k].sum = A[l];
			nodes[k].sqr = A[l] * A[l];
			nodes[k].mx = nodes[k].mn = A[l];
			return ;
		}
		int mid = (l + r)/2;
		build(k<<1, l, mid);
		build(k<<1|1, mid+1, r);
		pushUp(k);
	} 
	// operator, assign > add
	void assignUpdate(int k, int l, int r, long long val) {
		nodes[k].label[0] = make_pair(1, val);
		nodes[k].label[1] = make_pair(0, 0); // cancel lower priority
		nodes[k].sum = (long long) (r - l + 1) * val;
		nodes[k].sqr = (long long) (r - l + 1) * val * val;
		nodes[k].mn = nodes[k].mx = val;
	}
	void addUpdate(int k, int l, int r, long long val) {
		nodes[k].label[1].first = 1;
		nodes[k].label[1].second += val;
		nodes[k].sqr += 2LL * val * nodes[k].sum + (long long) (r - l + 1) * val * val;
		nodes[k].sum += (long long) (r - l + 1) * val;
		nodes[k].mn += val;
		nodes[k].mx += val;
	}
	void assign(int k, int l, int r, int x, int y, int val) {
		if (x <= l && r <= y) {
			assignUpdate(k, l, r, val);
			return;
		}
		pushDown(k, l, r);
		int mid = (l + r)/2;
		if (x <= mid)
			assign(k<<1, l, mid, x, y, val);
		if (y > mid)
			assign(k<<1|1, mid+1, r, x, y, val);
		pushUp(k);
	}
	void add(int k, int l, int r, int x, int y, int val) {
		if (x <= l && r <= y) {
			addUpdate(k, l, r, val);
			return;
		}
		pushDown(k, l, r);
		int mid = (l + r)/2;
		if (x <= mid)
			add(k<<1, l, mid, x, y, val);
		if (y > mid)
			add(k<<1|1, mid+1, r, x, y, val);
		pushUp(k);
	}
	// query 
	long long r_sum, r_sqr, r_mx, r_mn;
	void qinit() {
		r_sum = r_sqr = 0;
		r_mx = -1LL<<60, r_mn = 1LL<<60;
	}
	void query(int k, int l, int r, int x, int y) {
		if (x <= l && r <= y) {
			r_sum += nodes[k].sum;
			r_sqr += nodes[k].sqr;
			r_mx = max(r_mx, nodes[k].mx);
			r_mn = min(r_mn, nodes[k].mn);
			return ;
		}
		pushDown(k, l, r);
		int mid = (l + r)/2;
		if (x <= mid)
			query(k<<1, l, mid, x, y);
		if (y > mid)
			query(k<<1|1, mid+1, r, x, y);
	}
} tree;
long long llgcd(long long x, long long y) {
	long long t;
	while (x%y)
		t = x, x = y, y = t%y;
	return y;
}
int main() {
	int testcase, cases = 0;
	int n, q;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &q);
		for (int i = 1; i <= n; i++)
			scanf("%lld", &tree.A[i]);
			
		tree.build(1, 1, n);
		
		printf("Case %d:\n", ++cases);
		for (int i = 0; i < q; i++) {
			int cmd, l, r, val;
			scanf("%d", &cmd);
			if (cmd == 0) { // assign [l, r] = val
				scanf("%d %d %d", &l, &r, &val);
				tree.assign(1, 1, n, l, r, val);
			} else if (cmd == 1) { // add [l, r] = val
				scanf("%d %d %d", &l, &r, &val);
				tree.add(1, 1, n, l, r, val);
			} else if (cmd == 2) {
				scanf("%d %d", &l, &r);
				
				tree.qinit();
				tree.query(1, 1, n, l, r);
				
				long long m = (r - l + 1), g;
				long long a = tree.r_sqr * m - tree.r_sum * tree.r_sum;
				long long b = m * m;
				g = llgcd(a, b);
				a /= g, b /= g;
				printf("%lld/%lld ", a, b);
				printf("%lld\n", tree.r_mx - tree.r_mn);
			}
		}
	}
	return 0;
}
/*
999
9 6
-1 3 2 4 -2 8 0 5 -7
2 3 6
0 5 5 2
2 3 6
1 4 7 1
2 3 7
2 1 1
9 6
-1 3 2 4 -2 8 0 5 -7
2 3 6
0 5 5 2
2 3 6
1 4 7 1
2 3 7
2 1 1
*/
Read More +
解題區►解題區 - UVa

UVa 11098 - Battle II

Problem

每個炸彈都有引爆範圍、炸彈半徑、以及炸彈所在座標。

  • 引爆一個炸彈時，其爆炸範圍內的其他炸彈也會被引爆，產生連鎖反應一次引爆多顆炸彈。
  • 引爆過的炸彈，無法再次引爆。
  • 引爆一個炸彈的成本與爆炸範圍成正比 1 : 1。

求平均花費 (引爆總花費 / 引爆次數) 最小為何？

Sample Input

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

Sample Output

1
Case #1: 1 0 2

Solution

問平均最少花費是有原因的，如果只問最少花費只需要引爆無法被連鎖的炸彈，或者在 SCC 連通元件中找一個花費最小的炸彈。

首先，在一個連鎖反應下，先做 SCC 進行縮點，知道一個 SCC 元件中用花費最小的那個炸彈代表即可，將圖轉換成 DAG 後。indegree = 0 的點必然需要手動引爆，在這樣的情況下，已經能讓所有炸彈引爆。

為了要讓平均花費最小，勢必增加引爆炸彈的數量，引爆時便能降低平均花費，但引爆的順序必須按照拓樸排序，否則會違反 引爆過的炸彈，無法再次引爆 的規則。

藉此，根據貪心策略，將非 indegree = 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
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
// SCC, DAG, greedy
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN = 1024;
class SCC {
public:
	int n;
	vector<int> g[MAXN], dag[MAXN];
	// <SCC begin>
	int vfind[MAXN], findIdx;
	int stk[MAXN], stkIdx;
	int in_stk[MAXN], visited[MAXN];
	int contract[MAXN];
	int scc_cnt;
	// <SCC end>
	int scc(int u) {
	    in_stk[u] = visited[u] = 1;
	    stk[++stkIdx] = u, vfind[u] = ++findIdx;
	    int mn = vfind[u], v;
	    for(int i = 0; i < g[u].size(); i++) {
	    	v = g[u][i];
	        if(!visited[v])
	            mn = min(mn, scc(v));
	        if(in_stk[v])
	            mn = min(mn, vfind[v]);
	    }
	    if(mn == vfind[u]) {
	        do {
	            in_stk[stk[stkIdx]] = 0;
	            contract[stk[stkIdx]] = scc_cnt;
	        } while(stk[stkIdx--] != u);
	        scc_cnt++;
	    }
	    return mn;
	}
	void addEdge(int u, int v) { // u -> v
		g[u].push_back(v);
	}
	void solve() {
		for (int i = 0; i < n; i++)
			visited[i] = in_stk[i] = 0;
        scc_cnt = 0;
        for (int i = 0; i < n; i++) {
        	if (visited[i])	continue;
        	stkIdx = findIdx = 0;
        	scc(i);
        }
	}
	void make_DAG() {
		int x, y;
		for (int i = 0; i < n; i++) {
			x = contract[i];
			for (int j = 0; j < g[i].size(); j++) {
				y = contract[g[i][j]];
				if (x != y)
					dag[x].push_back(y);
			}
		}
		for (int i = 0; i < scc_cnt; i++) {
			sort(dag[i].begin(), dag[i].end());
			dag[i].resize(unique(dag[i].begin(), dag[i].end()) - dag[i].begin());
		}
	}
	void init(int n) {
		this->n = n;
		for (int i = 0; i < n; i++)
			g[i].clear(), dag[i].clear();
	}
} g;
int X[MAXN], Y[MAXN], E[MAXN], R[MAXN];
void greedy() {
	int m = g.scc_cnt, n = g.n;
	int cost[MAXN], scc_id[MAXN], pick[MAXN] = {};
	for (int i = 0; i < m; i++)
		cost[i] = 0x3f3f3f3f, scc_id[i] = -1;
	for (int i = 0; i < n; i++) {
		if (cost[g.contract[i]] > E[i])
			cost[g.contract[i]] = E[i], scc_id[g.contract[i]] = i;
	}
	
	int indeg[MAXN]	= {};
	vector<int> topo;
	queue<int> Q;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < g.dag[i].size(); j++) {
			indeg[g.dag[i][j]]++;
		}
	}
		
	// greedy, let reta / retb = minimum value
	// if (reta / retb) > (reta + cost) / (retb + 1)
	long long reta = 0, retb = 0; // min average cost = total cost / #bomb
	vector< pair<int, int> > candidate;
	for (int i = 0; i < m; i++) {
		if (indeg[i] == 0) {
			reta += cost[i], retb++;
			pick[i] = 1;
		} else {
			candidate.push_back(make_pair(cost[i], i));
		}
	}
	sort(candidate.begin(), candidate.end()); 
	for (int i = 0; i < candidate.size(); i++) {
		long long c = candidate[i].first;
		if (reta * (retb + 1) > (reta + c) * retb) {
			reta += c, retb++;
			pick[candidate[i].second] = 1;
		}
	}
	
	// topo
	for (int i = 0; i < m; i++)
		if (indeg[i] == 0)	Q.push(i);
	while (!Q.empty()) {
		int u = Q.front(), v;
		Q.pop();
		topo.push_back(u);
		for (int i = 0; i < g.dag[u].size(); i++) {
			v = g.dag[u][i];
			if (--indeg[v] == 0)
				Q.push(v);
		}
	}
	
	// make order with fire rule
	int topo_r[MAXN] = {};
	vector< pair<int, int> > ret;
	for (int i = 0; i < topo.size(); i++) {
		topo_r[topo[i]] = i;
	}
	for (int i = 0; i < m; i++) {
		if (pick[i])
			ret.push_back(make_pair(topo_r[i], scc_id[i]));
	}
	sort(ret.begin(), ret.end());
	
	for (int i = ret.size() - 1; i >= 0; i--)
		printf(" %d", ret[i].second);
	puts("");
//	printf("%lld / %lld\n", reta, retb);
}
int main() {
	int testcase, cases = 0;
	int n;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			scanf("%d %d %d %d", &X[i], &Y[i], &R[i], &E[i]);
		
		g.init(n);	
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j)
					continue;
				long long dist = (long long)(X[i] - X[j]) * (X[i] - X[j]) + (long long)(Y[i] - Y[j]) * (Y[i] - Y[j]);
				long long r = (long long)(R[i] + E[i] + R[j]) * (R[i] + E[i] + R[j]);
				if (dist <= r) 
					g.addEdge(i, j);
			}
		}
		
		g.solve();
		g.make_DAG();
		
		printf("Case #%d:", ++cases);
		greedy();
	}
	return 0;
}
/*
1
3
4 7 2 2
8 5 1 0
3 -3 1 1
1
7
24 1 4 7
38 33 4 3
13 13 2 0
34 1 0 0
6 25 5 4
1 14 3 7
30 35 1 6
*/
Read More +