解題區►解題區 - UVa

UVa 12897 - Decoding Baby Boos

Problem

每一個主字串，接著根據一大堆規則， 依序 將字母做替換。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
AVVU_TUMI_COLING_PARO_NAY
3
B V
D L
H Y
AABBCCY
3
A B
B C
C A

Sample Output

1
2
ABBU_TUMI_CODING_PARO_NAH
CCCCBBY

Solution

由於主字串可能很長，不用針對每次詢問將每一個主字串都拿來修改。只需考量每一種字符轉換的可能，例如源頭 ‘A’ -> ‘Z’, ‘B’ -> ‘X’, ‘C’ -> ‘Z’, … 那麼，接下來遇到 ‘Z’ -> ‘W’，只需要針對 ‘A’ -> ‘W’, ‘C’ -> ‘W’ 即可。

因此，每一次詢問最多消耗 O(26) 完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h> 
#include <string.h>
using namespace std;
char s[1048576];
int main() {
	int testcase, n;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%s", s);
		scanf("%d", &n);
		
		char R[128], s1[10], s2[10];
		for (int i = 0; i < 128; i++)
			R[i] = i;
		for (int i = 0; i < n; i++) {
			scanf("%s %s", s1, s2);
			for (int j = 'A'; j <= 'Z'; j++)
				if (R[j] == s2[0])
					R[j] = s1[0];
		}
		
		for (int i = 0; s[i]; i++)
			putchar(R[s[i]]);
		puts("");
	}
	return 0;
}
/*
2
AVVU_TUMI_COLING_PARO_NAY
3
B V
D L
H Y
AABBCCY
3
A B
B C
C A
*/
Read More +
解題區►解題區 - UVa

UVa 12874 - Blanket

Problem

寒冷的冬天，為街道上的人鋪設毛毯，現在有 n 個無限長毛毯，每一個毛毯都有其紋路，呈現厚薄厚薄厚薄 … 的順序，其中厚的長度為 ai，而薄的長度為 bi - ai。

現在長度為 1…m 的街道，請問蓋到 1 件、2 件、3 件、 …、n 件薄毛毯的人分別有多少人。

Sample Input

1
2
3
4
5
1
3 30
2 5
3 5
3 6

Sample Output

1
2
3
4
6
9
9
6

Solution

看到 ai, bi <= 16。

窮舉每個人，O(16) 計算蓋到幾件薄毛毯。

如果用 O(nm) 顯然太慢，由於 bi 很小，針對所有可能，預建表得到循環下累計結果。

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
#include <stdio.h> 
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;
}
int ret[131072];
int main() {
	int testcase, n, m;
//	scanf("%d", &testcase);
	ReadInt(&testcase);
	while (testcase--) {
//		scanf("%d %d", &n, &m);
		ReadInt(&n);
		ReadInt(&m);
		int A[20][20] = {}, a, b;
		for (int i = 0; i < n; i++) {
//			scanf("%d %d", &a, &b);
			ReadInt(&a);
			ReadInt(&b);
			A[b][a]++;
		}
		for (int i = 1; i <= 16; i++) {
			for (int j = 1; j <= 16; j++)
				A[i][j] += A[i][j-1];
		}
		for (int i = 0; i <= n; i++)
			ret[i] = 0;
		for (int i = 0; i < m; i++) {
			int cover = 0;
			for (int j = 1, t; j <= 16; j++) {
				t = i%j;
				cover += A[j][16] - A[j][t];
			}
			ret[cover]++;
		}
		for (int i = 0; i <= n; i++)
			printf("%d\n", ret[i]);
	}
	return 0;
}
/*
9999
3 30
2 5
3 5
3 6
2 15
1 2
3 4
*/
Read More +
解題區►解題區 - UVa

UVa 12846 - A Daisy Puzzle Game

Problem

有一套撥花瓣遊戲，一朵花有 n 片花瓣，每一片花瓣分別位置在 1…n，呈現環狀，首尾相連。兩個人輪流撥花瓣，每一次撥一片、或者撥相鄰的兩片，最後一個取走花瓣的人輸。

給已經撥去花瓣，請問現在她先手會不會勝利？

Sample Input

1
2
3
4
5
2
13 1
7
5 3
1 3 4

Sample Output

1
2
Case 1: yes
Case 2: no

Solution

看出是一道 SG 博奕遊戲，假設有 n 個連續花瓣，取中間一片、或連續兩片，將會變成兩段連續花瓣，藉此建造 SG 函數，求出連續 n 個連續花瓣的 SG 值，隨後統計有多少段連續花瓣，並且各自擁有多少花瓣，接著套用 nim 遊戲得到結果。

