解題區/解題區 - UVa

UVa 938 - Gilix

Problem

給一個環狀的蜂巢式地圖，上下沒有包裹，只有左右是相連的。現在在某一個蜂巢中放置特殊藥水，走到那個放置處喝下，之後所需要的花費都會砍半。求某點到某點的最少花費。

Sample Input

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

Sample Output

1
18

Solution

類似最短路徑，不過狀態為 dist[N][2] 是否已經經過放置藥水的地點，隨著 spfa 更新即可。關於蜂巢地圖，直接根據奇偶數 row 分開討論即可。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int g[512][512];
int dist[512][512][2], inq[512][512][2];
const int dx1[] = {-1, -1, 0, 1, 1, 0};
const int dy1[] = {0, 1, 1, 1, 0, -1};
const int dx2[] = {-1, -1, 0, 1, 1, 0};
const int dy2[] = {-1, 0, 1, 0, -1, -1};
void spfa(int L, int C, int sx, int sy, int ex, int ey, int px, int py) {
    memset(dist, 63, sizeof(dist));
    queue<int> X, Y, S;
    int tx, ty, ts, ss;
    dist[sx][sy][0] = 0;
    X.push(sx), Y.push(sy), S.push(0);
    while (!X.empty()) {
        sx = X.front(), X.pop();
        sy = Y.front(), Y.pop();
        ss = S.front(), S.pop();
        inq[sx][sy][ss] = 0;
        for (int i = 0; i < 6; i++) {
            if (sx&1)
                tx = sx + dx1[i], ty = sy + dy1[i];
            else
                tx = sx + dx2[i], ty = sy + dy2[i];
            if (tx < 0 || tx >= L)	continue;
            ty = (ty + C)%C;
            ts = ss;
            int cost = ts ? g[tx][ty]/2 : g[tx][ty];
            if (tx == px && ty == py)
                ts = ss | 1;
            if (dist[tx][ty][ts] > dist[sx][sy][ss] + cost) {
                dist[tx][ty][ts] = dist[sx][sy][ss] + cost;
                if (!inq[tx][ty][ts]) {
                    inq[tx][ty][ts] = 1;
                    X.push(tx), Y.push(ty), S.push(ts);
                }
            }
        }
    }
    printf("%d\n", min(dist[ex][ey][0], dist[ex][ey][1]));
}
int main() {
    int L, C;
    int sx, sy, ex, ey, px, py;
    while (scanf("%d %d", &L, &C) == 2) {
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < C; j++)
                scanf("%d", &g[i][j]);
        }
        scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
        scanf("%d %d", &px, &py);
        spfa(L, C, sx, sy, ex, ey, px, py);
    }
    return 0;
}
/*
4 8
4 2 2 2 4 4 6 10
2 6 8 4 4 4 4 2
8 2 6 8 4 4 4 6
6 4 4 6 8 4 4 4
0 0
3 4
1 1
*/
Read More +
解題區/解題區 - UVa

UVa 233 - Package Pricing

Problem

總共有 a, b, c, d 四種類型的燈泡，現在給予一些組合包的價格和各自內有四種類型的燈泡數量，現在要求購買指定個數以上的方案，求最少花費。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
5
10 25.00 b 2
502 17.95 a 1
3 13.00 c 1
55 27.50 b 1 d 2 c 1
6 52.87 a 2 b 1 d 1 c 3
6
d 1
b 3
b 3 c 2
b 1 a 1 c 1 d 1 a 1
b 1 b 2 c 3 c 1 a 1 d 1
b 3 c 2 d 1 c 1 d 2 a 1

Sample Output

1
2
3
4
5
6
1:   27.50 55
2:   50.00 10(2)
3:   65.50 3 10 55
4:   52.87 6
5:   90.87 3 6 10
6:  100.45 55(3) 502

Solution

這一題不外乎就是整數線性規劃，很明顯地是一個 NPC 問題，所以就兩種策略強力剪枝、背包問題。

關於強力剪枝，大概是當年解決問題的方法，因為題目沒有特別說明數據範圍，用背包問題是相當不方便的，我也搜索不到當年 WF 的 code，所以測試一下數據範圍，發現將四種類型燈泡需求相乘結果不大於 100 萬。

