解題區►解題區 - UVa

UVa 11724 - Evaluate the Expression

Problem

每個變數皆為正整數，給定一個算術表達式和變數之間的大小關係，請問最少產生出來的答案為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
3
a+b*c
2
a>b
c>b
z*(x+y)
3
z>x
x>y
z>y
a+b+c+a
0

Sample Output

1
2
3
Case 1: 4
Case 2: 9
Case 3: 4

Solution

先使用 spfa 找到根據 greedy 策略分配的變數值，如果發生負環情況直接輸出 -1。

然後使用矩陣鏈乘積的 DP 方法進行找到最小答案。

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
#include <stdio.h> 
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
char exp[1024], cond[1024];
int val[26];
int spfa(vector<int> g[]) {
	queue<int> Q;
	int inq[26] = {}, dist[26] = {};
	int cnt[26] = {};
	int u, v;
	for (int i = 0; i < 26; i++) {
		Q.push(i), dist[i] = 1;
	}
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		inq[u] = 0;
		for (int i = 0; i < g[u].size(); i++) {
			v = g[u][i];
			if (dist[v] < dist[u] + 1) {
				dist[v] = dist[u] + 1;
				if (!inq[v]) {
					inq[v] = 1, Q.push(v);
					if (++cnt[v] > 26)
						return 0;
				}
			}
		}
	}
	for (int i = 0; i < 26; i++)
		val[i] = dist[i];
	return 1;
}
int used[512][512];
long long dp[512][512];
long long dfs(int l, int r) {
	if (used[l][r])
		return dp[l][r];
	if (l == r)
		return val[exp[l] - 'a'];
	used[l][r] = 1;
	long long &ret = dp[l][r];
	ret = 1LL<<60;
	int p = 0, test = 0;
	for (int i = l; i <= r; i++) {
		if (exp[i] == '(')	p++;
		if (exp[i] == ')')	p--;
		if (p == 0 && exp[i] == '+') {
			ret = min(ret, dfs(l, i-1) + dfs(i+1, r));
			test++;
		}
		if (p == 0 && exp[i] == '*') {
			ret = min(ret, dfs(l, i-1) * dfs(i+1, r));
			test++;
		}
	}
	if (test == 0)
		ret = min(ret, dfs(l+1, r-1));
	return ret;
}
int main() {
	int testcase, cases = 0;
	int n;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%s", exp);
		scanf("%d", &n);
		vector<int> g[26];
		for (int i = 0; i < n; i++) {
			scanf("%s", cond);
			g[cond[2]-'a'].push_back(cond[0]-'a');
		}
		printf("Case %d: ", ++cases);
		if(!spfa(g)) {
			puts("-1");
		} else {
			memset(used, 0, sizeof(used));
			printf("%lld\n", dfs(0, strlen(exp) - 1));
		}
	}
	return 0;
}
/*
3
a+b*c
2
a>b
c>b
z*(x+y)
3
z>x
x>y
z>y
a+b+c+a
0
*/
Read More +
解題區►解題區 - UVa

UVa 1045 - The Great Wall Game

Problem

將棋子移動到可以形成萬里長城，也就是說移動到同一行、或同一列、或其一對角線上。

求移動得最少步數。

Sample Input

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

Sample Output

1
2
3
4
5
Board 1: 6 moves required.
  
Board 2: 0 moves required.
  
Board 3: 1 moves required.

Solution

窮舉要移動到哪裡，然後找完美匹配的最大權重 - KM 算法。