特別小心是環狀的，題目沒有描述得很清楚。

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int SG[1024];
void buildSG() {
	int mex[1024] = {};
	SG[0] = 0;
	for (int i = 1; i < 50; i++) {
		memset(mex, 0, sizeof(mex));
		for (int j = 0; j < i; j++) {
			mex[SG[j] ^ SG[i-j-1]] = 1;
			if (i-j-2 >= 0)
				mex[SG[j] ^ SG[i-j-2]] = 1;
		}
		int sg = 0;
		for (sg; mex[sg]; sg++);
		SG[i] = sg;
	}
}
int main() {
	buildSG();
	int testcase, cases = 0, n, m, x;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &m);
		int used[64] = {}, last = 0;
		for (int i = 0; i < m; i++) {
			scanf("%d", &x);
			x--;
			used[last = x] = 1;
		}
		
		vector<int> nim;
		for (int i = 0, tmp = 0, pos; i < n; i++) {
			pos = (last + i)%n;
			if (used[pos] == 0)
				tmp++;
			if (used[pos] || i == n-1) {
				if (tmp)
					nim.push_back(tmp);
				tmp = 0;
			}
		}
		
		int ret = 0;
		for (int i = 0; i < nim.size(); i++)
			ret ^= SG[nim[i]];
		printf("Case %d: %s\n", ++cases, ret ? "yes" : "no");
	}
	return 0;
}
/*
9999
13 1
7
5 3
1 3 4
6 2
1 5
1 1
1
1 0
*/
Read More +
解題區►解題區 - UVa

UVa 12837 - Hasmot Ali Professor

Problem

給定一個主字串 S，接著數筆詢問有多少不同的子字串以 X 開頭、Y 結尾。

Sample Input

1
2
3
4
5
6
1
abab
3
a a
a b
ba ab

Sample Output

1
2
3
4
Case 1:
2
2
1

Solution

由於題目是要找不同的子字串，必然會造成比對速度上的問題，由於主子串長度最多 1000，而詢問的 X、Y 長度都小於 10，顯然地窮舉是相當有利。但是詢問次數最多 50000，窮舉起來必須有效率地映射到答案中，因此建議離線把詢問建成一個 Trie，同時避免重複的詢問。

窮舉每個子字串，為了加速匹配，最多跑 O(len * len * 10 * 10)，當決定子字串為 [l, r] 時，遞增起頭指針、遞減結尾指針，對於每一組詢問串成 X#inv(Y)，那麼只需要循序走訪一棵 trie，如此一來速度就提升了不少。

接著考慮如何去重複，關鍵點在於窮舉每個子字串，也依序插入 trie 中，當有新增新的節點時再進行答案的驗證。

