學校課程/通識課程

[通識] 文明的進程 Week 4

每次小考禮貌與羞恥相關的考題，看來這門通識相當難過呢。

文明相對性

文明化是具有相對性的，根據不同時間，原本認為好的文明舉止也有可能被汰換掉，而不好的舉止也有可能再下一個世代中被重用。

舉一個最簡單的例子，以我們亞洲社會來講，一個溫文儒雅、拘謹的人才算文明，而在過去可能認為瀟灑自在、豪放不羈才算是一個文明俠士。在這一個過程中，文明舉止居然變得不文明，是個相當有趣的現象。

看看那電影中的英雄，有多少文明人呢？個個不守規矩，個個都有反抗意識。還做英雄？還是做文明人？

文明阻隔

文明舉止阻隔了什麼？身為一個生物的 自然功能 (Elias 書中特地不寫 屎尿屁 )，現代人眼中講出 屎尿屁 三字的羞恥程度居然沒有比過去還要高，Elias 的年代講出這幾個字想必都羞愧不如。

進食 可以忍耐、延後，但是屎尿屁三者卻是相當難抑制。人都不人，這正常功能卻要被約束，抑制反而會傷了身體，為了禮儀而傷了自己，在現代則盡可能以 健康為由 ，走向與禮儀相反的舉止，盡可能轉換這一過程。

論廁所

廁所越來越不像廁所，越來越隱密，越隱密就越受歡迎，相反的卻也越來越不環保，為了在空氣流通不好的地方保持流通，消耗更多電力來維護。

當人們越常在外活動，公廁的存在就很重要，因此用公廁的普遍性呈現一個國家的文明程度，

在鄉下的農業社會中，鄉民們還會替你準備公廁呢，「 你的屎尿就是黃金肥料 」 化學肥料沒有普及到那邊時，屎尿可能比黃金更珍貴，因此處處可見這種由農民建起的公廁，而有誤解成中國為 “禮儀之邦”，人的屎尿不會隨處可見，反觀歐洲在下水道還沒有技術支持前，人的屎尿在街道上到處都是，相較中國反而文明了！

規範手法

  • 外顯禮貌
  • 內在羞恥

其中羞恥心為最重要的手法，尤其是當沒有別人眼光時，仍然要遵守禮儀就是相當需要羞恥心的。

「小天使會在一旁看著，如果不想讓天使討厭你，請隨時注意禮節。」而在現在監視器取代了小天使，想要在沒人的地方裸體，看來還是得注意點呢！

已經從顧及他人觀感到愛護自己健康，愛護自己更具有說服力，潔身自愛成為新的主流，人際之間的階層關係沒有說服力，誰能抵擋健康這一個理由呢！

什麼時候會拋棄自己的文化舉動呢？向低等人示友好厚愛時，做出一樣羞恥的事情，反而會更加地容易親近，但是相反地會更鞏固之間的階層關係 (因為認同彼此階級的差別)。

論餐桌夾菜

  • 階層社會：以示照顧、關愛
  • 平等社會：侵犯主權

被傷害的孩子

禮儀演進消耗百年，而孩子卻要在數年之內完成禮儀和羞恥的學習，這麼巨量的訊息藉由不同管道了解，每當我們認為小孩相當不禮貌時，同時也表示我們對於禮儀的要求又更高。

結語

如果在沒人的地方，做出平常人不會做的事情，就真的羞恥了嗎？為什麼沒有傷害別人，卻也必須冠上妨害風化、風俗的罪名。為了防止無知的效仿效應，難道這一點趣味都要遏止？

禮儀教給我們到底是什麼？更加鞏固自己的地位嗎？區分彼此身分的第一印象嗎？我們遵守禮儀失去了真正生物的本能，就如捷運殺人案，反抗本能消散，我們是怎麼失去暴力的。

作業

請觀看影片 2 cellos “Thunderstruck”，並從文明化的觀點分析（100字）

大人們固定成形的價值觀，相較於小孩更難以改變，只要一更動部分可能就會替換掉一大部分觀念，年輕人講出來的點子的基準不同，彼此之間的溝通性好、衝突少。才會造就影片中受到小孩喜歡、大人們卻難以接受的情況。