藉由這個條件，將狀態訂為 dp[a_size][b_size][c_size][d_size] 的最小花費為何，但是可能忽大忽小，所以自己定義 row major 來完成。嘗試將每一種組合去迭代找最小值，中間過程要記得取 min bound，以免越界。

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 <iostream>
#include <sstream>
#include <algorithm>
#include <assert.h>
#include <map>
#include <queue>
using namespace std;
struct COMB {
    int label, supply[4];
    double price;
    void init() {
        memset(supply, 0, sizeof(supply));
    }
    void print() {
        printf("%d %lf %d %d %d %d\n", label, price, supply[0], supply[1], supply[2], supply[3]);
    }
    bool operator<(const COMB &p) const {
        return label < p.label;
    }
} products[64];
int n, q, need[16];
int mnCnt[64], path[64];
double mnCost;
double dp[1048576];
int dpChoose[1048576][2];
int row[4];
int getIndex(int A[]) {
    int v = 0;
    for (int j = 0; j < 4; j++)
        v += A[j] * row[j];
    return v;
}
void bfs() {
    row[0] = (need[3]+1)*(need[2]+1)*(need[1]+1);
    row[1] = (need[3]+1)*(need[2]+1);
    row[2] = need[3]+1;
    row[3] = 1;
    int A[4], B[4], u, v, mxState = getIndex(need);
    for (int i = 0; i <= mxState; i++)
        dp[i] = 1e+50, dpChoose[i][0] = dpChoose[i][1] = -1;
    dpChoose[0][1] = -1, dp[0] = 0;
    for (int p = 0; p <= mxState; p++) {
        u = p;
        for (int i = 0; i < 4; i++)
            A[i] = u / row[i], u %= row[i];
        u = p;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 4; j++)
                B[j] = min(A[j] + products[i].supply[j], need[j]);
            v = getIndex(B);
            if (dp[v] > dp[u] + products[i].price)
                dp[v] = dp[u] + products[i].price, dpChoose[v][0] = i, dpChoose[v][1] = u;
        }
    }
    memset(mnCnt, 0, sizeof(mnCnt));
    for (int p = mxState; p != -1; p = dpChoose[p][1])
        mnCnt[dpChoose[p][0]]++;		
    mnCost = dp[mxState];
}
int main() {
    char line[1024];
    string token;
    int cnt = 0;
    while (scanf("%d", &n) == 1) {
        while (getchar() != '\n');
        
        for (int i = 0; i < n; i++) {
            products[i].init();
            gets(line);
            stringstream sin(line);
            sin >> products[i].label >> products[i].price;
            while (sin >> token >> cnt)
                products[i].supply[token[0] - 'a'] += cnt;
        }
        sort(products, products + n);
        gets(line);
        sscanf(line, "%d", &q);
        for (int i = 0; i < q; i++) {
            memset(need, 0, sizeof(need));
            gets(line);
            stringstream sin(line);
            while (sin >> token >> cnt)
                need[token[0] - 'a'] += cnt;
            bfs();
            printf("%d:%8.2lf", i + 1, mnCost);
            for (int j = 0; j < n; j++) {
                if (mnCnt[j]) {
                    printf(" %d", products[j].label);
                    if (mnCnt[j] > 1)
                        printf("(%d)", mnCnt[j]);
                }
            }
            puts("");
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12806 - Grand Tichu

Problem

增加 4 張牌到撲克牌中，每名玩家將會獲得 14 張牌，而在有 8 張的時候，可以預估是否會湊到 4 種類型的手牌，如果可以組合出其中一種的機率大於 0.25，則喊出 Grand Tichu!。

Sample Input

1
2
3
4
5
6
7
D23468AA
D2P4688K
D23468KA
D2233889
PdM2345T
PdM234AA
0

Sample Output

1
2
3
4
5
6
Grand Tichu!
Grand Tichu!
Grand Tichu!
...
...
...

Solution

搜索順序的重要性，由於 4 種組合牌中，只與 ADPMd 有關，剩下的類型可以直接利用組合去計算，只要窮舉 ADPMd 出現在手牌的組合情況即可。

如果按照一般的 23456789TJQKADPMd 效率不彰，耗費時間太久，再多剪枝都不夠。

一開始誤以為是 4 種機率加總大於 0.25 就輸出，不管怎麼樣連範測都會錯，後來發現是湊出其中一種的機率必須大於 0.25。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long C[50][50];
const char kind[20] = "ADPMd23456789TJQK";
int ihand[20], ohand[20], mhand[20];
int suffix[20];
long long va[10], vb;
void dfs(int idx, int card, long long ways) {
    if (idx > 4) {
        ways = ways * C[suffix[idx]][14 - card];
        int hh = 0;
        if (ohand[1] > 0 && ohand[2] > 0 && ohand[0] > 0)
            hh = 1, va[hh] += ways;// D P A
        if (ohand[1] > 0 && ohand[0] >= 2)
            hh = 2, va[hh] += ways;// D A A
        if (ohand[2] > 0 && ohand[0] >= 3)
            hh = 3, va[hh] += ways; // P A A A
        if (ohand[1] > 0 && ohand[2] > 0 && ohand[3] > 0 && ohand[4] > 0)
            hh = 4, va[hh] += ways; // D P M d
        vb += ways;
        return ;
    }
    if (card == 14) {
        int hh = 0;
        if (ohand[1] > 0 && ohand[2] > 0 && ohand[0] > 0)
            hh = 1, va[hh] += ways;// D P A
        if (ohand[1] > 0 && ohand[0] >= 2)
            hh = 2, va[hh] += ways;// D A A
        if (ohand[2] > 0 && ohand[0] >= 3)
            hh = 3, va[hh] += ways; // P A A A
        if (ohand[1] > 0 && ohand[2] > 0 && ohand[3] > 0 && ohand[4] > 0)
            hh = 4, va[hh] += ways; // D P M d
        vb += ways;
        return ;
    }
    if (idx == 17 || card + suffix[idx] < 14)	return ;
    for (int i = 0; i <= ihand[idx] && card + i <= 14; i++) {
        ohand[idx] += i;
        dfs(idx+1, card + i, ways * C[ihand[idx]][i]);
        ohand[idx] -= i;
    }
}
int main() {
    for (int i = 0; i < 50; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
    char hand[64];
    while (scanf("%s", &hand) == 1 && hand[0] != '0') {
        memset(ihand, 0, sizeof(ihand));
        memset(ohand, 0, sizeof(ohand));
        for (int i = 4; i < 17; i++)
            ihand[i] = 4, mhand[i] = 4;
        ihand[0] = 4, mhand[0] = 4;
        for (int i = 1; i <= 4; i++)
            ihand[i] = 1, mhand[i] = 1;
        for (int i = 0; i < 8; i++) {
            int p = find(kind, kind + 17, hand[i]) - kind;
            ihand[p]--, ohand[p]++;
        }
        memset(suffix, 0, sizeof(suffix));
        for (int i = 17; i >= 0; i--)
            suffix[i] = suffix[i+1] + ihand[i];
        memset(va, 0, sizeof(va));
        vb = 0;
        dfs(0, 8, 1);
        int ok = 0;
        for (int i = 0; i < 4; i++) {
            double p = (double)va[i] / vb;
            if (p > 0.25)	ok = 1;
        }
        if (ok)
            puts("Grand Tichu!");
        else
            puts("...");
    }
    return 0;
}
/*
D23468AA
D2P4688K
D23468KA
D2233889
PdM2345T
PdM234AA
0
D23468AA
0.000000
0.125000
1.000000
0.025439
Grand Tichu
D2P4688K
0.000000
0.424761
0.070768
0.004394
Grand Tichu
D23468KA
0.000000
0.125000
0.336263
0.003315
Grand Tichu
D2233889
0.000000
0.046558
0.070768
0.000298
...
PdM2345T
0.000000
0.046558
0.006332
0.004394
...
PdM234AA
0.000000
0.125000
0.125000
0.236702
...
*/
Read More +
解題區/解題區 - UVa

UVa 12804 - The Necronomicon of Computing

Problem

給一段簡單的組合語言，有三種指令。

  1. 判斷指令：有可能跳到第 x 個指令，不然就會執行下一行指令。
  2. 計算指令：計算完，執行下一行指令。
  3. 跳躍指令：直接跳躍到第 x 個指令。

判斷這支程式是否有機會停止、或者是進入無限迴圈、還是一直都會結束。

Sample Input

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

Sample Output

1
2
3
NEVER
ALWAYS
SOMETIMES

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
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MAXN 1024
vector<int> g[MAXN];
char cmd[MAXN][16];
int N[MAXN], used[MAXN], instk[MAXN];
int loopflag, endflag;
void dfs(int u) {
    instk[u] = 1, used[u] = 1;
    for (int i = 0; i < g[u].size(); i++) {
        if (used[g[u][i]] == 0)
            dfs(g[u][i]);
        if (instk[g[u][i]] == 1)
            loopflag = 1;
    }
    instk[u] = 0;
}
int main() {
    int testcase, L;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &L);
        for (int i = 0; i <= L + 1; i++)
            g[i].clear();
        for (int i = 1; i <= L; i++) {
            scanf("%s", cmd[i]);
            if (cmd[i][0] == 'A') {
                g[i].push_back(i+1);
            } else if (cmd[i][0] == 'J') {
                scanf("%d", &N[i]);
                g[i].push_back(N[i]);
            } else if (cmd[i][0] == 'C') {
                scanf("%d", &N[i]);
                g[i].push_back(N[i]);
                g[i].push_back(i+1);
            }
        }
        memset(used, 0, sizeof(used));
        memset(instk, 0, sizeof(instk));
        loopflag = 0, endflag = 0;
        dfs(1);
        endflag = used[L + 1];
        if (loopflag == 0 && endflag == 1)
            puts("ALWAYS");
        else if (loopflag == 1 && endflag == 0)
            puts("NEVER");
        else
            puts("SOMETIMES");
    }
    return 0;
}
/*
3
3
A
A
J 1
5
A
J 4
J 5
C 3
A
4
A
A
C 2
A
*/
Read More +
解題區/解題區 - UVa

UVa 12803 - Arithmetic Expressions

Problem

給一個浮點數的五則運算表達式，計算其值。

Sample Input

1
2
3
4
3
( 3.00 + 4.50 )
( 5.00 - ( 2.50 * 3.00 ) )
( ( 7.00 / 3.00 ) + ( 4.00 - ( 3.00 * 7.00 ) ) )

Sample Output

1
2
3
7.50
-2.50
-14.67

Solution

中序表達轉換成後序表達，隨後再使用 stack 完成計算。

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
#include <stdio.h>
#include <stack>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
int priority_op(char c) {
    switch(c) {
        case '(':return 0;
        case '+': case '-':return 1;
        case '*': case '/':return 2;
    }
    return -1;
}
void trans(char infix[], char buffer[]) {
    int len = strlen(infix);
    char *ptr = buffer;
    stack<char> op;
    *ptr = '\0';
    for(int i = 0; i < len; i++) {
    	if (infix[i] == ' ')	continue;
        if(infix[i] >= '0' && infix[i] <= '9' || 
            (infix[i] == '-' && infix[i+1] >= '0' && infix[i+1] <= '9')) {
            while (infix[i] >= '0' && infix[i] <= '9' || 
                (infix[i] == '-' && infix[i+1] >= '0' && infix[i+1] <= '9') || infix[i] == '.') {
            	sprintf(ptr, "%c", infix[i]), i++;
            	while(*ptr)    ptr++;
        	}
        	sprintf(ptr, " ");
            while(*ptr)    ptr++;
        	i--;
        }else {
            if(infix[i] == ')') {
                while(!op.empty() && op.top() != '(') {
                    sprintf(ptr, "%c ", op.top()), op.pop();
                    while(*ptr) ptr++;
                }
                op.pop();
            } else {
                if(infix[i] != '(')
                while(!op.empty() && priority_op(op.top()) >= priority_op(infix[i])) {
                    sprintf(ptr, "%c ", op.top()), op.pop();
                    while(*ptr) ptr++;
                }
                op.push(infix[i]);
            }
        }
    }
    while(!op.empty()) {
        sprintf(ptr, "%c ", op.top()), op.pop();
        while(*ptr) ptr++;
    }
}
int isOper(char c) {
    switch(c) {
        case '(':return 1;
        case '+': case '-':return 1;
        case '*': case '/':return 1;
    }
    return 0;
}
double calcPostfix(char postfix[]) {
    stringstream sin(postfix);
    string token;
    stack<double> stk;
    double a, b, c;
    while (sin >> token) {
    	if (token.length() == 1 && isOper(token[0])) {
            b = stk.top(), stk.pop();
            a = stk.top(), stk.pop();
            switch(token[0]) {
                case '+': a = a+b;break;
                case '-': a = a-b;break;
                case '*': a = a*b;break;
                case '/': a = a/b;break;
            }
            stk.push(a);
    	} else {
    		stringstream cc(token);
    		cc >> c;
    		stk.push(c);
    	}
    }
    return stk.top();
}
char infix[262144], postfix[262144];
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (getchar() != '\n');
    while (testcase--) {
        gets(infix);
        trans(infix, postfix);
        printf("%.2lf\n", calcPostfix(postfix));
    }
    return 0;
}
/*
3
( 3.00 + 4.50 )
( 5.00 - ( 2.50 * 3.00 ) )
( ( 7.00 / 3.00 ) + ( 4.00 - ( 3.00 * 7.00 ) ) )
*/
Read More +
解題區/解題區 - UVa

UVa 1629 - Cake slicing

Problem

切割長方形蛋糕，使得每一塊上恰好有一個莓果，每一次切割的花費即線長，求最小花費。

Sample Input

1
2
3
4
3 4 3 
1 2 
2 3 
3 2

Sample Output

1
Case 1: 5

Solution

利用 DP 精神，考慮每一個地方都去切割，定義 dp[x][y][w][h] 為左上角座標 (x, y)，其長寬 (w, h) 的長方形蛋糕的最小花費。

沒有辦法對於連續空白之間只取一次切割，如果只切一次縱切的，切著左右兩側的橫切個數將會影響很大，所以每個位置都要嘗試。

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
#include <stdio.h> 
#include <algorithm>
#include <string.h>
using namespace std;
int N, M, K;
int g[32][32], sum[32][32];
int dp[32][32][32][32], used[32][32][32][32], testcase = 0;
int getArea(int x, int y, int w, int h) {
    return sum[x + w-1][y + h-1] - sum[x-1][y + h-1] - sum[x + w-1][y-1] + sum[x-1][y-1];
}
int dfs(int x, int y, int w, int h) {
    if (used[x][y][w][h] == testcase)
        return dp[x][y][w][h];
    if (getArea(x, y, w, h) < 2)
        return 0;
    used[x][y][w][h] = testcase;
    int &ret = dp[x][y][w][h];
    ret = 0x3f3f3f3f;
    for (int i = 1; i < w; i++) {
        if (getArea(x, y, i, h) > 0 && getArea(x+i, y, w-i, h) > 0)
            ret = min(ret, dfs(x, y, i, h) + dfs(x+i, y, w-i, h) + h);
    }
    for (int i = 1; i < h; i++) {
        if (getArea(x, y, w, i) > 0 && getArea(x, y+i, w, h-i) > 0)
            ret = min(ret, dfs(x, y, w, i) + dfs(x, y+i, w, h-i) + w);
    }
    return ret;
}
int main() {
    while (scanf("%d %d %d", &N, &M, &K) == 3) {
        memset(g, 0, sizeof(g));
        memset(sum, 0, sizeof(sum));
        int x, y;
        for (int i = 0; i < K; i++) {
            scanf("%d %d", &x, &y);
            g[x][y]++;
        }
        for (int i = 1; i <= N; i++) {
            int x = 0;
            for (int j = 1; j <= M; j++) {
                x += g[i][j];
                sum[i][j] = sum[i-1][j] + x;
            }
        }
        testcase++;
        printf("Case %d: %d\n", testcase, dfs(1, 1, N, M));
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12424 - Answering Queries on a Tree

Problem

給一棵樹

  1. 調整某一個節點上的顏色
  2. 詢問兩個點路徑上，哪一個顏色數量最多，輸出數量即可。

Sample Input

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

Sample Output

1
2
3
4
2
3
1
1

Solution

由於顏色不大於 10，可以安妥建造 10 棵線段樹，利用樹鏈剖分的概念，重邊將會取子樹最大的那一邊，其他都是輕邊，隨後保證每一個點往上爬升，最多經過 log n 個輕邊。

因此時間複雜度調整 O(log n) 詢問 O(log^2 n)。

對於樹鏈剖分找 LCA 操作，針對兩個 (x, y) 所在的 node 而言，查看哪個 node 位置高低，調整到同高進行操作，保證爬的次數最多 log n，對於每一個 node 中建造一個線段樹，因此各自 query 也要 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
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
#include <stdio.h> 
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXN 131072
int color[MAXN];
int hNext[MAXN], iNode[MAXN], aPos[MAXN];
int used[MAXN], nodesize = 0;
struct Node {
    int p, pPos, dep;
    vector<int> A;
    vector<int> seg[10];
    void init() {
        A.clear();
        p = -1, dep = 0;
    }
} nodes[262144];
struct Tree {
    vector<int> g[MAXN];
    int root;	
    void init(int n) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        root = 0;
    }
    void addEdge(int x, int y) {
        g[x].push_back(y);
        g[y].push_back(x);
    }
} tree;
int getSTsize(int n) {
    int ret = 1;
    for (ret = 1; ret < n; ret <<= 1);
    return ret<<1;
}
int prepare(int u, int p) {
    int sz = 1, mx = -1, hedge = -1;
    int v, t;
    for (int i = 0; i < tree.g[u].size(); i++) {
        v = tree.g[u][i], t;
        if (v == p)	continue;
        sz += (t = prepare(v, u));
        if (mx < t)
            mx = t, hedge = v;
    }
    hNext[u] = hedge;
    return sz;
}
void buildST(Node &nd, int k, int l, int r) {
    if (l > r)	return ;
    if (l == r) {
        nd.seg[color[nd.A[l]]][k] = 1;
        return;
    }
    int mid = (l + r)/2;
    buildST(nd, k<<1, l, mid);
    buildST(nd, k<<1|1, mid+1, r);
    for (int i = 0; i < 10; i++)
        nd.seg[i][k] = nd.seg[i][k<<1] + nd.seg[i][k<<1|1];
}
void build(int u, int p) {	
    if (used[u] == 0) {
        Node &nd = nodes[++nodesize];
        nd.init();
        for (int i = u; i != -1; i = hNext[i]) {
            used[i] = 1;
            iNode[i] = nodesize, aPos[i] = nd.A.size();
            nd.A.push_back(i);
        }
        for (int i = 0; i < 10; i++)
            nd.seg[i].clear(), nd.seg[i].resize(getSTsize(nd.A.size()), 0);
        buildST(nd, 1, 0, nd.A.size() - 1);
        if (p != -1) {
            nd.p = iNode[p], nd.pPos = aPos[p];
            nd.dep = nodes[nd.p].dep + 1;
        }
    }
    int v;
    for (int i = 0; i < tree.g[u].size(); i++) {
        v = tree.g[u][i];
        if (v == p)	continue;
        build(v, u);
    }
}
int colorsum[10];
void queryST(Node &nd, int k, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        for (int i = 0; i < 10; i++)
            colorsum[i] += nd.seg[i][k];
        return ;
    }
    int mid = (l + r)/2;
    if (x <= mid)
        queryST(nd, k<<1, l, mid, x, y);
    if (mid < y)
        queryST(nd, k<<1|1, mid+1, r, x, y);
    
}
void search(int u, int v) {
    memset(colorsum, 0, sizeof(colorsum));
    int x = iNode[u], y = iNode[v];
    u = aPos[u], v = aPos[v];
    while (x != y) {
        if (nodes[x].dep < nodes[y].dep)
            swap(x, y), swap(u, v);
        assert(u <= nodes[x].A.size());
        queryST(nodes[x], 1, 0, nodes[x].A.size() - 1, 0, u);
        u = nodes[x].pPos, x = nodes[x].p;
    }
    if (u > v)	swap(u, v);
    queryST(nodes[x], 1, 0, nodes[x].A.size() - 1, u, v);
    int ret = 0;
//	for (int i = 0; i < 10; i++)
//		printf("%d ", colorsum[i]);
//	puts("");
    for (int i = 0; i < 10; i++)
        ret = max(ret, colorsum[i]);
    printf("%d\n", ret);
}
void modifyST(Node &nd, int k, int l, int r, int x, int v) {
    if (l == r) {
        for (int i = 0; i < 10; i++)
            nd.seg[i][k] = 0;
        nd.seg[v][k]++;
        return ;
    }
    int mid = (l + r)/2;
    if (x <= mid)
        modifyST(nd, k<<1, l, mid, x, v);
    else
        modifyST(nd, k<<1|1, mid+1, r, x, v);
    for (int i = 0; i < 10; i++)
        nd.seg[i][k] = nd.seg[i][k<<1] + nd.seg[i][k<<1|1];
}
void modify(int u, int color) {
    int x = iNode[u];
    modifyST(nodes[x], 1, 0, nodes[x].A.size() - 1, aPos[u], color);
}
int main() {
//	freopen("in.txt","r+t",stdin);
//    freopen("out2.txt","w+t",stdout);
    int testcase;
    int n, q, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &q);
        for (int i = 0; i < n; i++)
            scanf("%d", &color[i]), color[i]--;
        tree.init(n);
        
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            tree.addEdge(x, y);
        }
        
        prepare(tree.root = 0, -1);
        memset(used, 0, sizeof(used));
        nodesize = 0;
        build(tree.root = 0, -1);
        