也許這類型的題目可以先建造一個 suffix tree，然後想辦法詢問，仔細想想不容易就放棄。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
struct TrieNode {
    int n;
    int link[27];
} Node[1048576<<2];
int TrieSize;
int rename(char c) {
	if ('a' <= c && c <= 'z')
		return c - 'a';
	return 26;
}
void insertTrie(const char* str, int root) {
	static int i, idx, c;
	for(i = 0, idx = root; str[i]; i++) {
		c = rename(str[i]);
		if(Node[idx].link[c] == 0) {
			TrieSize++;
			memset(&Node[TrieSize], 0, sizeof(Node[0]));
			Node[idx].link[c] = TrieSize;
		}
		idx = Node[idx].link[c];
	}
}
TrieNode* getTrieNode(const char* str, int root) {
	static int i, idx, c;
	for(i = 0, idx = root; str[i]; i++) {
		c = rename(str[i]);
		if(Node[idx].link[c] == 0) {
			TrieSize++;
			memset(&Node[TrieSize], 0, sizeof(Node[0]));
			Node[idx].link[c] = TrieSize;
		}
		idx = Node[idx].link[c];
	}
	return &Node[idx];
}
const int MAXQL = 10 - 1;
const int MAXQ = 50000;
char ms[MAXQ][32];
int main() {
	int testcase, q, cases = 0;
	char s1[32], s2[32], s[1024];
	int A[1024], B[1024];
	scanf("%d", &testcase);
    while(testcase--) {
    	scanf("%s", s);
		scanf("%d", &q);
		int sn = strlen(s), s1n, s2n, an, bn;
		TrieSize = 2;
		int root1 = 0, root2 = 1;
		memset(&Node[root1], 0, sizeof(Node[root1]));
		memset(&Node[root2], 0, sizeof(Node[root2]));
		for (int i = 0; i < q; i++) {
			scanf("%s %s", s1, s2);
			s1n = strlen(s1), s2n = strlen(s2);
			int m = 0;
			for (int j = 0; j < s1n; j++)
				ms[i][m++] = s1[j];
			ms[i][m++] = '#';
			for (int j = s2n - 1; j >= 0; j--)
				ms[i][m++] = s2[j];
			ms[i][m] = '\0';
			insertTrie(ms[i], root2);
		}
		
		for (int i = 0; i < sn; i++) {
			int idx = root1, idx2, c;
			for (int j = i; j < sn; j++) { // add s[l, r]
				c = rename(s[j]);
				if(Node[idx].link[c] == 0) {
					TrieSize++;
					memset(&Node[TrieSize], 0, sizeof(Node[0]));
					Node[idx].link[c] = TrieSize;
					// create new node == create distinct substring
					int idx2 = root2;
					int L = min(j, i + MAXQL);
					for (int k = i; k <= L; k++) { // brute head
						if (Node[idx2].link[rename(s[k])] == 0)	break;
						idx2 = Node[idx2].link[rename(s[k])];
						if (Node[idx2].link[rename('#')]) {
							int idx3 = Node[idx2].link[rename('#')];
							int R = max(i, j - MAXQL);
							for (int l = j; l >= R; l--) { // brute tail
								if (Node[idx3].link[rename(s[l])] == 0)	break;
								idx3 = Node[idx3].link[rename(s[l])];
								Node[idx3].n ++; // [l, r] = strA + ... + strB
							}
						}
					}
				}
				idx = Node[idx].link[c];
			}
		}
		printf("Case %d:\n", ++cases);
		for (int i = 0; i < q; i++) {
			TrieNode *p = getTrieNode(ms[i], root2);
			printf("%d\n", p->n);
		}
    }
    return 0;
}
/*
1
abab
3
a a
a b
ba ab
*/
Read More +
解題區►解題區 - UVa

UVa 12875 - Concert Tour

Problem

現在有位歌手，要舉辦演唱會，在各地的百貨公司打算邀請歌手來演唱，藉以吸引更多的顧客來消費。每個百貨公司提供在哪一天歌手來演唱時可以得到的獲益，歌手必須自費從另一個地點到另一個地點，因此會給定兩地之間的自費費用。可以留在原地。

求歌手在 m 天內可以獲得的最大利益為何，假設第一天到任何場地都是 0 花費，沒有指派最後一天所在的位置。

Sample Input

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

Sample Output

1
2
3
170
60
65

Solution