Read More +
解題區/出題解題

[ACM 題目] 少女與戰車

Problem

蘋果樹和梨樹花朵綻放，茫茫霧靄在河面飄揚。出門走到河岸邊，喀秋莎，到那又高又陡的河岸。

一面走著，一面唱著歌兒。唱道草原上空的蒼鷹，唱道她衷心喜愛的男孩。他的來信封封都珍藏。

啊！歌兒，女孩悠揚的歌聲，請跟隨著光明的太陽，飛翔到遙遠前方的戰士，為喀秋莎來向他致意。

願他還記得純情的女孩，願她的歌聲能被聽聞。願他保衛著祖國的大地，而喀秋莎守護著愛情。

蘋果樹和梨樹花朵綻放，茫茫霧靄在河面飄揚。出門走到河岸邊，喀秋莎，到那又高又陡的河岸。

正當梨花開遍了天涯，河上飄著柔曼的輕紗，喀秋莎站在峻峭的岸上，歌聲好像明媚的春光。

姑娘唱著美妙的歌曲，她在歌唱草原的雄鷹，她在歌唱心愛的人兒，她還藏著愛人的書信。

啊，這歌聲姑娘的歌聲，跟著光明的太陽去飛吧，去向遠方邊疆的戰士，把喀秋莎的問候傳達。

駐守邊疆年輕的戰士，心中懷念遙遠的姑娘，勇敢戰鬥保衛祖國，喀秋莎愛情永遠屬於他。

正當梨花開遍了天涯，河上飄著柔曼的輕紗，喀秋莎站在峻峭的岸上，歌聲好像明媚的春光。

現在有 N 台戰車平行奔馳在雪地上，在時間$t = 0$ 時，分別位於$x_{i}$，並且每戰車都維持等速度$v_{i}$，請問有哪幾台曾經在奔馳的過程中當過領先者。

Input

輸入有多組測資，每組第一行會有一個整數 N (N < 32767)。

接著會有 N 行戰車資訊，每一行上會有兩個實數$(x_{i}, v_{i})$，其中$-100,000\le x_{i} \le 100,000$$-100\le v_{i} \le 100$。

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
3
5 -1
1 2
3 -3
6
16 0.125
14 0.2727
18 -0.125
4  0.8333
12 0.3
6  0.5714
3
4 1
4 0.5
0 2.25
4
3 0
5 -1
0 0.75
1 0.5

Sample Output

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

hint

Javascript Animation Click It !

example 1
example 2
example 3
example 4

Solution

1
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 +
解題區/解題區 - 其他題目

ZJOI 2012 DAY2 灾难

Problem

阿米巴是小强的好朋友。
阿米巴和小强在草原上捉蚂蚱。小强突然想，如果蚂蚱被他们捉灭绝了，那么吃蚂蚱的小鸟就会饿死，而捕食小鸟的猛禽也会跟着灭绝，从而引发一系列的生态灾难。
学过生物的阿米巴告诉小强，草原是一个极其稳定的生态系统。如果蚂蚱灭绝了，小鸟照样可以吃别的虫子，所以一个物种的灭绝并不一定会引发重大的灾难。
我们现在从专业一点的角度来看这个问题。我们用一种叫做食物网的有向图来描述生物之间的关系：
一个食物网有N个点，代表N种生物，如果生物x可以吃生物y，那么从y向x连一个有向边。
这个图没有环。
图中有一些点没有连出边，这些点代表的生物都是生产者，可以通过光合作用来生存； 而有连出边的点代表的都是消费者，它们必须通过吃其他生物来生存。
如果某个消费者的所有食物都灭绝了，它会跟着灭绝。
我们定义一个生物在食物网中的“灾难值”为，如果它突然灭绝，那么会跟着一起灭绝的生物的种数。
举个例子：在一个草场上，生物之间的关系是：

如果小强和阿米巴把草原上所有的羊都给吓死了，那么狼会因为没有食物而灭绝，而小强和阿米巴可以通过吃牛、牛可以通过吃草来生存下去。所以，羊的灾难值是1。但是，如果草突然灭绝，那么整个草原上的5种生物都无法幸免，所以，草的灾难值是4。
给定一个食物网，你要求出每个生物的灾难值。

