解題區►解題區 - UVa

UVa 250 - Pattern Matching Prelims

Problem

對於一個 N * M 的灰階矩陣，找一個重心 $(c_{x}, c_{y})$，重心會符合將

$$|column[0, c_{x}-1] - column[c_{x}+1, N-1]| \\ |row[0, c_{y}-1] - row[c_{y}+1, M-1]|$$

最小化, 其中 column, row 表示該列、該行的總和。如果有數個相同，則盡可能輸出最右小角的座標 (座標值越大越好)

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5 5
0.1 0.2 0.1 0.2 0.1
0.1 0.2 0.3 0.1 0.1
0.2 0.3 0.1 0.1 0.3
0.4 0.1 0.1 0.1 0.2
0.2 0.2 0.3 0.3 0.1
5 10
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2
0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3
0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.6
0 0

Sample Output

1
2
Case 1: center at (3, 3)
Case 2: center at (4, 6)

Solution

其實會發現 x 軸、y 軸的結果可以分開計算，是不會影響最後的結果，兩別分別取最佳的位置即可。

而為了求這個值，累計每一行、列的總和，使用 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
#include <stdio.h>
#include <math.h>
int main() {
#define eps 1e-6
	int n, m, cases = 0;
	while(scanf("%d %d", &n, &m) == 2 && n+m) {
		double row[128] = {}, col[128] = {};
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				double x;
				scanf("%lf", &x);
				row[i] += x, col[j] += x;
			}
		}
		double left = 0, right = 0;
		double diff = 1e+30;
		int cx, cy;
		for(int i = 1; i < n; i++)
			right += row[i];
		for(int i = 0; i < n; i++) {
			if(fabs(right - left) < diff + eps) {
				diff = fabs(right - left);
				cx = i;
			}
			left += row[i], right -= row[i+1];
		}
		left = right = 0;
		diff = 1e+30;
		for(int i = 1; i < m; i++)
			right += col[i];
		for(int i = 0; i < m; i++) {
			if(fabs(right - left) < diff + eps) {
				diff = fabs(right - left);
				cy = i;
			}
			left += col[i], right -= col[i+1];
		}
		printf("Case %d: center at (%d, %d)\n", ++cases, cx+1, cy+1);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 239 - Tempus et mobilius. Time and motion

Problem

有一個神秘的球時鐘，球時鐘會有三個堆疊位置，分別是存放每分鐘、每五分鐘、每一個小時的球球，軌道每一分鐘會將一個球釋出，並且滾入位置，放置的位置優先順序為每分鐘、每五分鐘、每小時。

如果滾入的位置分別滿了 5, 12, 12 個球，則該位置的球將會按照原本進入順序的反順序放入軌道隊列的最晚端。在剛好滿的那個瞬間，那個球將會到次優先的位置去。

假使球有各自的編號，請問在第幾天的同一個時刻後，會回到原本的位置。

Sample Input

1
2
3
30
45
0

Sample Output