只要將移動步數弄成負權重套上去 KM 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct KM {
	int W[105][105], N;
	int mx[105], my[105]; // match arr
	int lx[105], ly[105]; // label arr
	int x[105], y[105]; // used arr
	int hungary(int nd) {
	    int i;
	    x[nd] = 1;
	    for(i = 0; i < N; i++) {
	        if(y[i] == 0 && W[nd][i] == lx[nd]+ly[i]) {
	            y[i] = 1;
	            if(my[i] == -1 || hungary(my[i])) {
	                my[i] = nd;
	                return 1;
	            }
	        }
	    }
	    return 0;
	}
	int run() {
	    int i, j, k, d;
	    memset(mx, -1, sizeof(mx));
	    memset(my, -1, sizeof(my));
	    for (int i = 0; i < N; i++)
	    	lx[i] = -0x3f3f3f3f, ly[i] = 0;
	    for(i = 0; i < N; i++)
	        for(j = 0; j < N; j++)
	            lx[i] = lx[i] > W[i][j] ? lx[i] : W[i][j];
	    for(i = 0; i < N; i++) {
	        while(1) {
	            memset(x, 0, sizeof(x));
	            memset(y, 0, sizeof(y));
	            if(hungary(i))  break;
	            d = 0x3f3f3f3f;
	            for(j = 0; j < N; j++) {
	                if(x[j]) {
	                    for(k = 0; k < N; k++)
	                        if(!y[k])
	                        d = d < lx[j]+ly[k]-W[j][k] ?
	                            d : lx[j]+ly[k]-W[j][k];
	                }
	            }
	            if(d == 0x3f3f3f3f)  break;
	            for(j = 0; j < N; j++) {
	                if(x[j])    lx[j] -= d;
	                if(y[j])    ly[j] += d;
	            }
	        }
	    }
	    int res = 0;
	    for(i = 0; i < N; i++) {
	        if(my[i] != -1)
	            res += W[my[i]][i];
	    }
	    return res;
	}
} km;
int dist(int x1, int y1, int x2, int y2) {
	return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
	int cases = 0;
    int n, x[105], y[105];
    while(scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) {
        	scanf("%d %d", &x[i], &y[i]);
        	x[i]--, y[i]--;
        }
        km.N = n;
        int ret = -0x3f3f3f3f;
        for (int i = 0; i < n; i++) {
        	for (int j = 0; j < n; j++)
        		for (int k = 0; k < n; k++)
        			km.W[j][k] = -dist(x[j], y[j], i, k);
        	ret = max(ret, km.run());
        }
        for (int i = 0; i < n; i++) {
        	for (int j = 0; j < n; j++)
        		for (int k = 0; k < n; k++)
        			km.W[j][k] = -dist(x[j], y[j], k, i);
        	ret = max(ret, km.run());
    	}
    	for (int i = 0; i < n; i++) {
        	for (int j = 0; j < n; j++)
        		km.W[j][i] = -dist(x[j], y[j], i, i);	
    	}
		ret = max(ret, km.run());
    	for (int i = 0; i < n; i++) {
        	for (int j = 0; j < n; j++)
        		km.W[j][i] = -dist(x[j], y[j], i, n - i - 1);
    	}
		ret = max(ret, km.run());
        printf("Board %d: %d moves required.\n\n", ++cases, -ret);
    }
    return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12801 - Grandpa Pepe's Pizza

Problem

現在 pizza 上有 m 個橄欖，請問是否能均分 m 塊，使得每一塊皆有一個橄欖。

Sample Input

1
2
3
4
12 3
2 8 11
12 4
4 5 7 11

Sample Output

1
2
S
N

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 <algorithm>
using namespace std;
int main() {
	int n, m, A[65536];
	while (scanf("%d %d", &n, &m) == 2) {
		for (int i = 0; i < m; i++)
			scanf("%d", &A[i]);
		A[m] = A[0] + n;
		int ret = 0, div = n/m;
		for (int i = A[0]; i < A[1]; i++) {
			int d = i, ok = 1;
			for (int j = 1; j <= m; j++) {
//				printf("(%d %d] %d\n", d, d+div, A[j]);
				if (d < A[j] && A[j] <= d + div)
					d += div;
				else {
					ok = 0;
					break;
				}
			}
//			puts("");
			if (ok) {
				ret = 1;
				break;
			}
		}
		puts(ret ? "S" : "N");
	}
	return 0;
}
/*
12 3
2 8 11
12 4
4 5 7 11
*/
Read More +
解題區►解題區 - UVa

UVa 12677 - Join two kingdoms

Problem

給兩棵樹，請問將兩個樹用一條邊連起來，則獲得新的一棵樹的最長路徑期望值為何。

Sample Input

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

Sample Output

1
2
5.350
4.400

Solution

利用 dp 方法，找到通過點 v 的 (以 v 為路徑端點)最長路徑為何，以及兩棵樹分別原有的最長路徑為何。