定義狀態 dp[stores][days]，在第幾天到哪一個城鎮。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 128
#define MAXM 64
long long dp[MAXN][MAXM];
int profit[MAXN][MAXM], cost[MAXN][MAXN];
int main() {
	int testcase, n, m;
	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", &profit[i][j]);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				scanf("%d", &cost[i][j]);
				
		memset(dp, 0, sizeof(dp));
		
		long long ret = 0;
		for (int i = 0; i < n; i++)
			dp[i][0] = profit[i][0];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					dp[k][i+1] = max(dp[k][i+1], dp[j][i] + profit[k][i+1] - cost[j][k]);
				}
			}
		}
		for (int i = 0; i < n; i++)
			ret = max(ret, dp[i][m-1]);
		printf("%lld\n", ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12887 - The Soldier's Dilemma

Problem

N 個人不同高，現在佔一排，任挑三個人的身高從左向右的相對高度，不存在矮、高、中的情況有多少種。

Sample Input

1
2
3
2
2
3

Sample Output

1
2
2
5

Solution

卡塔蘭數 (Catalan number)。

每一次考慮加入一個最高的人，窮舉最高的人應該佔在哪個位置，則其左、右側也要滿足定義，同時左側的人都要比右側的人高。最後得到公式如下，與卡塔蘭數相同。

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
#include <stdio.h> 
/*
add tallest people in position i
ways[n] = \sum ways[i] * ways[n-i-1].
			   ^^^^^^[1] ^^^^^^^^^^[2]
[1] left tree pos[0, i-1]
[2] right tree pos[i+1, n-1]
then label of right tree must small than label of left tree
=> Catalan number, an = (4n-2)/(n+1) * an-1
*/
long long inv(long long n, long long m) { // get n*? = 1 (mod m)
	long long la = 1, lb = 0, ra = 0, rb = 1;
	long long i = 0, t, mod = m;
	while(n%m) {
		if(!i) {
			la -= n/m*ra, lb -= n/m*rb;
		} else {
			ra -= n/m*la, rb -= n/m*lb;
		}
		i = !i;
		t = n, n = m, m = t%m;
	}
	return i ? (la%mod+mod)%mod : (ra%mod+mod)%mod;
}
#define MAXN 5005
long long Catalan[MAXN];
const long long mod = 1000000007LL;
int main() {
	Catalan[0] = Catalan[1] = 1;
	for (int i = 2; i < MAXN; i++) {
		Catalan[i] = Catalan[i-1] * (4 * i - 2) %mod;
		Catalan[i] = Catalan[i] * inv(i+1, mod) %mod;
	}
	int n, testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		printf("%lld\n", Catalan[n]);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12880 - Book Club

Problem

有 N 個人的愛書俱樂部，他們會喜歡某些人的書，如果相互喜歡對方的書就可以進行交換，現在要問的是否每個人都能找到能夠交換的對象，讓每個人都獲得新書。

如果 A -> B, B -> C, C -> A，那麼他們可以環狀地交換新書。

Sample Input

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

Sample Output

1
YES

Solution

每個人只能找一個對象進行交換，找二分圖的 perfect matching。

二分圖中左側是每個人，右側是想要交換的對象，兩邊的個數都是 N。匹配完會找到數個環狀，這就是最後的交換情況。然而由於點數很多，用匈牙利算法可以減枝來加快，每一次擴充路徑都必須得成功。如果使用 maxflow，則盡可能減少邊的無效使用。

當然可以使用 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
#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 n, m, x, y;
	while (scanf("%d %d", &n, &m) == 2) {
		g.Init(2 * n + 2);
		int source = 2 * n, sink = 2 * n + 1;
		for (int i = 0; i < n; i++)
			g.Addedge(source, i, 1), g.Addedge(i + n, sink, 1);
		for (int i = 0; i < m; i++) {
			scanf("%d %d", &x, &y);
			g.Addedge(x, y + n, 1);
		}
		
		int matching = g.Maxflow(source, sink);
		puts(matching == n ? "YES" : "NO");
	}
	return 0;
}
/*
9 9
0 1
1 2
2 0
3 4
4 3
5 6
6 7
7 8
8 5
*/
Read More +
解題區►解題區 - UVa

UVa 12878 - Flowery Trails

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
10 15
0 1 580
1 4 90
1 4 90
4 9 250
4 2 510
2 7 600
7 3 200
3 3 380
3 0 150
0 3 100
7 8 500
7 9 620
9 6 510
6 5 145
5 9 160
4 7
0 1 1
0 2 2
0 3 10
0 3 3
1 3 2
2 3 1
1 1 1

Sample Output

1
2
3860
18

Solution

最短路徑可能有數條，因此要窮舉每一條邊是否在最短路徑上，已知景點分別為 st 和 ed ，那麼找到 st -> u 和 ed -> v 的單源最短路徑，接下來窮舉 u -> v ，加上 st -> u 和 v -> ed ，得到 st -> u -> v -> ed 的最少花費，檢查是否等於最短路徑長即可。

這一題是雙向圖，如果是單向圖則要反轉邊，才能對 ed 進行單源最短路徑 (SSSP)。在這一題寫 SSSP 使用 SPFA 算法，也許 dijkstra 也是挺不錯的。

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
 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm> 
using namespace std;
#define MAXN 32767
vector< pair<int, int> > g[MAXN];
int dist1[MAXN], dist2[MAXN];
void spfa(int st, int ed, int dist[]) {
	static int inq[MAXN];
	queue<int> Q;
	int u, v, w;
	dist[st] = 0, Q.push(st);
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		inq[u] = 0;
		for (int i = 0; i < g[u].size(); i++) {
			v = g[u][i].first, w = g[u][i].second;
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				if (!inq[v])
					inq[v] = 1, Q.push(v);
			}
		}
	}
}
int main() {
	int n, m;
	int x, y, w;
	while (scanf("%d %d", &n, &m) == 2) {
		for (int i = 0; i < n; i++)
			g[i].clear();
		for (int i = 0; i < m; i++) {
			scanf("%d %d %d", &x, &y, &w);
			g[x].push_back(make_pair(y, w));
			g[y].push_back(make_pair(x, w));
		}
		
		for (int i = 0; i < n; i++)
			dist1[i] = dist2[i] = 0x3f3f3f3f;
		spfa(0, n-1, dist1);
		spfa(n-1, 0, dist2);
	
		int sp = dist1[n - 1], ret = 0;
		for (int i = 0; i < n; i++) {
			x = i;
			for (int j = 0; j < g[i].size(); j++) {
				y = g[i][j].first, w = g[i][j].second;
				if (dist1[x] + w + dist2[y] == sp)
					ret += w;
			}
		}
		printf("%d\n", ret * 2);
	}
	return 0;
}
/*
10 15
0 1 580
1 4 90
1 4 90
4 9 250
4 2 510
2 7 600
7 3 200
3 3 380
3 0 150
0 3 100
7 8 500
7 9 620
9 6 510
6 5 145
5 9 160
4 7
0 1 1
0 2 2
0 3 10
0 3 3
1 3 2
2 3 1
1 1 1
*/
Read More +
解題區►解題區 - UVa

