解題區/解題區 - UVa

UVa 12785 - Emacs Plugin

Problem

每個 * 位置，可以任意替換成任何字串或者是空字串，是問是否有可能匹配主字串。

Sample Input

1
2
3
4
5
6
7
8
9
4
heyhelloyou
hel*
*o*e
e*o
hello
1
hello
x

Sample Output

1
2
3
4
5
yes
no
yes
yes
no

Solution

以 * 劃分，將其切割成好幾個 token，根據貪心原則只要按照順序出現這些 token 即可，因此盡可能靠左。

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <sstream>
using namespace std;
#define MAXN 100005
char P[MAXN], T[MAXN];
int kmpTable[MAXN];
void KMPtable(const char *P, int len) {
    int i, j;
    kmpTable[0] = -1, i = 1, j = -1;
    while(i < len) {
        while(j >= 0 && P[j+1] != P[i])
            j = kmpTable[j];
        if(P[j+1] == P[i])
            j++;
        kmpTable[i++] = j;
    }
}
int KMPmatching(const char *T, int tlen, const char *P, int plen) {
    for(int i = 0, j = -1; i < tlen; i++) {
        while(j >= 0 && P[j+1] != T[i])
            j = kmpTable[j];
        if(P[j+1] == T[i])  j++;
        if(j == plen-1)
        	return i;
    }
    return -1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, plen, tlen;
    string token;
    while (scanf("%d", &n) == 1) {
        while (getchar() != '\n');
        gets(P);
        plen = strlen(P);
        for (int i = 0; i < n; i++) {
            gets(T);
            for (int j = 0; T[j]; j++) {
                if (T[j] == '*')
                    T[j] = ' ';
            }
            stringstream sin(T);
            int start = 0;
            while (sin >> token) {		
                KMPtable(token.c_str(), token.length());
                int test = KMPmatching(P + start, plen - start, token.c_str(), token.length());
//				printf("%s %d %s\n", token.c_str(), test, P + start);
                if (test == -1)	 {start = -1; break;}
                start += test + 1;
            }
            puts(start == -1 ? "no" : "yes");
        }
    }
    return 0;
}
/*
4
heyhelloyou
hel*
*o*e
e*o
hello
1
hello
x
10
rwoeyhtdvtswftfguuujqxdxdqylkyqaahianzbejckxbgeybq
oexktdvtswftf*w*n*q*rvdloll*qr
kdd*ts*ftv**ur**cdx*qi
*dtlk
**q**g****a**n
*/
Read More +
解題區/解題區 - UVa

UVa 10597 - Right Words

Problem

對一個已經是 Chomsky normal form 的 CFG，問一個 string 是否在 CFG 之中。

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
S
SABC
ab
S -> AB
S -> BC
A -> BA
A -> a
B -> CC
B -> b
C -> AB
C -> a
# -> #
baaba
ab
abaa
a
aaaaa
bbbbb
#
S
SAB
ab
S -> AB
A -> AA
A -> a
B -> b
# -> #
ab
aaab
aba
baaaaaaaa
abbbbbb
aaaaaba
baaaaaaaab
aaaa
a
ab
#

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
baaba is in L(G)
ab is in L(G)
abaa is in L(G)
a is not in L(G)
aaaaa is in L(G)
bbbbb is not in L(G)
 
ab is in L(G)
aaab is in L(G)
aba is not in L(G)
baaaaaaaa is not in L(G)
abbbbbb is not in L(G)
aaaaaba is not in L(G)
baaaaaaaab is not in L(G)
aaaa is not in L(G)
a is not in L(G)
ab is in L(G)

Solution