接著考量是否加入新一條會成為最長路徑，也就是說會通過新增加的邊。分別對每個樹的節點構成的最長路徑做排序，接著窮舉連接的點，用二分搜索找到另一個樹的節點，能夠使之成為更長的最長路徑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
#define oo 0xfffffff
using namespace std;
vector<int> g[65536];
int dp_down[65536][2], dp_up[65536];
int used[65536];
void dfs(int u) {
	used[u] = 1;
	dp_down[u][0] = dp_down[u][1] = 0;
    for(int i = 0; i < g[u].size(); i++) {
    	int v = g[u][i];
        if(used[v] == 0) {
            dfs(v);
            if(dp_down[v][0]+1 > dp_down[u][1])
                dp_down[u][1] = dp_down[v][0] + 1;
            if(dp_down[u][1] > dp_down[u][0])
                swap(dp_down[u][0], dp_down[u][1]);
        }
    }
}
void dfs2(int u, int dep) {
    dp_up[u] = dep, used[u] = 1;
    for(int i = 0; i < g[u].size(); i++) {
    	int v = g[u][i];
        if(used[v] == 0) {
            int hv;
            if(dp_down[v][0] + 1 != dp_down[u][0])
                hv = dp_down[u][0];
            else
                hv = dp_down[u][1];
            hv = max(hv, dp_up[u]);
            dfs2(v, hv+1);
        }
    }
}
int main() {
	int n, m;
	int x, y;
    while (scanf("%d %d", &n, &m) == 2) {
    	int mxpath[2][65636];
		int a_diameter = 0, b_diameter = 0;
    	for (int i = 0; i <= n; i++)
    		g[i].clear();
    	for (int i = 1; i < n; i++) {
    		scanf("%d %d", &x, &y);
    		g[x].push_back(y);
    		g[y].push_back(x);
    	}
    	memset(used, 0, sizeof(used));
    	dfs(1);
    	memset(used, 0, sizeof(used));
    	dfs2(1, 0);
    	for (int i = 1; i <= n; i++) {
    		mxpath[0][i] = max(max(dp_down[i][0], dp_down[i][1]), dp_up[i]);
    		a_diameter = max(a_diameter, dp_down[i][0] + dp_down[i][1]);
    		a_diameter = max(a_diameter, dp_down[i][0] + dp_up[i]);
    	}
    		
    	for (int i = 0; i <= m; i++)
    		g[i].clear();
    	for (int i = 1; i < m; i++) {
    		scanf("%d %d", &x, &y);
    		g[x].push_back(y);
    		g[y].push_back(x);
    	}
    	memset(used, 0, sizeof(used));
    	dfs(1);
    	memset(used, 0, sizeof(used));
    	dfs2(1, 0);
		for (int i = 1; i <= m; i++) {
    		mxpath[1][i] = max(max(dp_down[i][0], dp_down[i][1]), dp_up[i]);
    		b_diameter = max(b_diameter, dp_down[i][0] + dp_down[i][1]);
    		b_diameter = max(b_diameter, dp_down[i][0] + dp_up[i]);
    	}
    	double ret = 0, suffix[65536] = {};
    	sort(mxpath[0]+1, mxpath[0]+1+n);
    	sort(mxpath[1]+1, mxpath[1]+1+m);
    	for (int i = m; i >= 0; i--)
    		suffix[i] = suffix[i+1] + mxpath[1][i];
    	int mx_diameter = max(a_diameter, b_diameter);
    	for (int i = 1, j = m; i <= n; i++) {
    		while (j > 0 && mxpath[0][i] + mxpath[1][j] >= mx_diameter)
    			j--;
    		ret += j * mx_diameter + (suffix[j + 1] + mxpath[0][i] * (m - j) + m - j);
    	}
    	printf("%.3lf\n", ret / n / m);
    }
    return 0;
}
/*
*/
Read More +
解題區►出題解題

[ACM 題目] 學姊日談

Description

Background

某 M 正與學姊討論蘿莉控追小海女的故事。

某 M 喃喃自語 …
『用了暴力法來完成的話，就能在調整 O(1) - O(E[x]) 完成。』
『如果用一個最常見的樹鏈剖分來完成也不過是 O(log n) - O(log^2 n)』
『在一般情況下，詢問次數肯定比調整次數來得高，想一想常數還得加上去，完全贏不了啊。』

學姊在一旁說到
『那如果是單純的二元樹，有比較好做嗎？說不定有更簡化的算法來完成？』
『說不定那個 … bitvertor 還是 bitset 能完成呢。』
『這個想法難不成是找到 lowbit 嗎？我沒有暫時想法。』某 M 這麼回答道。
『也許吧 … 我也不確定』學姊簇著眉。

某 M 發了瘋似的想了一個算法
『如果我們將其轉換成 k-ary search tree，也就是說需要將節點編號重新編成有大小關係，然後維護一個 BST 來查找 lower_bound 的結果，這麼一來就是 O(k log n) - O(log n) 了！』
『啊啊啊，這個方法不可行，』
學姊將鄙視般的眼神投向某 M。看來這場病還要持續很久。

『將題目弄成找樹前綴和好了，既然暴力法有期望值的剪枝，讓它剪不了不就好了！』
『你覺得不會被其他解法坑殺嗎 …』學姊如此擔憂地表示到。
『沒關係，吾等 M 可不是說假的』