UVa 12876 - City

Problem

現在給定格子狀的街區，每一個街區只會與垂直、水平的相鄰街區有通行的人行道。現在已知每個街區有多少人行道，求未知的街區人行道數量情況。

Sample Input

1
2
3
4
5
1
3 3
2 2 3
1 -1 3
1 1 0

Sample Output

1
1

Solution

二分圖黑白染色，知道每一個只會與相鄰上下左右的街區相鄰，那麼就像國際象棋一樣的黑白染色，相鄰的人行道一定只會連接於黑跟白之間。

分別計算黑和白的 degree 總數，差的絕對值就是未知街區的答案。

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
#include <stdio.h> 
#include <stdlib.h>
#include <algorithm>
using namespace std;
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;
}
int main() {
	int testcase, n, m, x;
//	scanf("%d", &testcase);
	ReadInt(&testcase);
	while (testcase--) {
//		scanf("%d %d", &n, &m);
		ReadInt(&n);
		ReadInt(&m);
		int odd = 0, even = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
//				scanf("%d", &x);
				ReadInt(&x);
				if (x == -1)	continue;
				if ((i+j)&1)
					odd += x;
				else
					even += x;
			}
		} 
		printf("%d\n", abs(odd - even));
	}
	return 0;
}
/*
1
3 3
2 2 3
1 -1 3
1 1 0
*/
Read More +
學校課程►資料庫系統

資料庫正規化 Database BCNF

Problem

stackoverflow : Decomposing a relation into BCNF.

資料庫講到正規化，針對 1NF, 2NF, 3NF 的做法。正規化的目的
－要避免資料重複或相互矛盾的情形，並使資料庫在使用時能更有效率、更容易維護。

關於 1NF, 2NF, 3NF 的細節操作就上網查吧。也就是在還沒正規化前，可能會遭遇到

  • 修改一個 f(x) = y 值時，可能修改非常大量的 row，因為有可能 f(x, z) = y，無用相依關係的 z 很多。
  • 刪除某個元素時，造成 y 值沒有被任何相依，導致 y 的資訊無法存入資料庫。 … 如此類推。

現在給定 relation 和 functional dependencies，正規化它們！

舉個例子：(直接從 stackoverflow 的例子來說)

  • Relation : R(A, C, B, D, E)
  • Functional dependencies (FD): A -> B, C -> D

Functional dependencies 簡單來說就是一個決定性的一對多、或者是一對一的相依關係，可以根據 LHS (left hand side) 決策 RHS (right hand side)，當然 function dependencies 的訊息只有部分，也暗示著具有遞移關係。因此例如 A->B, B->C 則可以推論出 A->C 。

定義 X+ 為 X 的遞移閉包，因此假設知道 A->B, B->C 則 {A}+ = {A, B, C} ，假設知道 AB->C 則 {A, B}+ = {A, B, C}

回到例子，每一步要找到違反 BCNF 規則 (violates BCNF) 的 R’ 進行拆分。怎麼樣才算違反 BCNF 規則？可以找到一個 X != X+ != [R’ all attributes] ，就可以對 R’ 進行拆分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Step 1:
S = {ABCDE}       
	R' = ABCDE, 
	find {A} != {A, B} != {A, B, C, D, E}, 
	R1 = (X+) = {A, B}
	R2 = R' - ((X+) - X) = {A, C, D, E}
Step 2:
S = {ACDE, AB}
	R' = ACDE,
	find {C} != {C, D} != {A, C, D, E}, 
	R1 = (X+) = {C, D}
	R2 = R' - ((X+) - X) = {A, C, E}