1
2
30 balls cycle after 15 days.
45 balls cycle after 378 days.

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
#include <stdio.h> 
#include <stack>
#include <queue>
using namespace std;
long long gcd(long long x, long long y) {
	for(long long t; x%y; t = x, x = y, y = t%y);
	return y;
}
int main() {
	int n;
	while(scanf("%d", &n) == 1 && n) {
		// simulation
		queue<int> Q;
		stack<int> minute, five, hour;
		for(int i = 0; i < n; i++)
			Q.push(i);
		for(int i = 0; i < 24 * 60; i++) {
			int x = Q.front();
			Q.pop();
			if(minute.size() < 4) {
				minute.push(x);
			} else {
				while(!minute.empty())
					Q.push(minute.top()), minute.pop();
				if(five.size() < 11)
					five.push(x);
				else {
					while(!five.empty())
						Q.push(five.top()), five.pop();
					if(hour.size() < 11)
						hour.push(x);
					else {
						while(!hour.empty())
							Q.push(hour.top()), hour.pop();
						Q.push(x);
					}
				}
			}
		}
		
		// permutation group
		int M[8192], visited[8192] = {};
		for(int i = 0; i < n; i++)
			M[i] = Q.front(), Q.pop();
		long long ret = 1;
		for(int i = 0; i < n; i++) {
			if(visited[i] == 0) {
				int j, len = 1;
				visited[i] = 1;
				for(j = M[i]; j != i; j = M[j]) {
					visited[j] = 1, len++;
				}
				ret = ret / gcd(ret, len) * len;
			}
		}
		printf("%d balls cycle after %lld days.\n", n, ret);  
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 221 - Urban Elevations

Problem

給定一個三維空間建築物配置，給予每一個建築物西南方的端點，以及距離的深度，面向的建築物寬度和高度。求從南面往北面看過去，有多少建築物是可以被看到一部分的？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
14
160 0 30 60 30
125 0 32 28 60
95 0 27 28 40
70 35 19 55 90
0 0 60 35 80
0 40 29 20 60
35 40 25 45 80
0 67 25 20 50
0 92 90 20 80
95 38 55 12 50
95 60 60 13 30
95 80 45 25 50
165 65 15 15 25
165 85 10 15 35
0

Sample Output

1
2
For map #1, the visible buildings are numbered as follows:
5 9 4 3 10 2 1 14

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
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Building {
	int x, y;
	int width, depth, height, label;
	int in() {
		return scanf("%d %d %d %d %d", &x, &y, &width, &depth, &height) == 5;
	}
	bool operator<(const Building &a) const {
		if(make_pair(x, y) != make_pair(a.x, a.y))
			return make_pair(x, y) < make_pair(a.x, a.y);
		return depth < a.depth;
	}
}; 
int coverL(vector< pair<int, int> > interval, int l, int r) {
	sort(interval.begin(), interval.end());
	int y = l;
	for(int i = 0; i < interval.size(); i++) {
		if(interval[i].first <= y)
			y = max(y, interval[i].second);
		else
			return 0;
	}
	return y >= r;
}
void solve(Building D[], int n) {
	sort(D, D+n);
	int f = 0;
	for(int i = 0; i < n; i++) {
		vector< pair<int, int> > interval;
		for(int j = 0; j < n; j++) {
			if(j == i)	continue;
			if(D[i].height > D[j].height || D[i].y <= D[j].y)
				continue;
			int l = max(D[i].x, D[j].x), r = min(D[i].x+D[i].width, D[j].x+D[j].width);
			if(l < r)
				interval.push_back(make_pair(l, r));
		}
		if(!coverL(interval, D[i].x, D[i].x + D[i].width)) {
			if(f++)	putchar(' ');
			printf("%d", D[i].label + 1);
		}
	}
	puts("");
}
int main() {
	int n, cases = 0;
	Building D[128];
	while(scanf("%d", &n) == 1 && n) {
		for(int i = 0; i < n; i++)
			D[i].in(), D[i].label = i;
		if(cases++)	puts("");
		printf("For map #%d, the visible buildings are numbered as follows:\n", cases);
		solve(D, n);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 215 - Spreadsheet Calculator

Problem

給一張 N * M 的試算表，並且給定每一格的值可以倚靠其他欄位的結果。是否存在循環依賴？如果不存在則將每一格的答案計算出，否則將輸出存有循環依賴上的所有格子情形。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2 2
A1+B1
5
3
B0-A1
3 2
A0
5
C1
7
A1+B1
B0+A1
0 0

Sample Output

1
2
3
4
5
6
7
      0     1
A     3     5
B     3    -2
A0: A0
B0: C1
C1: B0+A1

Solution

其實就最簡單就是利用高斯消去找解，但是測資中最討厭的地方在於假使 A0 = A0-A0 這種情況也要算依賴關係，那麼高斯消去仍然找得到所有變數的解。

所以最後還是弄一個 dfs 找是否會抵達環上任何一點。

如果將這些資訊排除，圖就是一個 DAG，不用高斯消去也是相當容易的模擬計算。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
void gaussianElimination(double mtx[][256], int n, double sol[], int nosol[]) {
#define eps 1e-6
    int i, j;		
    for(i = 0; i < n; i++) {
        int k = i;
        for(j = i; j < n; j++)
            if(fabs(mtx[k][i]) < fabs(mtx[j][i]))
                k = j;
        if(fabs(mtx[k][i]) < eps)
            continue;
        if(k != i) {
            for(j = 0; j <= n; j++)
                swap(mtx[k][j], mtx[i][j]);
        }
        for(j = 0; j < n; j++) {
            if(i == j)  continue;
            for(k = n; k >= i; k--) {
                mtx[j][k] -= mtx[j][i]/mtx[i][i]*mtx[i][k];
            }
        }
    }	
//	for(int i = 0; i < n; i++) {
//		for(int j = 0; j <= n; j++)
//			printf("%lf ", mtx[i][j]);
//		puts("");
//	}
    for(int i = 0; i < n; i++)
    	nosol[i] = 0;
    for(i = n-1; i >= 0; i--) {
        if(fabs(mtx[i][i]) < eps)
            nosol[i] = 1;
        else {
            if(fabs(mtx[i][n]) < eps)
                sol[i] = 0;
            else
                sol[i] = mtx[i][n]/mtx[i][i];
        }
        for(j = i+1; j < n; j++)
            if(fabs(mtx[i][j]) > eps && nosol[j])
                nosol[i] = 1;
    }
}
vector<int> depend[512];
int visited[512], in_stk[512];
int dfs(int u, int p) {
	visited[u] = 1, in_stk[u] = 1; 
	for(int i = 0; i < depend[u].size(); i++) {
		int v = depend[u][i];
		if(in_stk[v])	return 1;
		if(visited[v] == 0 && dfs(v, u))
			return 1;
	}
	in_stk[u] = 0;
	return 0;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	int N, M;
	char s[1025], exp[32][32][128];
	while(scanf("%d %d", &N, &M) == 2 && N+M) {
		while(getchar() != '\n');
		
		int notsolvable[256];
		double f[256][256] = {}, value[256];
		
		for(int i = 0; i < N * M; i++) {
			depend[i].clear();
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				scanf("%s", s);
				strcpy(exp[i][j], s);
				int sign = 1;
				f[i * M + j][i * M + j] = 1;
				for(int k = 0; s[k]; k++) {
					if(s[k] == '+')			sign = 1;
					else if(s[k] == '-')	sign = -1;
					else if('0' <= s[k] && s[k] <= '9') {
						int num = 0;
						while('0' <= s[k] && s[k] <= '9')
							num = num * 10 + s[k] - '0', k++;
						k--;
						f[i * M + j][N * M] += sign * num;
					} else {
						int rol = s[k] - 'A', num = 0;
						k++;
						while('0' <= s[k] && s[k] <= '9')
							num = num * 10 + s[k] - '0', k++;
						k--;
						f[i * M + j][rol * M + num] -= sign;
						depend[i * M + j].push_back(rol * M + num);
					}
				}
			}
		}
		gaussianElimination(f, N*M, value, notsolvable);
		for(int i = 0; i < N*M; i++) {
			memset(visited, 0, sizeof(visited));
			memset(in_stk, 0, sizeof(in_stk));
			notsolvable[i] |= dfs(i, i);
		}
		int allsol = 1;
		for(int i = 0; i < N*M; i++) {
//			printf("%lf %d\n", value[i], notsolvable[i]);
			allsol &= !notsolvable[i];
		}
		if(allsol) {
			printf(" ");
			for(int i = 0; i < M; i++)
				printf("%6d", i);
			puts("");
			for(int i = 0; i < N; i++) {
				printf("%c", i + 'A');
				for(int j = 0; j < M; j++)
					printf("%6d", (int)value[i * M +j]);
				puts("");
			}
		} else {
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					if(notsolvable[i * M + j]) {
						printf("%c%d: %s\n", i + 'A', j, exp[i][j]);
					}
				}
			}
		}
		puts("");
	} 
	return 0;
}
/*
2 2
A1+B1
5
3
B0-A1
3 2
A0
5
C1
7
A1+B1
B0+A1
0 0
*/
Read More +
解題區►解題區 - UVa

UVa 11871 - New Land

Problem

題目給定在 n * m 的格子中，以及一些障礙物，求一個最大空白矩形。

Sample Input

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

Sample Output

1
2
Case 1: 12
Case 2: 3

Solution

帶入單調堆。

線性時間 O(NM) 完成。紀錄每一列的向左拓展最寬為何，然後對於每一列(假設它是矩形的最右側的邊上)找到最大矩形。

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
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <string.h>
#define maxL ((2048*2048)>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
using namespace std;
int mark[maxL];
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
// http://mypaper.pchome.com.tw/zerojudge/post/1326159411
int solve(int n, int h[]) {
    int ret = 0;
    int i, height;
    stack< pair<int, int> > stk;// <height, position>
    pair<int, int> e;
    stk.push(make_pair(-1, 0));
    h[n] = 0;// visual height.
    for(i = 0; i <= n; i++) {
        height = h[i];
        e = make_pair(height, i);
        while(height < stk.top().first) {
            e = stk.top(), stk.pop();
            ret = max(ret, (i - e.second) * e.first);
        }
        if(height > stk.top().first)
            stk.push(make_pair(height, e.second));
    }
    return ret;
}    
int n, m, h[2048];
int main() {
	int k, c, x, cases = 0, testcase;
	ReadInt(&testcase);
    while(testcase--) {
    	ReadInt(&n);
    	ReadInt(&m);
    	memset(mark, 0, sizeof(mark));
    	memset(h, 0, sizeof(h));
        for(int i = 0; i < n; i++) {
        	ReadInt(&k);
        	ReadInt(&c);
        	int pos = 0;
            for(int j = 0; j < k; j++) {
            	ReadInt(&x);
				c = !c;
				if(c) {
            		while(x--)
            			SET(i * 2048 + pos), pos++;
            	} else {
            		pos += x;
            	}
            }
        }
        int ret = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
            	if(GET(j * 2048 + i))
            		h[j]++;
            	else
            		h[j] = 0;
            }
            ret = max(ret, solve(n, h));
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11870 - Antonyms

Problem

告訴你那些是同義詞，以及誰與誰是反義詞，最後回報是否有矛盾情況。

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
3
2 2
big large
small tiny
big small
tiny huge
2 1
xyz abc
abc def
def xyz
1 3
fire flame
fire ice
ice water
water fire

Sample Input

1
2
3
Case 1: YES
Case 2: NO
Case 3: NO

Solution

對於每個詞建立兩個節點 (正反兩種意思的節點)，同義詞則對兩個正做連接，只需要對建造反義祠的時候檢查，查詢每次是否會落在相同集合的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h> 
#include <string.h>
#include <map>
#include <iostream>
using namespace std;
int p[2048], rank[2048];
int findp(int x) {
	return p[x] == x ? x : (p[x]=findp(p[x]));
}
int joint(int x, int y) {
	x = findp(x), y = findp(y);
	if(x == y)	return 0;
	if(rank[x] > rank[y])
		p[y] = x, rank[x] += rank[y];
	else
		p[x] = y, rank[y] += rank[x];
	return 1;
}
int main() {
	int testcase, cases = 0, N, M;
	char s[1024];
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d %d", &N, &M);
		map<string, int> R;
		int size = 0;
		for(int i = 0; i < 2048; i++)
			p[i] = i, rank[i] = 1;
		for(int i = 0; i < N; i++) {
			scanf("%s", s);
			int &x = R[s];
			if(x == 0)	x = ++size;
			scanf("%s", s);
			int &y = R[s];
			if(y == 0)	y = ++size;
			joint(2 * x, 2 * y);
		}
		int ret = 1;
		for(int i = 0; i < M; i++) {
			scanf("%s", s);
			int &x = R[s];
			if(x == 0)	x = ++size;
			scanf("%s", s);
			int &y = R[s];
			if(y == 0)	y = ++size;
			if(findp(2 * x) == findp(2 * y))
				ret = 0;
			joint(2 * x + 1, 2 * y);
			joint(2 * y + 1, 2 * x);
		}
		printf("Case %d: %s\n", ++cases, ret ? "YES" : "NO");
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11851 - Celebrity Split

Problem

家產劃分給兩個人，兩個人分配的房子總價值必須相同，剩下無法劃分的房子將換成現金分配給兩個人，求換成現金的總額最小為何？

Sample Input

1
2
3
4
5
6
7
5
6000000
30000000
3000000
11000000
3000000
0

Output for Sample Input

1
41000000

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <functional>
using namespace std;
int n;
long long A[32], suffix[32], ret;
void dfs(int i, long long x, long long y, long long sold) {
	if(sold >= ret || abs(x - y) > suffix[i])	return;
	if(x == y)
		ret = min(ret, sold + suffix[i]);
	if(i == n)
		return;
	if(x == y) {
		dfs(i+1, x + A[i], y, sold);
		dfs(i+1, x, y, sold + A[i]);
	} else {
		dfs(i+1, x + A[i], y, sold);
		if(x)
			dfs(i+1, x, y + A[i], sold);
		dfs(i+1, x, y, sold + A[i]);
	}
}
int main() {
	while(scanf("%d", &n) == 1 && n) {
		for(int i = 0; i < n; i++)
			scanf("%lld", &A[i]);
		sort(A, A+n, greater<long long>());
		suffix[n] = 0;
		for(int i = n-1; i >= 0; i--)
			suffix[i] = suffix[i+1] + A[i];
		ret = 1LL<<60;
		dfs(0, 0, 0, 0);
		printf("%lld\n", ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11848 - Cargo Trains

Problem

在 N 個點的地圖中，有兩家運輸公司 A, B，如果它們都有在 x, y 之間部屬線路，則運輸費用將會根據參數 a 進行調整 a * Ca + (1 - a) * Cb，求從編號 0 到 N-1 的最少花費為何。

Sample input

1
2
3
4
5
6
7
8
9
3 2 2 3
0 1 100
1 2 200
0 1 200
1 2 150
0
1
0.5
-1 -1 -1 -1

Sample Output

1
2
3
350
300
325

Solution

每一次詢問 a 的時候，就做一次 spfa。似乎沒有別的方法可以預處理訊息。

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
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
int gA[128][128], gB[128][128];
int spfa(int st, int ed, int n, double p) {
	double dist[128];
	int inq[128] = {}, u, v;
	queue<int> Q;
	for(int i = 0; i < n; i++)
		dist[i] = 1e+10;
	dist[st] = 0, Q.push(st);
	while(!Q.empty()) {
		u = Q.front(), Q.pop();
		inq[u] = 0;
		for(int i = 0; i < n; i++) {
			int wa = gA[u][i], wb = gB[u][i];
			double cost = 0;
			if(wa < 0 && wb < 0)	continue;
			if(wa >= 0 && wb >= 0)
				cost = wa * p + wb * (1-p);
			else
				cost = wa >= 0 ? wa : wb;
			if(dist[i] > dist[u] + cost) {
				dist[i] = dist[u] + cost;
				if(!inq[i])
					inq[i] = 1, Q.push(i);
			}
		}
	}
	return (int)dist[ed];
}
int main() {
	int N, Na, Nb, Q;
	int x, y, v;
	double p;
	while(scanf("%d %d %d %d", &N, &Na, &Nb, &Q) == 4 && N >= 0) {
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
				gA[i][j] = gB[i][j] = -1;
		for(int i = 0; i < Na; i++) {
			scanf("%d %d %d", &x, &y, &v);
			if(gA[x][y] != -1)
				gA[x][y] = gA[y][x] = min(gA[x][y], v);
			else
				gA[x][y] = gA[y][x] = v;
		}
		for(int i = 0; i < Nb; i++) {
			scanf("%d %d %d", &x, &y, &v);
			if(gB[x][y] != -1)
				gB[x][y] = gB[y][x] = min(gB[x][y], v);
			else
				gB[x][y] = gB[y][x] = v;
		}
		for(int i = 0; i < Q; i++) {
			scanf("%lf", &p);
			printf("%d\n", spfa(0, N-1, N, p));
		}
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11844 - The Melding Plague

Problem

給定每一個蛋白質在下一個時刻會變成什麼，從一開始的各種蛋白質類型的數量，是否會在哪一個時刻符合目標蛋白質種類的數量。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
2 5 4 3
CAD CELR2
ELTD1 XIRP2
POMC 1
CAD 2
SCN5A 2
XIRP2 1
ELTD1 1
POMC 1
CELR2 2
SCN5A 2
XIRP2 2
2 3 3 3
GP183 NALCN
CAC1S GP183
CAC1S 2
YCFI 1
MRP6 3
YCFI 1
MRP6 3
NALCN 2
2 3 3 1
GP183 NALCN
CAC1S GP183
CAC1S 2
YCFI 1
MRP6 3
YCFI 1
MRP6 3
NALCN 2
3 2 1 2
CAD YCFI
ELTD1 XIRP2
CAD SCN5A
CAD 1
YCFI 1
YCFI 2
0 0 0 0

Sample Output

1
2
3
4
Cure found in 1 mutation(s)
Cure found in 2 mutation(s)
Nostalgia for Infinity is doomed
Protein mutations are not deterministic

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
#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <map>
using namespace std;
map<string, int> R;
int getLabel(string s) {
	int &x = R[s];
	return x == 0 ? x = R.size() : x;
}
#define MAXN 4096
int main() {
	int Nm, Ni, Nc, n, x, y;
	char s[MAXN];
	while(scanf("%d %d %d %d", &Nm, &Ni, &Nc, &n) == 4) {
		if(Nm + Ni + Nc + n == 0)
			break;
		R.clear();
		int Icnt[MAXN] = {}, Ccnt[MAXN] = {}, g[MAXN] = {};
		int eflag = 0;
		for(int i = 1; i < MAXN; i++)
			g[i] = i;
		for(int i = 0; i < Nm; i++) {
			scanf("%s", s);
			x = getLabel(s);
			scanf("%s", s);
			y = getLabel(s);
			if(g[x] != x && g[x] != y)	eflag = 1;
			g[x] = y;
		}
		for(int i = 0; i < Ni; i++) {
			scanf("%s %d", s, &y);
			x = getLabel(s);
			Icnt[x] = y;
		}
		for(int i = 0; i < Nc; i++) {
			scanf("%s %d", s, &y);
			x = getLabel(s);
			Ccnt[x] = y;
		}
		if(eflag) {
			puts("Protein mutations are not deterministic");
			continue;
		}
		eflag = 1;
		for(int i = 0; i <= n; i++) {			
			if(memcmp(Icnt, Ccnt, sizeof(Icnt)) == 0) {
				printf("Cure found in %d mutation(s)\n", i);
				eflag = 0;
				break;
			}
			int next[MAXN] = {};
			for(int j = 1; j <= R.size(); j++) {
				next[g[j]] += Icnt[j];
			}
			memcpy(Icnt, next, sizeof(next));
		}
		if(eflag)
			puts("Nostalgia for Infinity is doomed");
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11828 - Palindrome Again

Problem

You are given a string S of length N. Can you find a string P which satisfies the following conditions?

  1. Length of P will be N

  2. Distance between S and P will be less than or equal to K

  3. P will be a palindrome.

  4. P can contain only characters ‘a’, ‘b’, …, ‘z’

You have to calculate, in how many ways you can choose P. This number can be very large, so print the answer modulo 1000000000 (109).

Notes:

  • A string is a sequence of characters. For this problem consider that all strings can contain only ‘a’, ‘b’, …, ‘z’, i.e. 26 available characters.

  • The length of the string is defined by the number of characters in the string. For example, length of “abcba” is 5.

  • A string is called palindrome when it is the same string when written from forwards or backwards. For example – “abcba”, “abba”, “a” are palindrome but “abc” is not a palindrome.

  • Distance between two string of same length is the number of mismatches of corresponding characters. For example, distance between “abcb” and “bcba” is 4 because no character of first string matches to the character of the corresponding index of second string, but distance between “abc” and “cba” is 2.

    Input

Input starts with an integer T (T is around 5000), the number of test cases.

Each test case consists of two lines. First line contains two integers N(1≤N≤1000) and K (0≤K≤1000). Second line contains a string S of length N. S contains only characters from ‘a’, ‘b’, …, ‘z’.

Output

For each test case output the number of test cases followed by the number of ways the string can be chosen modulo 1000000000 (109). See sample output for exact format.

Sample Input

1
2
3
4
5
6
7
3
3 2
kxk
4 1
addc
4 3
addc

Output for Sample Input

1
2
3
Case 1: 51
Case 2: 2
Case 3: 76

Solution

題目描述：

對一個 S 字串，修改最多 K 個字符的情況下，求最多有多少不同的字符串是迴文

題目解法：

最樸素的算法，對於每個字串 S，使用 O(NK) 的算法，利用 dp[N][K] 表示對於前綴長為 N，已經修改了 K 個字符的總數為何。

先來看最樸素的寫法，一定會拿 TLE，原因是詢問的次數過多。

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
// TLE
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <ctype.h>
using namespace std;
int main() {
	int testcase, cases = 0, N, K;
	char s[1024];
	long long dp[2][1024];
	long long mod = 1000000000LL;
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d %d %s", &N, &K, s);
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		int froll = 0, L = N/2 + N%2;
		for(int i = 0; i < N; i++)
			s[i] = tolower(s[i]);
		for(int i = 0; i < L; i++) {
			memset(dp[!froll], 0, sizeof(dp[!froll]));
			int diff, cos;
			diff = s[i] == s[N - i - 1] ? 0 : 1;
			cos = i == N - i - 1 ? 1 : 2;
			for(int j = 0; j <= K; j++) {
				if(diff) {
					dp[!froll][j + 2] += dp[froll][j] * 24;
					dp[!froll][j + 1] += dp[froll][j] * 2;
				} else {
					dp[!froll][j + cos] += dp[froll][j] * 25; // using diff
					dp[!froll][j] += dp[froll][j];
				}
				dp[!froll][j] %= mod;
			}
			froll = !froll;
		}
		long long ret = 0;
		for(int i = 0; i <= K; i++)
			ret = (ret + dp[froll][i])%mod;
		printf("Case %d: %lld\n", ++cases, ret);
	}
	return 0;
}

之後，仔細拆解之後，發現由於只會考慮字串的一半，並且條件分為兩種，原本就已經匹配還是沒有匹配，而事實上我們可以分成 P, Q 兩種形式。

  • P = number of characters where a[i] = a[n-i-1];
  • Q = number of characters where a[i] != a[n-i-1];

所以考慮預先建表，將這兩個事件獨立分開計算，最後乘積起來就可以了。

對於 P, Q 的情況，分別建立 dp(i, j) 為目前 i 個字符，恰好修改 j 次的迴文字串數量。但是題目要求為 最多修改 K 次，因此對 P, Q 其中一種進行調整為 dp(i, j) 為目前 i 個字符，修改最多 j 次的回文字串數量。

因此對於每次詢問，可以在 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 <algorithm>
#include <ctype.h>
using namespace std;
long long dp1[1024][1024], dp2[1024][1024];
long long mod = 1000000000LL;
/*
P= number of characters where a[i] = a[n-i-1];
Q= number of characters where a[i] != a[n-i-1];
*/
long long solve(int P, int Q, int K) {
	long long ret = 0;
	for(int i = 0; i <= K; i++)
		ret = (ret + dp1[P][i] * dp2[Q][K - i])%mod;
	return ret;
}
int main() {
	dp1[0][0] = dp2[0][0] = 1;
	// dp1(P, K), dp2(Q, K)
	for(int i = 1; i < 1024; i++) {
		for(int j = 0; j < 1024; j++) {
			if(j >= 2)
				dp1[i][j] += dp1[i - 1][j - 2] * 25;
			dp1[i][j] += dp1[i - 1][j];
			if(j >= 1)
				dp2[i][j] += dp2[i - 1][j - 1] * 2;
			if(j >= 2)
				dp2[i][j] += dp2[i - 1][j - 2] * 24;
			dp1[i][j] %= mod, dp2[i][j] %= mod;
		}
	}
	// 
	for(int i = 0; i < 1024; i++) {
		for(int j = 1; j < 1024; j++)
			dp2[i][j] = (dp2[i][j] + dp2[i][j-1])%mod;
	}
	
	int testcase, cases = 0, N, K;
	char s[1024];
	
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d %d %s", &N, &K, s);
		int P = 0, Q = 0;
		for(int i = 0; i < N/2; i++) {
			P += s[i] == s[N - i - 1];
			Q += s[i] != s[N - i - 1];
		}
		long long ret = 0;
		if(N&1)
			ret = (solve(P, Q, K) + solve(P, Q, K - 1) * 25) %mod;
		else
			ret = solve(P, Q, K);
		printf("Case %d: %lld\n", ++cases, ret);
	}
	return 0;
}
Read More +