Problem

給定一棵樹，樹根 root 編號 0，每個點一開始的權重為 0。

操作 x k: 將節點 x 的權重增加 k，請輸出從 x 到 root 的權重和。

Input

輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。

接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。

Output

對於每個詢問結果輸出一行，請參照範例輸出的說明。

每組測資後空一行。

Sample Input

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

Sample Output

1
2
3
4
5
1
3
1
4
12

More

名為 “學姊”。

Solution

1
Read More +
解題區►出題解題

[ACM 題目] 計畫巧遇

Description

Background

正陷入暗戀的蘿莉控，對象正是那小海女 “能年犬”，為了與其相遇，做了一個情報偵測器，但總不能刻意繞道去相遇，這顯然會相當接近跟蹤狂。根據情報網顯示，地圖將會長得跟樹狀圖一樣，接著會有一連串的消息顯示小海女疑似出現的地方，同時也會被驗證是假消息。

能年犬

蘿莉控只想知道如果從 x 點回到家的路上，有沒有機會遇到小海女。如果事先知道將會在哪個場所相遇，就能事先準備。接下來就請你協助他了！

Problem

給定一棵樹，樹根編號 0，每個點一開始的權重為 0，操作有以下兩種。

操作 M x : 將節點 x 的權重從 0->1 或者 1->0。
操作 S x : 輸出從 x 到 root 路徑上，第一個權重為 1 的節點編號。

Input

輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。

接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。

Output

對於每個詢問結果輸出一行，請參照範例輸出的說明。

每組測資後空一行。

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
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
10
0 1
0 2
1 3
0 4
3 5
4 6
5 7
5 8
4 9
10
M 1
S 8
S 4
M 0
M 7
M 9
S 5
M 3
M 8
S 5
31
0 1
0 2
0 3
1 4
1 5
2 6 
2 7
3 8
4 9
4 10
4 11
6 12
6 13
12 14
12 15
13 16
13 17
14 18
14 19
14 20
17 21
17 22
20 23
21 24
21 25
22 26
22 27
23 28
24 29
24 30
10
M 6
S 29
S 9
M 0
S 9
S 6
S 2
M 6
S 29
S 6

Sample Output

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

Solution

1
Read More +
解題區►解題區 - UVa

UVa 12793 - Confederation

Problem

在三維空間中劃分區域，給定 N 個平面，對於每一個點而言形成 N-tuple 的資訊 (0/1 左側、右側)。請問哪一個 N-tuple 具有最多點，輸出最多的點個數即可。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2 5
1 0 0 1
2 0 0 8
0 1 0
2 2 2
3 3 3
5 5 5
2 18 4
4 8
0 0 1 1
1 0 1 2
-1 1 1 3
-1 -1 1 3
0 0 5
0 0 4
0 0 -2
1 0 5
40 19 104
13 26 84
89 -45 18
3 1 0

Sample Output

1
2
3
5

Solution

直接將平面帶入每一個點，得到 N-tuple 資訊，接著對這個資訊做 RS hash 下，直接壓 int 去做 count，這樣會快於 map<string, int>。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h> 
#include <map> 
#include <algorithm>
using namespace std;
int main() {
	int n, m, x, y, z;
	int A[512], B[512], C[512], D[512];
	while (scanf("%d %d", &n, &m) == 2) {
		for (int i = 0; i < n; i++)
			scanf("%d %d %d %d", A+i, B+i, C+i, D+i);
		map<unsigned int, int> R;
		for (int i = 0; i < m; i++) {
			scanf("%d %d %d", &x, &y, &z);
			unsigned int a = 63689, b = 378551;
			unsigned int value = 0;
			for (int j = 0; j < n; j++) {
				if (A[j] * x + B[j] * y + C[j] * z > D[j])
					value = value * a + 1;
				else
					value = value * a + 0;
				a *= b;
			}
			R[value]++;
		}
		int ret = 0;
		for (map<unsigned int, int>::iterator it = R.begin();
			it != R.end(); it++)
				ret = max(ret, it->second);
		printf("%d\n", ret);
	}
	return 0;
}
/*
*/
Read More +
解題區►解題區 - UVa

UVa 12796 - Teletransport

Problem

目標從太空船 S 到太空船 T，每一個太空船上有 N 個按鈕，每一種按鈕可以傳送到指定的太空船上，請問 L 步從 S 到 T 的按法有幾種。

Sample Input

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

Sample Output

1
2
3
4
5
7776
0
1
0
4

Solution