//		for (int i = 0; i < n; i++)
//			printf("[%d] %d\n", i, hNext[i]);
        int cmd, u, v;
        for (int i = 0; i < q; i++) {
            scanf("%d %d %d", &cmd, &u, &v);
            if (cmd == 0) {
                u--, v--;
                modify(u, v);
            } else {
                u--, v--;
                search(u, v);
            }
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12783 - Weak Links

Problem

是否存在 weak link，使得兩個 component 會因為 weak link 斷掉而無法連通。

Sample Input

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

Sample Output

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

Solution

找橋 bridge！利用 back edge 的深度進行判斷。

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 <string.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int visited[1024], depth[1024];
vector< pair<int, int> > bridge;
int findBridge(int u, int p, int dep) {
    visited[u] = 1, depth[u] = dep;
    int back = 0x3f3f3f3f;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(v == p)	continue;
        if(!visited[v]) {
            int b = findBridge(v, u, dep+1);
            if(b > dep)
                bridge.push_back(make_pair(u, v));
            back = min(back, b);
        } else {
            back = min(back, depth[v]);
        }
    }
    return back;
}
int main() {
    int n, m, q, x, y;
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        for(int i = 0; i < n; i++)
            g[i].clear();
        for(int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        
        bridge.clear();
        memset(visited, 0, sizeof(visited));
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                findBridge(i, -1, 0);
            }
        }
        for (int i = 0; i < bridge.size(); i++)
            if (bridge[i].first > bridge[i].second)
                swap(bridge[i].first, bridge[i].second);
        sort(bridge.begin(), bridge.end());
        printf("%d", bridge.size());
        for (int i = 0; i < bridge.size(); i++)
            printf(" %d %d", bridge[i].first, bridge[i].second);
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12784 - Don't Care