Input

第一行是一个正整数N，表示生物的种数。生物从1标号到N。
接下来N行，每行描述了一个生物可以吃的其他生物的列表，格式为用空格隔开的若干个数字，每个数字表示一种生物的标号，最后一个数字是0表示列表的结束。

Output

包含N行，每行一个整数，表示每个生物的灾难值。

Sample Input

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

Sample Output

1
2
3
4
5
4
1
0
0
0

Solution

解法參照網路各位大神，效率為 O(E log V)，必須為 DAG 圖。

题目大意 ：给你一个有向可拓扑图，入度为零的点成为源点，然后考虑每一个点，假若删掉了他以及对应的边，那么除他外有多少个点不可达源点。

算法 ：按拓扑序遍历N个点，将距每个点最近的必须通过的点设为它的父亲，构造出一棵树。对于每个点，若向它连边的点只有一个，其父亲就是向它连边的点；若向它连边的点不只一个，其父亲是向它连边的所有点的最近公共祖先。删掉每个点后不可达点个数就是其子树的节点个数。

這個做法接近貪婪思路，建造一個瓶頸樹，建造的過程找到最鄰近的瓶頸，而瓶頸的找法根據 LCA 完成。

  • 建造完，利用 dfs 計算子樹大小，發生 stackoverflow，系統恰好沒有抓到，改用 bfs 計算就 A 過。
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
#include <stdio.h> 
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
// http://oi.nks.edu.cn/showproblem?problem_id=2646 
#define MAXN 65536
#define LOGMAXN 17
vector<int> g[MAXN], invg[MAXN], tree[MAXN];
int indeg[MAXN] = {};
vector<int> toposort(vector<int> g[], int n) {
    vector<int> ret;
    queue<int> Q;
    int u, v;
    for (int i = 0; i <= n; i++)
        indeg[i] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < g[i].size(); j++)
            indeg[g[i][j]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0)
            Q.push(i);
    }
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        ret.push_back(u);
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if (--indeg[v] == 0)
                Q.push(v);
        }
    }
    return ret;
}
int depth[MAXN], parent[MAXN][LOGMAXN];
int getLCA(int x, int y) {
    int dist, i;
    if (depth[x] < depth[y])	swap(x, y);
    dist = depth[x] - depth[y];
    for (int i = 0; dist; i++, dist /= 2) {
        if (dist&1)	x = parent[x][i];
    }
    for (i = 0; x != y;) {
        if (parent[x][i] != parent[y][i] || (i == 0 && parent[x][i] == parent[y][i])) {
            x = parent[x][i];
            y = parent[y][i];
            i++;
        } else {
            i--;
        }
    }
    return x;
}
void buildTree(vector<int> &topo, vector<int> g[], int n) {
    for (int i = 1; i <= n; i++)
        tree[i].clear();
    int u, v;
    parent[0][0] = -1, depth[0] = 0;
    for (int i = 0; i < topo.size(); i++) {
        u = topo[i];
        if (g[u].size() == 0) {
            depth[u] = 1, parent[u][0] = 0;
            continue;
        }
        int lca = g[u][0];
        for (int j = 0; j < g[u].size(); j++)
            v = g[u][j], lca = getLCA(lca, v);
        depth[u] = depth[lca] + 1;
        parent[u][0] = lca;
        tree[lca].push_back(u);
        for (int i = 0; parent[u][i]; i++) {
            parent[u][i+1] = parent[parent[u][i]][i];
        }
    }
}
int used[MAXN], subtree[MAXN];
void sumTree(int n) {
    queue<int> Q;
    int u, v;
    for (int i = 1; i <= n; i++) {
        subtree[i] = 1;
        indeg[i] = tree[i].size();
        if (tree[i].size() == 0)	Q.push(i);
    }
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        v = parent[u][0];
        indeg[v]--;
        subtree[v] += subtree[u];
        if (indeg[v] == 0)
            Q.push(v);
    }
}
int main() {	
    int n, x, y, u, v;
    while(scanf("%d", &n) == 1) {
        for (int i = 0; i <= n; i++)
            g[i].clear(), invg[i].clear();
        for (int i = 1; i <= n; i++) {
            while (scanf("%d", &x) == 1 && x) {
                g[i].push_back(x);
                invg[x].push_back(i);
            }
        }
        vector<int> topo = toposort(invg, n);
        buildTree(topo, g, n);
        sumTree(n);
        for (int i = 1; i <= n; i++)
            printf("%d\n", subtree[i] - 1);
    }
    return 0;
}
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 +
解題區/解題區 - 其他題目