Step 3:
S = {ACE, AB, CD}
	// NOT FOUND END.

在程式實作 (非人工) 的時候，如何找到 X 滿足上述的條件很重要，由於 X 是所有變數的 subset 情況，相當於 O(2n) ，很多項目是無用的。假如 R’ = ABE ，針對 X = AC 是無效的操作，基本上只要拿所有 function dependencies 的 X = LHS 進行測試即可？這貪心的做法應該是對的。

1
2
3
4
5
6
7
BCNF_Decompose(R)
	find X s.t.: X != (X+) != [all attributes]
	if (not found) then “R is in BCNF”
	let Y = (X+) - X
	let Z = [all attributes] - (X+)
	decompose R into R1(X union Y) and R2(X union Z) 
	continue to decompose recursively R1 and R2

說真的，老師上課講的練習答案還有錯，講算法時也不夠確切，真不知道教授怎麼教的，還是我沒認真上課。當教授發現全班答題有極端的相似錯誤時，到底是我們學不好？還是他沒教好？教授一點都不會反思。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
5 2
A->B
C->D
6 3
AC->B
C->D
A->EF
6 6
AB->C
BC->AD
D->E
CF->B
BC->A
BC->D 
5 3
AB->C
DE->C
B->E

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
A->B
S = {AB, ACDE}
C->D
S = {AB, CD, ACE}
  
C->D
S = {CD, ABCEF}
A->EF
S = {ABC, CD, AEF}
  
AB->C
S = {ABCDE, ABF}
D->E
S = {ABCD, DE, ABF}
  
AB->C
S = {ABD, ABCE}
B->E
S = {ABC, ABD, BE}

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <assert.h>
using namespace std;
#define INF 0x3f3f3f3f
// stackoverflow Database: Decomposing a relation into BCNF
void parsingStmt(string s, string &l, string &r) {
    size_t pos = s.find("->");
    l = s.substr(0, pos);
    r = s.substr(pos + 2);
}
int toBitmask(string s) {
    int ret = 0;
    for (int i = 0; i < s.length(); i++) {
        assert(s[i] >= 'A' && s[i] <= 'Z');
        ret |= 1<<(s[i] - 'A');
    }
    return ret;
}
void printBitmask(int state) {
    for (int i = 0; (1<<i) <= state; i++) {
        if ((state>>i)&1)
            putchar(i + 'A');
    }
}
vector<int> LHS, RHS;
int findFD(int i) {
    int ss = i;
    for (int j = 0; j < LHS.size(); j++) {
        if ((LHS[j]&i) == LHS[j])
            ss |= RHS[j];
    }
    if (ss != i)
    	return findFD(ss);
    return ss;
}
vector<int> decomposing(vector<int> state, int fdlhs, int fdrhs) {
    vector<int> ret;
    for (int i = 0; i < state.size(); i++) { // X->Y
        int X = fdlhs, Y = fdrhs&state[i];
        if (Y != state[i] && (X&state[i]) == X && Y && X && X != Y) {
            ret.push_back(state[i]^X^Y);
            ret.push_back(Y);
        } else {
            ret.push_back(state[i]);
        }
    }
    sort(ret.begin(), ret.end());
    ret.resize(unique(ret.begin(), ret.end()) - ret.begin());
    return ret;
}
void printResult(vector<int> &ret) {
    printf("S = {");
    for (int i = 0; i < ret.size(); i++) {
        printBitmask(ret[i]);
        if (i != ret.size() - 1) {
            printf(", ");
        }
    }
    puts("}");
}
int main() {
    int n, m;
    string s;
    while (cin >> n >> m) {
        LHS.clear(), RHS.clear();
        for (int i = 0; i < m; i++) {
            cin >> s;
            string lhs, rhs;
            parsingStmt(s, lhs, rhs);
            LHS.push_back(toBitmask(lhs));
            RHS.push_back(toBitmask(rhs));
        }
        vector<int> ret;
        int update = 0;
        ret.push_back((1<<n) - 1);
        do {
            update = (int) ret.size();
            for (int i = 0; i < m; i++) {
                ret = decomposing(ret, LHS[i], findFD(LHS[i]));
                if (ret.size() > update) {	
					printBitmask(LHS[i]);
	            	printf("->");
	            	printBitmask(RHS[i]);
	            	puts("");
	                printResult(ret);
                	break;
                }            
            }
            update = ret.size() > update;
        } while (update);
    }
    return 0;
}
Read More +