Problem

問是否計算順序會影響結果，給一個有向圖，請問是否每一個操作都會 reduce 到同一個項目。

Sample Input

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

Sample Output

1
2
3
4
1
1
0
0

Solution

如果裡面有環肯定是不行的，因此需要偵測環是否存在。

在這之後，必須檢查是否會 reduce 到同一個項目，因此我們將每個 node reduce 的結果保存，之後取聯集，如果發現 reduce 項目超過一個則直接回傳失敗。

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
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
vector<int> g[1024];
set<int> A[1024];
int used[1024];
int instk[1024];
int dfs(int u) {
    used[u] = 1, instk[u] = 1;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (instk[v])
            return 1;
        if (!used[v]) {
            if(dfs(v))
                return 1;
            A[u].insert(A[v].begin(), A[v].end());
            if (A[u].size() > 1)
                return 1;
        }
    }
    if (g[u].size() == 0)
        A[u].insert(u);
    instk[u] = 0;
    return A[u].size() > 1;
}
int main() {
    int n, m, x, y;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        for (int i = 0; i < n; i++)
            g[i].clear(), used[i] = 0, A[i].clear(), instk[i] = 0;
        int indeg[1024] = {};
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            indeg[y]++;
        }
        
        int err = 0;
        for (int i = 0; i < n && !err; i++) {
            if (used[i] == 0 && indeg[i] == 0)
                err |= dfs(i);
        }
        for (int i = 0; i < n; i++) // cycle
            if (used[i] == 0)
                err = 1;
        printf("%d\n", !err);
    }
    return 0;
}
/*
3 2
0 1
1 2
2 2
0 1
0 1
2 2
0 1
1 0
3 2
0 1
0 2
0 0
*/
Read More +
解題區/解題區 - UVa