建造二元搜尋樹 O(n log n)

Problem

參照 Zerojudge d526: Binary Search Tree (BST) 按照插入的順序，建造一棵二元搜尋樹，原則上很簡單，但是很容易遇到極端的偏斜情況，如果插入順序很接近已經排序過的順序，則複雜度最慘為 O(n^2)。

Sample Input

1
2
3
4
11
368 115 121 88 741 762 801 34 41 511 60
6
5 2 10 4 9 15

Sample Output

1
2
368 115 88 34 41 60 121 741 511 762 801
5 2 4 10 9 15

Solution

核心

先稍微認識一下笛卡爾樹 (一種二元樹)，每個節點為 <key, value>，只看 key 時，笛卡爾樹是一棵二元搜尋樹，而看 value 時，它是一個最大堆 (或者是最小堆)。

在建造前，先撇清一點，笛卡爾樹的深度可能到達 n，與一般平衡樹不同。

笛卡爾樹如何建造 ? 假使已經對於 key 值由小到大排序 (升排序)，那麼將點依序插入笛卡爾樹，能保證的是－由於要符合二元搜尋樹，新加入的點一定是這棵樹某個節點的右節點。知道這一點後，再往前考慮前一次插 入的點(它原本也符合再某節點的右節點)，往這個節點往上爬，直到符合最大堆(性質 node.v > new_insert.v)，這時將這個節點的右子樹移到新加入節點的左子樹 (此時符合二元搜尋樹的性質，也保有原本堆的性質)。就這麼持續入點下去。

這麼發現，往上爬的次數不超過節點個數，因為每個節點只會從右子樹換到左子樹。均攤下 O(n) (每個節點只會從右子樹推到左子樹一次，因此最多 n 次)

我們接著將 “按照順序插入的 BST” 轉換成建造笛卡爾樹，key 值依舊為輸入的元素大小，而 value 則訂為輸入順序，根據 key 值為一個二元搜尋樹，根據 value 建造一個最小堆，那麼仔細思考可以得到與原本相同的二元搜尋樹。

建造笛卡爾樹只需要花 O(n) 時間，但建造前必須根據 key 排序 O(n log n)，所以複雜度為 O(n log n)。

在這樣的方式建造有一個缺點，並不知道途中插入的情況，只會在最後得到一樣的二元搜尋樹。假使要得到途中插入的情況，考慮離線處理，將所有操作儲存起來，而二元樹的節點位置並不會更動的情況下，事先建造一個靜態樹，隨後使用一個懶標記存在與否即可。

補充

  • 如何利用這個笛卡爾樹解決最簡單的 RMQ 問題？
    對於 <key, value> = <i, A[i]> 所建造的笛卡爾樹，可以利用 LCA 的 tarjan 算法(離線作法) 在 O(n) 時間內完成。RMQ 假使查找 [l, r] 的最小值，又因為我們根據 value 建造最小堆，則根據 tarjan 的搜索順序，拜訪右子樹時(對於區間的 r 來說)，左子樹將會跟其 LCA 合併，而 LCA 的 index 肯定比左子樹來得大 (大於等於 l)，又根據最小堆保證是大於等於 l 且小於等於 r 的最小值。
  • 只有笛卡爾樹可以做到建造二元搜尋樹嗎？
    其實並不然，還可以藉由一個額外的平衡樹來完成，效率一樣在 O (n log n)，但是親自撰寫平衡樹本身就本末倒置，如果藉由 STL 提供的平衡樹，代碼量會比笛卡爾樹好寫多。具體而言使用 lower_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
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct Node {
    int key, value;
    int lson, rson, parent;
};
Node D[65536];
void insertCartesianTree(int index, Node D[]) {
    int p = index - 1;
    while(D[p].value > D[index].value)
        p = D[p].parent;
    D[D[p].rson].parent = index;
    D[index].lson = D[p].rson;
    D[p].rson = index;
    D[index].parent = p;
}
void dfsPrint(int node) {
    if(node == 0)    return;
    printf("%d ", D[node].key);
    dfsPrint(D[node].lson);
    dfsPrint(D[node].rson);
}
int main() {
    int N, x;
    pair<int, int> A[65536];
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 1; i <= N; i++) {
            scanf("%d", &x);
            A[i] = make_pair(x, i);
        }
        sort(A+1, A+1+N);
        D[0].value = -1;
        D[0].lson = D[0].rson = D[0].parent = 0;
        for(int i = 1; i <= N; i++) {
            D[i].lson = D[i].rson = D[i].parent = 0;
            D[i].value = A[i].second, D[i].key = A[i].first;
        }
        for(int i = 1; i <= N; i++) {
            insertCartesianTree(i, D);
        }
        dfsPrint(D[0].rson);
        puts("");
    }
    return 0;
}
Read More +
學校課程/通識課程