既然按鈕都不同，那就可以轉換成一般的 Graph，然後轉化成 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
#include <stdio.h> 
#include <string.h>
const int mod = 10000;
struct Matrix {
	int v[100][100];
	int row, col; // row x col
	Matrix(int n, int m, int a = 0) {
		memset(v, 0, sizeof(v));
		row = n, col = m;
		for(int i = 0; i < row && i < col; i++)
			v[i][i] = a;
	}
	Matrix operator*(const Matrix& x) const {
		Matrix ret(row, x.col);
		for(int i = 0; i < row; i++) {
			for(int k = 0; k < col; k++) {
				if (v[i][k])
				for(int j = 0; j < x.col; j++) {
					ret.v[i][j] += v[i][k] * x.v[k][j],
					ret.v[i][j] %= mod;
				}
			}
		}
		return ret;
	}
	Matrix operator^(const int& n) const {
		Matrix ret(row, col, 1), x = *this;
		int y = n;
		while(y) {
			if(y&1)	ret = ret * x;
			y = y>>1, x = x * x;
		}
		return ret;
	}
};
int main() {
	int N, L, S, T;
	int x, y;
	while (scanf("%d %d", &N, &L) == 2) {
		scanf("%d %d", &S, &T);
		Matrix m(N, N);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < 4; j++) {
				scanf("%d", &x), x--;
				m.v[i][x]++;
			}
		}
		Matrix ret = m ^ L;
		S--, T--;
		printf("%d\n", ret.v[S][T]);
	}
	return 0;
}
/*
2 20
1 1
2 2 2 2
1 1 1 1
2 29
1 1
2 2 2 2
1 1 1 1
2 0
1 1
2 2 2 2
1 1 1 1
2 0
1 2
2 2 2 2
1 1 1 1
3 2
3 1
1 2 2 2
2 1 3 2
2 2 3 1
*/
Read More +
解題區►Latex

[轉] Latex ACM-ICPC template

要一下出題目規格，就有漂亮的 latex pdf！

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
\documentclass[12pt,psfig,epsf]{article}
\setlength{\topmargin}{-1in}
\setlength{\textheight}{10in}
\setlength{\textwidth}{5.5in}
\usepackage{epsfig}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{graphicx}
\begin{document}
\begin{center}
   {\Large\bfseries Problem test}\\			% Problem Number
   {\large\bf Hello World}\\			% Problem Name
   {\large Input File: {\em test.in}}\\		% Input file name
   {\large Time Limit: {\em 1 Second}}\\	% Time limit in seconds
\end{center}
% Problem description here
Output hello world !
% Technical Specification and constraints
%\vspace*{.3in} \noindent {\large \bfseries Technical Specification}
%\begin{enumerate}
%\item The . . .
%\end{enumerate}
% Input File Format
\vspace*{.3in} \noindent {\large \bfseries Input File Format}\\
Input consists of several datasets.  ...
% Output File Format
\vspace*{.3in} \noindent {\large \bfseries Output Format}\\
For each dataset, ....
% Sample Input
\vspace*{.3in} \noindent {\large \bfseries Sample Input} 
\begin{verbatim}
morris
\end{verbatim}
% Sample Output
\vspace*{.3in} \noindent {\large \bfseries Output for the Sample Input}
\begin{verbatim}
hello morris !
\end{verbatim}
\end{document}
Read More +
解題區►出題解題

[ACM 題目] 人格分裂

Problem

某 M 現在正在平面座標上的原點 (0, 0)，現在四周被擺放了很多很多鏡子，某 M 可以藉由鏡子與他的人格小夥伴對話，請問那些鏡子可以見到小夥伴。

鏡子可以當作一個線段，之間不會交任何一點，只要能見到該鏡子中一小段區域就算可見到。

備註：不考慮反射看到。

Input

輸入有多組測資。

每組測資第一行將會有一個整數 n (n < 32767)，表示總共有多少個鏡子。
接著會有 n 行，每一行上會有 4 個整數 sx, sy, ex, ey，表示鏡子所在的線段。

(-32767 < sx, sy, ex, ey < 32767)

Output

對於每組測資輸出一行，每一行將會有 n 個整數 (0/1)，分別表示輸入中第 i 個鏡子是否可見到。

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
1
5 -5 5 5
4
4 2 5 -2
2 4 6 1
5 5 8 1
3 -4 7 -1
7
-1 2 3 1
2 4 5 -1
-3 -1 1 -2
-1 -4 3 -2
-2 -4 1 -5
-4 1 -1 4
-3 4 -4 3
1
1 1 2 2
2
-1 3 -2 -2
-2 -1 -3 -1

Sample Output

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

More

sample 2

sample 3

Solution

1
Read More +