UVa 225 - Golygons

Problem

每一步轉角九十度，並且第 i 次要走 i 長單位，回到原點且沿途不經過障礙物，同時轉角不可重複。

Sample Input

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

Sample Output

1
2
3
4
wsenenws
Found 1 golygon(s).
Found 0 golygon(s).

Solution

沿途經過障礙物，同時轉角不重複。一開始曲解了經過的轉角點，以為他也不能在隨後中經過，但實際上是可以的，因此拿了不少 WA。

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
#include <stdio.h> 
#include <stdlib.h>
#include <algorithm>
#include <set>
#include <vector>
#include <iostream>
#include <assert.h>
using namespace std;
int n, m, golygons;
set< pair<int, int> > ban;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const char sdir[] = "nsew";
char path[1024];
char g[2048][2048] = {}, g2[2048][2048];
vector<string> ways;
#define BASE 1024
void dfs(int x, int y, int dir, int step) {
    if (abs(x - 0) + abs(y - 0) > (step + n) * (n - step + 1)/2) {
        return;
    }
    if (step == n + 1) {
        if (x == 0 && y == 0) {
            path[step - 1] = '\0';
//			puts(path);
            ways.push_back(path);
            golygons++;
        }
        return ;
    }
    if (dir != 0) {
        for (int i = 0; i < 2; i++) {
            int tx = x, ty = y, ok = 1;
            for (int j = 0; j < step; j++) {
                tx = tx + dx[i], ty = ty + dy[i];
                assert(BASE + tx >= 0 && BASE + ty >= 0);
                assert(BASE + tx < 2048 && BASE + ty < 2048);
                if (g[BASE + tx][BASE + ty]) {
                    ok = 0;
                    break;
                }
            }
            if (ok && g2[BASE + tx][BASE + ty] == 0) {
                g2[BASE + tx][BASE + ty] = 1;
                path[step - 1] = sdir[i];
                dfs(tx, ty, 0, step + 1);
                g2[BASE + tx][BASE + ty] = 0;
            }
        }
    }
    if (dir != 1) {
        for (int i = 2; i < 4; i++) {
            int tx = x, ty = y, ok = 1;
            for (int j = 0; j < step; j++) {
                tx = tx + dx[i], ty = ty + dy[i];
                assert(BASE + tx >= 0 && BASE + ty >= 0);
                assert(BASE + tx < 2048 && BASE + ty < 2048);
                if (g[BASE + tx][BASE + ty]) {
                    ok = 0;
                    break;
                }
            }
            if (ok && g2[BASE + tx][BASE + ty] == 0) {
                g2[BASE + tx][BASE + ty] = 1;
                path[step - 1] = sdir[i];
                dfs(tx, ty, 1, step + 1);
                g2[BASE + tx][BASE + ty] = 0;
            }
        }
    }
}
int main() {
    int testcase, x[64], y[64];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        ban.clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x[i], &y[i]);
            ban.insert(make_pair(x[i], y[i]));
            g[BASE + x[i]][BASE + y[i]] = 1;
        }
        ways.clear();
        dfs(0, 0, -1, 1);
        sort(ways.begin(), ways.end());
        for (int i = 0; i < ways.size(); i++)
            puts(ways[i].c_str());
        printf("Found %d golygon(s).\n\n", ways.size());
        for (int i = 0; i < m; i++)
            g[BASE + x[i]][BASE + y[i]] = 0;
    }
    return 0;
}
/*
2
8
2
-2 0
6 -2
8
2
2 1
-2 0
1000
16
0
*/
Read More +