因為 chomsky normal form 恰好劃分成兩個，定義字串 dp[l][r] 中可以解析出那些 nonterminal，藉由矩陣鍊乘積的方式，將其組合。最後檢查整個字串是否可以推回 start symbol。

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
#include <stdio.h> 
#include <string.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    char s1[1024], s2[1024];
    while (scanf("%s", s1) == 1) {
        char start = s1[0];
        scanf("%*s %*s");
        set<char> re[128];
        set<char> rule[128][128];
        while (scanf("%s -> %s", s1, s2) == 2 && s1[0] != '#') {
            if (s2[1] == '\0')
                re[s2[0]].insert(s1[0]);
            else {
                rule[s2[0]][s2[1]].insert(s1[0]);
            }
        }
        while (scanf("%s", s1) == 1 && s1[0] != '#') {
            int n = strlen(s1);
            set<char> dp[64][64];
            for (int i = 0; i < n; i++) {
                dp[i][i].insert(re[s1[i]].begin(), re[s1[i]].end());
            }
            for (int i = 1; i < n; i++) {
                for (int j = 0; i + j < n; j++) {
                    for (int k = j; k < i+j; k++) {
                        for (set<char>::iterator a = dp[j][k].begin();
                            a != dp[j][k].end(); a++)
                        for (set<char>::iterator b = dp[k+1][i+j].begin();
                            b != dp[k+1][i+j].end(); b++)
                            dp[j][i+j].insert(rule[*a][*b].begin(), rule[*a][*b].end());
                    }
                }
            }
            printf("%s is %sin L(G)\n", s1, dp[0][n-1].find(start) == dp[0][n-1].end() 
                                        ? "not " : "");
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12747 - Back to Edit Distance

Problem

目標從起始序列經過操作變成目標序列。

  • 操作 1 : 任意替除掉一個元素。
  • 操作 2 : 將元素插入到任意位置。

請問最少次數為何

Sample Input

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

Sample Output

1
2
Case 1: 2
Case 2: 6

Solution

很明顯地看出，任意插入就可以直接無視，只要找有最長共同子序列即可，剩餘的元素一次替除一次插入即可。

但是最長子序列在這一題無法使用 O(n * n) 的算法，因此將其轉換成 LIS 做法，由於元素恰好不重複，可以在 O(n log 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
#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
// LCS to LIS
int A[262144], B[262144];
int LIS(int A[], int n) {
    vector<int> r;
    r.push_back(A[0]);
    for (int i = 1; i < n; i++) {
        int pos = (int)(upper_bound(r.begin(), r.end(), A[i]) - r.begin());
        if (pos == r.size())
            r.push_back(A[i]);
        else
            r[pos] = A[i];
    }
    return r.size();
}
int main() {
    int testcase, cases = 0;
    int n, x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            A[x] = i;
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            B[i] = A[x];
        }
        printf("Case %d: %d\n", ++cases, (n - LIS(B, n)) * 2);
    }
    return 0;
}
/*
2
5
1 3 5 4 2
1 5 4 3 2
4
1 2 4 3
3 4 2 1
*/
Read More +
解題區/解題區 - UVa

UVa 12166 - Equilibrium Mobile

Problem

給一個天平表達式，請問至少要調整幾個權重才能使之平衡。

Sample Input

1
2
3
4
3
[[3,7],6]
40
[[2,3],[4,5]]

Sample Output

1
2
3
1
0
3

Solution

恰好是一棵二元樹，那麼可以得知道假使一個權重不改，最後的天平重量為何。
假使 depth 上的權重 w 不改，則最後的天平重量就是 w * pow(2, depth)。

藉此，可以記錄所有最後的天平重量，得知最多有多少不改 = 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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
char exp[1048576];
map<long long, int> R;
void dfs(int l, int r, int dep) {
    if (exp[l] == '[') {
        int p = 0;
        for (int i = l + 1; i <= r - 1; i++) {
            if (exp[i] == '[')	p++;
            if (exp[i] == ']')	p--;
            if (p == 0 && exp[i] == ',') {
                dfs(l+1, i-1, dep+1);
                dfs(i+1, r-1, dep+1);
            }
        }
    } else {
        int w;
        exp[r+1] = '\0';
        sscanf(exp+l, "%d", &w);
        R[(long long)w<<dep]++;
    }
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", exp);
        R.clear();
        dfs(0, strlen(exp) - 1, 0);
        int sum = 0, mx = 0;
        for (map<long long, int>::iterator it = R.begin();
            it != R.end(); it++)
            sum += it->second, mx = max(mx, it->second);
        printf("%d\n", sum - mx);
    }
    return 0;
}
/*
3
[[3,7],6]
40
[[2,3],[4,5]]
*/
Read More +
解題區/解題區 - 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 +
解題區/解題區 - 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 +