[通識] 文明的進程 Week 3

上週因為上課在想題目，花了一大段時間在挑戰不可能的任務，最後宣告無法在指定要求下的時間內完成。

首先，講到十五世紀到文藝復興這段時間，歐洲開始興起的禮儀運動，儘管當時的跟現代禮儀差距是巨大的，那時人們認為的禮貌到了現代說不定還會被當作詬病。

禮貌運動從何來？為什麼突然會有禮貌之分？要求別人也要有禮貌，為了看起來合適、舒服？什麼是 羞恥 、 嬌貴 ？對於沒有在自然界存有的情感，人類為什麼卻擁有？

這些都源自於 階級 的出現，為了凸顯同種之間的高低之分，階級是很重要的，以人類而言，同種之間差別不太能從外表體現，就以行為舉止來作為第一印象。為什麼一開始不說外表呢？在物質還沒有這麼豐裕之前，其實貴族和平民之間差別並不大，所以追溯歷史，一開始比較注重行為舉止，往後才在物質豐饒的社會中，開始利用光鮮亮麗的裝飾品來凸顯階層。

階級仇視，每當越強調階級之差時，人民對於仇視的怨念增強，不外乎看看我們的 PTT 鄉民們，好吧，也許不是，那島民呢？

從刀槍物質上的強大區分階級，隨後已經變成了無形的距離之差反應階級，看著那騎士精神的消散，就能明白人們不再以武力來講自己有多偉大、崇高。

「我比你高貴，但不是單純的外在，而是你那難以進化的心靈。」

現代如何區分過去？我們開始追求極簡化的結構、嚴謹的環境以及情感上所呈現的一種寧靜安穩的姿態，講著講著，有點類似難以動搖的心靈，受任何波折都不容易易怒。說來笑話，這有點 面癱 了，都要變成非生物的巨石，也許擺脫生物本能變成大自然的一部分，才是真正的高貴吧！

為什麼宗教會興盛？從現代人的眼光來看，有普及教育的出現，信不信教沒有特別的意義，但為什麼還有人信？就是看著原先那些信教的人們，看起來比較崇高、端莊，加入宗教就能與它們站在相同的地位，向宗教最高的神悔過自己的罪孽，不斷地心靈規訓，就能煥然一新？

加入咱們宗教，就能升一級哦！你就會有所不同！

把持不住的孩子們都去了，人活著就耐不住寂寞、離群，「照著人多的地方走，肯定不會有問題的！」某方面的確是這樣，這沒有什麼對錯，「我思故我在」你曾是否講過做點不同的？還是一本死嗑？

禮儀書是什麼？告訴你「 如何去做 」出這種書的人自己不去做嗎？又是哪種人出了這種書？社會階層流動時，人們有機會往上爬，才會去夢、才有動力，禮儀書正是隨著洪流而出，學習與分享，只有下階層的人們才懂得那些事。

那上面的人要怎麼穩固自己的勢力呢？把原本區分階級的方式變得更加複雜，倒不如說奇特、古怪，努力地推層出新，就是為了要防止自我的存在貶值。

聽著老師說的這些，看來我要去悔過。

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 +