解題區►解題區 - UVa

UVa 12452 - Plants vs. Zombies HD SP

Problem

給一個 N 個點的樹圖，在點上放置植物保護所有的邊，每個點上最多放置一個植物，請問最少花費為何？

  • 綠豆槍手：花費 100 元，保護相鄰一條邊。
  • 分裂碗豆：花費 175 元，保護相鄰兩條邊。
  • 楊桃：花費 500 元，保護相鄰所有邊。

Sample Input

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

Sample Output

1
2
$100
$175

Solution

將樹轉換成有根樹，對於每一個 node 當成 tree 去做考慮。

狀態 dp[node][1:protect edge from parent, 0:none]

以 node 以下作為一個 subtree 的最少花費，並且是否已經保護通往父親的邊。

效率 O(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
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 32767
vector<int> g[MAXN];
long long dp[MAXN][2]; // [node][1:protect edge from parent, 0:none]
#define INF (1LL<<50)
void dfs(int u, int p) {
	
	dp[u][0] = dp[u][1] = INF;
	
	long long cost[3] = {};
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (v == p)	continue;
		dfs(v, u);
		cost[0] += dp[v][0];
		cost[1] += dp[v][1];
		cost[2] += min(dp[v][0], dp[v][1]);
	}
	dp[u][0] = min(dp[u][0], cost[1]);
	dp[u][1] = min(dp[u][1], cost[1] + 100);
	dp[u][1] = min(dp[u][1], cost[2] + 500);
	
	long long c[2] = {INF, INF};
	for (int i = 0; i < g[u].size(); i++) {// two edge with subnode and parent.
		int v = g[u][i];
		if (v == p)	continue;
		dp[u][1] = min(dp[u][1], cost[1] - dp[v][1] + dp[v][0] + 175);
		if (-dp[v][1] + dp[v][0] < c[1]) {
			c[1] = -dp[v][1] + dp[v][0];
			if (c[0] > c[1])	swap(c[0], c[1]);
		}
	}
	// two two edge with two subnodes
	dp[u][0] = min(dp[u][0], cost[1] + c[0] + c[1] + 175);
}
int main() {
	int testcase, n;
	int u, v;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			g[i].clear();
		for (int i = 1; i < n; i++) {
			scanf("%d %d", &u, &v);
			g[u].push_back(v);
			g[v].push_back(u);
		}
		dfs(0, -1);
		printf("$%lld\n", min(dp[0][0], dp[0][1]));
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12440 - Save the Trees

Problem

有一排樹，每個樹分別有 type 和 height，現在要將其分團，

  • 每一團內不允許有相同的 type
  • 每一團的花費是最高的 height

計算總花費最小為何？

Sample Input

1
2
3
4
5
6
7
1
5
3 11
2 13
1 12
2 9
3 13

Sample Output

1
Case 1: 26

Solution

藉由掃描線的思路，可以得知每一個樹的位置 i，往左延伸最大多少內不會有重複的 type。詳見 12890 - Easy Peasy 的技巧。

因此會得到公式 $dp([i]) = min(dp[j - 1] + max(height[k])), j \geq f(i), j \le k \le i$

dp[i]：將前 i 個樹分團的最少費用。

計算這個公式需要 O(n^2)，由於 n 很大，必須找一個優化將其降下來。

首先知道 f(i) 是非遞減函數 (會一直增加)，單純看 i 時，dp[j - 1] 是固定的，但
max(height[k]) 會逐漸增加，如果能在 O(log n) 時間進行更新、詢問，複雜度將可以降至 O(n log n)。

每個元素有兩個屬性 (a, b)

  • query(f(i), i) : return min(A[k].a + A[k].b), f(i) <= k <= i
  • update(f(i), i, height[i]) : A[k].b = max(A[k].b, height[i])

左思右想仍然沒有辦法用線段樹完成它，至少是一個很 tricky 的花費計算。

有一個貪心的思路，考慮區間內的計算時，只需要找到嚴格遞減的高度進行更新即可，並非所有的可能進行嘗試。用一個單調隊列，只記錄 [f(i), i] 之間的嚴格遞減的高度資訊，接著每次需要窮舉單調隊列內的所有元素。

複雜度最慘還是 O(n^2)，隨機測資下速度是快非常多的。

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 <map>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 131072
int type[MAXN], height[MAXN];
long long dp[MAXN];
int dQ[MAXN];
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	int testcase, cases = 0;
	int n;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
			scanf("%d %d", &type[i], &height[i]);
		map<int, int> R;
		int L = 0;
		dp[0] = 0;
		int head = 0, rear = -1;
		for (int i = 1; i <= n; i++) {
			int &y = R[type[i]];
			L = max(L, y);
			y = i;
			while (head <= rear && dQ[head] <= L)
				head++;
			while (head <= rear && height[dQ[rear]] <= height[i])
				rear--;
			dQ[++rear] = i;
			
			dp[i] = 1LL<<60;
			for (int j = head; j <= rear; j++) {
				if (j != head)
					dp[i] = min(dp[i], dp[dQ[j-1]] + height[dQ[j]]);
				else
					dp[i] = min(dp[i], dp[L] + height[dQ[j]]);
			}
		}
		printf("Case %d: %lld\n", ++cases, dp[n]);
	}
	return 0;
}
/*
1
5
3 11
2 13
1 12
2 9
3 13
30
10
4 13
2 18
7 20
1 16
1 14
10 5
5 11
7 19
8 12
2 16
9999
10
10 16
3 5
8 11
8 2
5 3
6 2
10 19
6 10
6 16
6 4
9999
10
3 6
10 5
2 9
5 2
9 3
3 8
6 10
4 17
7 10
6 11
*/
Read More +
解題區►解題區 - UVa

UVa 1382 - Distant Galaxy

Problem

給平面上 N 個點，找一個最大矩形，使得矩形邊上有最多點個數。

Sample Input

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

Sample Output

1
Case 1: 7

Solution

UVa 1382

先離散化處理，將所有點放置在 grid[100][100] 內。

接著窮舉上下兩條平行線，由左而右開始掃描，邊緣的個數為 V[U1] + V[U2] + H[R] - V[U3] + V[U4] + H[L]，掃描時維護 V[U3] + V[U4] - H[L] 的最小值。

特別小心矩形的四個頂點的排容，上述的公式仍然不太夠。由於題目沒有特別要求正面積矩形，必須考慮共線上最多的點個數。

效率 O(n^2)。

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
#include <stdio.h> 
#include <map>
#include <algorithm>
using namespace std;
int main() {
	int n, x[128], y[128];
	int cases = 0;
	while (scanf("%d", &n) == 1 && n) {
		map<int, int> Rx, Ry;
		for (int i = 0; i < n; i++) {
			scanf("%d %d", &x[i], &y[i]);
			Rx[x[i]] = 0, Ry[y[i]] = 0;
		}
		
		int size, R, C;
		size = 0;
		for (map<int, int>::iterator it = Rx.begin();
			it != Rx.end(); it++) {
			it->second = size++;
		}
		R = size;
		size = 0;
		for (map<int, int>::iterator it = Ry.begin();
			it != Ry.end(); it++) {
			it->second = size++;
		}
		C = size;
		
		int g[128][128] = {}, ret = 0;
		for (int i = 0; i < n; i++) {
			int r, c;
			r = Rx[x[i]], c = Ry[y[i]];
			g[r][c]++;
		}
		
		for (int i = 0; i < R; i++) {
			int sum[128] = {}, s1, s2, mn;
			for (int j = i; j < R; j++) {
				s1 = s2 = 0, mn = 0;
				for (int k = 0; k < C; k++) {
//					printf("[%d %d] %d\n", i, j, k);
					sum[k] += g[j][k];
					s1 += g[i][k], s2 += g[j][k];
					if (i != j) {
//						printf("%d %d %d %d = %d\n", s1, s2, mn, sum[k], s1 + s2 - mn + sum[k]);
						ret = max(ret, s1 + s2 - mn + sum[k] - g[i][k] - g[j][k]);
						mn = min(mn, s1 + s2 - sum[k]);
					}
				}
			}
		}
		
		for (int i = 0; i < R; i++) {
			int sum = 0;
			for (int j = 0; j < C; j++)
				sum += g[i][j];
			ret = max(ret, sum);
		}
		
		for (int i = 0; i < C; i++) {
			int sum = 0;
			for (int j = 0; j < R; j++)
				sum += g[j][i];
			ret = max(ret, sum);
		}
		printf("Case %d: %d\n", ++cases, ret);
	}
	return 0;
}
/*
10 
2 3 
9 2 
7 4 
3 4 
5 7 
1 5 
10 4 
10 6 
11 4 
4 6 
3
1 1
2 1
3 1
3
1 1
1 2
1 3
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
*/
Read More +
學校課程►通識課程

[通識] 文明的進程 Week 11

主題－攻擊欲的轉變

不知何時開始，人們對於暴力行為開始無法容忍，逐漸地喪失對於暴力的經驗。曾經也打過架，恨不得把對方殺了，即使捶得再大力也弄不出傷口來，也許被馴化的怒火無法傷害任何人，只剩下精神上的威嚇。拿刀殺人的場景不是在電視情節中，就只能在夢裡、幻想裡去想這些。

同類相互攻擊在大自然中常見不過的事，為什麼在人類身上卻逐漸消失？沒錯！因為我們有穿越好幾世代的外部記憶體－文化。

攻擊欲

曾經的人們為了生活，長久時間的定居，明天在哪都不曉得。只要一戰爭，贏了高興，輸了什麼都沒，生命就是這麼地短暫，中古世紀曾有一段話「看見死亡才能安心、吃得好、睡得好」那是在什麼樣的生存條件下，活著不是殺死對方，又是被殺、被壓迫的日子。面對死亡才能安心，這才是真正的活著！「 未知死，焉知生 」古人說得有道理。

為什麼至今仍有黑道白道之分？當白道無法解決的事情，黑道顯得更有威震力，看看「日本黑道山口組」在許多電影情節中，黑道的存在反而凸顯了到底是傾聽社會聲音做事？還是聽從自己的本能。社會給予的牢籠，促使我們不做暴力的行為，隱藏自己的情感，然而這些情感去哪了？

沒有暴力的行為，如何表示自己的不滿？敵意？產生出的無力感、關係冷漠、義憤，用另外一種方式宣洩自己的攻擊欲，「 如果這些世界不接受我，那就摧毀這個世界吧！ 」沒了直來直往的暴力世界，卻產生出兩個極端的世界，被壓抑著暴力的人們何時會爆發呢？

殘暴的必要性－對敵人寬厚，就是壯大對方，未來必有危害，「斬草不除根，春風吹又生」不殺行嗎？用仁慈看那個世界，你就是找死！然而現今的攻擊欲，單純的攻擊欲也傷不了任何人，用武器所需要的技術越來越高，沒有技術也殺不死人，這片高牆越來越高厚呢。

陽剛

起初所謂的陽剛只得是什麼？不正是那殘暴的事實嗎？現今看看那些陽剛的定義，早已經被陰柔化，受到捧吹的帥哥又是在古時的男人嗎？追求性別平等的代價，造成暴力的消失，如果還要展現自己的暴力，只能迂迴表達自己那一身的肌肉。

行刑

既然沒法殺人，公開行刑正是大眾娛樂，一個人被處刑，整座城市的人都在看，這是為什麼？在電影情節中，殺人的血腥畫面是否令人振奮？追求安心才是本能！

現在有很多不殺人的行刑，例如剝奪尊嚴，相當於利用羞恥感、價值觀的攻擊，文化的禁忌－身體的隱蔽性，這還不讓人精神崩潰嗎？讓一個人不成人形的方式很多，精神是如此地脆弱。

死亡

過去人們很難活長，活到三、四十歲就算有幸，也因為戰爭死亡相當常見，如果人們對死亡感到悲傷，豈不是沒辦法過生活？整年都要哭天喊地的，你能說他們無情嗎？不行，他們本應該這麼做，否則沒辦法前進。

古人很容易 認命 ，對於前途未卜的不安，明天還能活著嗎？戰爭就在那麼一夕之間開打，生計被土地綁著，想走也走不了。有一夜沒一夜的的恐懼，「 今宵有酒今宵醉 」死了就什麼都沒了，為何不現在享用？總是 盤算未來 ，那是你們現代人的奢侈。

血濃於水，資產階級興起後，家族之間的私鬥相當常見，衝突一來，不少家族因此滅絕。信得過的人只有血緣關係的人，不要說為何當官的都想找自己人，找不同處境的人，不怕在背後被人捅一刀嗎？(不論豬隊友)

活在當下，並非沒有遠見、逃避現實 ，誰知道明天在哪？那等絕望，你還有盤算未來的本錢嗎？

剝奪

如何表示對別人的不滿？當下只剩下視覺的攻擊，作為一個活在現代的人，動手動腳就已經輸一半，觸覺已被作為侵略他人身體的領域，嗅覺則不能作為認識人的方法 (因為那如野獸一樣)。

視覺已成為唯一攻擊欲的發揮。觀賞球類運動也是如此，作為球迷欣賞支持的隊伍侵略，但自己除了看，什麼事情都不能做，一旦做了就是不文明的舉動。

暴力遊戲會使得人暴力嗎？愚蠢的人們啊，在怎麼轉換情感，也不可能百分百的宣洩。

魅力化

論吸血鬼、狼人的暴力魅力化，腐女們準備好了嗎？

以下開放暴動。本文 … 略。

Read More +
學校課程►自然語言

自然語言處理 論文研讀 2

著重目標

即使 Unigram 效果已經相當不錯，基於人類日常對話的模式，絕非單詞相依無關，藉由好幾個連詞表示出不同的意思是常有的事情，探討 n-grams (n > 3) 對於當前的語意分類器的強化、優化。

已知問題

當 n-grams (n > 3) 時，語意的模糊性質會提高，可能同時把正反兩面的詞放置在一起，如此一來這一組的利用價值並不高，在計算分類上會將精準度稀釋，同時對於記憶體的負荷也會增加 (必須記錄各種組合，例如化學元素與化合物的數量大小關係)。

接著 n-grams 通常是用在英文處理精準度比較好，因為 單詞分明 (藉由空白隔開)，對於機器而言中文句子並不存在詞 (token)，都是一堆字元 (character)。

研究顯示： 漢字順序並不一定影響閱讀

請看下述文字－研究顯示：漢字序順並不定一影閱響讀。

對於中文自然語言處理，斷詞的重要性、語意處理上有額外的研究領域，在這裡暫時不談論這些。也許可以談談看不考慮順序的 n-grams，型態從 tuple 變成 dag。

分類器

分類器分成線上訓練、離線訓練，就已知得到目前 SVM 仍然在實務上的效果是最好的，在這裡不談論 SVM，一部分原因是 SVM 太慢。

下面是在不同領域的分類器構思，線上訓練、線性調整。大多數的分類器都必須定義特徵，對於每一個要分辨的項目是否存有這一個特徵 (boolean)，而在部分可允許模糊的模型，可以利用權重 (float) 表示特徵強弱。

類神經網路

Passive-Aggressive Algorithm

對於感知機的內容所知不多，每加入一筆結果，將劃分的依準疊加上預期的法向量，成為新的劃分依準線。大多依靠數學的微積分來完成，並非完全相信新加入的結果，因此會有一個計算的權重，來權衡影響的大小。

訓練流程：

$$\begin{align} & \text{INITIALIZE : } w_{1} = (0 ... 0) \text{ as parameters of the classifier} \\ & \text{For } t = 1, 2, ... \\ & \text{receive instance : } x_{t} \in R^{n} \\ & \text{predict : } \hat{y_{t}} = sign(w_{t}, x_{t}) \\ & \text{receive correct label : } y_{t} \in {-1, +1} \\ & \text{suffer loss : } l_{t} = max\left \{ 0, 1 - y_{t}(w_{t} \cdot x_{t}) \right \} \\ & \text{update-1: set : } \tau_{t} = \frac{l_{t}}{\left \| x_{t} \right \|^{2}} \\ & \text{update-2: update : } w_{t+1} = w_{t} + \tau_{t} y_{t} x_{t} \end{align}$$

自然語言

Language Modeling

就如上課內容所講的

$$\begin{align} P(s) = \prod_{i = 1}^{l} P(w_{i}|w_{1}^{i-1}) \end{align}$$

用 Good Turing 的方式去 smoothing 那些從未在模型中出現的詞語，它們是有機會的，絕非是機率 0。

機器學習

Winnow algorithm

設定一個閥值作為是否存在此分類的依據，隨後根據閥值調整相關數據的參數大小。

$$h(x) = \sum_{w \in V}^{} f_{w}c_{w}(x)$$ $f_{w}$ 是需要調整的參數，$c_{w}(x)$ 為資料在每一個特徵的權重向量，運算內積值為 $h(x)$。

訓練流程：

$$\begin{align} & \text{Initialize all } f_{w} \text{ to 1.} \\ & \text{For each labeled revies x in the training set : } \\ & \text{Step 1. Calculate } h(x) \\ & \text{Step 2-1. If the revies is positive but Winnow predicts it as negative } \\ & h(x) < V \text{ , update the weight} f_{w} \text{ where } c_{w}(x) = 1 \text{ by } f'_{w} = f_{w} \times 2 \\ & \text{Step 2-2. If the revies is negative but Winnow predicts it as positive } \\ & h(x) > V \text{ , update the weight} f_{w} \text{ where } c_{w}(x) = 1 \text{ by } f'_{w} = f_{w} / 2 \\ \end{align}$$

簡單來說，當判斷錯誤時，將相關的 (它有的) 特徵係數權重調整，將其變大使得納入分類中、或者將其變小踢出分類中。

調和

為了加入 n-grams (n > 3) 的機制，必然要學習 忘記 、 無視 的才能，才能將垃圾訊息給捨去掉。同時也是降低記憶體的耗存的方法，這裡無法像人類有辦法根據時間將單詞組合抽象化，等到哪天 HTM 腦皮質學習算法 成功實作，相信在取捨上會更為流暢。

對於每一個特徵給予分數，保留前 K 好的特徵進行訓練，其餘特徵捨去，至於要保留的 K 大小將由實驗結果進行測試。

分數計算：

  • A：同一分類下，該屬性使用的資料筆數
  • B：在其他分類下，該屬性被使用的資料筆數
  • C：同一分類下，該屬性不使用的資料筆數
  • D：在其他分類下，該屬性不被使用的資料筆數
  • t：屬性
  • c：分類
$$\begin{align} x^{2}(t, c) = \frac{N \times (AD - CB)^{2} }{(A+C)\times (B + D) \times (A + B) \times (C + D)} \end{align}$$

結論

論文中提到，分別去了 50K、100K、200K 個分數高的 n-grams，又分別在 n = 3, 4, 5, 6 下進行測試，效果有那麼一點點地提升。

接著就是考驗我們期末 Project 要怎麼體現這篇論文的思路、擴充。

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

UVa 12873 - The Programmers

Problem

給 P 個隊伍、S 個賽區，每隊分別都有可以去的賽區，而每一個賽區最多容納 C 個隊伍。

請問參加的總隊伍數量最大為何？

Sample Input

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

Sample Output

1
2
2
3

Solution

建造 maxflow 模型，source - team - site - sink 即可完成。

不是說好 maxflow 不太會考的嗎？結果還是在泰國賽區出來了，雖然之前也噴過 mincost 最少費用流 …

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
using namespace std;
const int MAXV = 40010;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
    int v, cap, flow;
    Edge *next, *re;
} Edge;
class MaxFlow {
public:
    Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
    int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
    void Init(int x) {
        n = x, e = 0;
        for (int i = 0; i < n; ++i) adj[i] = NULL;
    }
    void Addedge(int x, int y, int flow){
        edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
        edge[e].re = &edge[e+1], adj[x] = &edge[e++];
        edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
        edge[e].re = &edge[e-1], adj[y] = &edge[e++];
    }
    void Bfs(int v){
        int front = 0, rear = 0, r = 0, dis = 0;
        for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
        level[v] = 0, ++lvCnt[0];
        Q[rear++] = v;
        while (front != rear){
            if (front == r) ++dis, r = rear;
            v = Q[front++];
            for (Edge *i = adj[v]; i != NULL; i = i->next) {
                int t = i->v;
                if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
            }
        }
    }
    int Maxflow(int s, int t){
        int ret = 0, i, j;
        Bfs(t);
        for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
        for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
        i = s;
        while (level[s] < n){
            while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow))
                arc[i] = arc[i]->next;
            if (arc[i]){
                j = arc[i]->v;
                pre[j] = arc[i];
                i = j;
                if (i == t){
                    int update = INF;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        if (update > p->flow) update = p->flow;
                    ret += update;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        p->flow -= update, p->re->flow += update;
                    i = s;
                }
            }
            else{
                int depth = n-1;
                for (Edge *p = adj[i]; p != NULL; p = p->next)
                    if (p->flow && depth > level[p->v]) depth = level[p->v];
                if (--lvCnt[level[i]] == 0) return ret;
                level[i] = depth+1;
                ++lvCnt[level[i]];
                arc[i] = adj[i];
                if (i != s) i = pre[i]->re->v;
            }
        }
        return ret;
    }
} g;
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        int P, S, C, m, x, y;
        scanf("%d %d %d %d", &P, &S, &C, &m);
        g.Init(P + S + 2);
        int source = 0, sink = P + S + 1;
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            g.Addedge(x, P + y, 1);
        }
        for (int i = 1; i <= P; i++)
            g.Addedge(source, i, 1);
        for (int i = 1; i <= S; i++)
            g.Addedge(P + i, sink, C);
        int ret = g.Maxflow(source, sink);
        printf("%d\n", ret);
    }
    return 0;
}
/*
 2
 2 2 1 4
 1 1
 1 2
 2 1
 2 2
 4 3 1 12
 1 1
 1 2
 1 3
 2 1
 2 2
 2 3
 3 1
 3 2
 3 3
 4 1
 4 2
 4 3
*/
Read More +
解題區►解題區 - UVa

UVa 12872 - Hidden Plus Signs

Problem

盤面上放置許多 + 展開，保證寬高相同並且不會超出格子外部，同時每一個大小不超過 11。而十字中心不會被其他十字覆蓋，每一格會顯示被覆蓋幾次。

找到一種放置方法，復原盤面結果，如果有種放置方法，選擇一種字典順序最小的輸出。

Sample Input

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

Sample Output

1
2
3
4
2
3 3
9
8 10

Solution

論窮舉順序的重要性，將會導致速度的快慢。

原則上先把所有 1 的位置挑出，依序窮舉每一個 1 是否可以進行放置。每一次選擇放置時，先從最大的寬高開始嘗試，先塞掉大多數的盤面結果，否則速度會被拉下。

不確定這一題是否有很正統的作法，求指導。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int g[32][32], n, m;
int A[900][2], N, SUM = 0;
int isEmpty() {
	return SUM == 0;
}
void remove(int x, int y, int w) {
	for (int i = x - w; i <= x + w; i++)
		g[i][y]--, SUM--;
	for (int i = y - w; i <= y + w; i++)
		g[x][i]--, SUM--;
	g[x][y]++, SUM++;
}
void resume(int x, int y, int w) {
	for (int i = x - w; i <= x + w; i++)
		g[i][y]++, SUM++;
	for (int i = y - w; i <= y + w; i++)
		g[x][i]++, SUM++;
	g[x][y]--, SUM--;
}
int place(int x, int y, int w) {
	for (int i = x - w; i <= x + w; i++)
		if (!g[i][y])
			return 0;
	for (int i = y - w; i <= y + w; i++)
		if (!g[x][i])
			return 0;
	return 1;
}
int dfs(int idx, int used, int LX, int LY) {
	if (isEmpty()) {
		printf("%d\n%d %d\n", used, LX + 1, LY + 1);
		return 1;
	}
	if (idx == N)
		return 0;
	int t = min(min(A[idx][0], A[idx][1]), min(n - 1 - A[idx][0], m - 1 - A[idx][1]));
	for (int i = t; i >= 1; i--) {
		if (place(A[idx][0], A[idx][1], i)) {
			remove(A[idx][0], A[idx][1], i);
			if (dfs(idx+1, used + 1, A[idx][0], A[idx][1]))
				return 1;
			resume(A[idx][0], A[idx][1], i);
		}
	}
	if (dfs(idx+1, used, LX, LY))
		return 1;
	return 0;
}
int main() {
	int testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &m);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				scanf("%d", &g[i][j]), SUM += g[i][j];
		N = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (g[i][j] == 1)
					A[N][0] = i, A[N][1] = j, N++;
		dfs(0, 0, -1, -1);
	}
	return 0;
}
/*
2
5 5
0 1 1 0 0
1 1 2 0 0
1 2 1 1 1
0 0 1 0 0
0 0 1 0 0
10 11
0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 1 1 0 1 0 0 0
0 0 1 1 1 2 2 1 1 0 0
0 0 1 2 2 1 1 2 2 0 0
0 0 1 1 3 1 0 0 1 0 0
0 0 0 2 1 2 2 1 1 1 1
0 1 0 0 1 1 1 0 1 1 0
1 1 1 0 1 1 1 1 3 1 1
0 1 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0 0 0 0
*/
Read More +
解題區►解題區 - UVa

UVa 12871 - Landmine Cleaner

Problem

給予每一個格子的得分，分數為鄰近九格的 L 個數 (1 個 1 分) 加上自己是否為 L (3 分)，因此最低 0 分，最高 12 分。

保證只有唯一解。

Sample Input

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

Sample Output

1
2
3
-L--
L-LL
LL--

Solution

不斷地刷新已知的可能結果，慢慢從邊緣開始向內侵蝕已知解。

要做整數線性規劃看來是不可能，用刷新的方式看看是否可以噴出解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXN 1024
int A[MAXN][MAXN], solv[MAXN][MAXN];
int g[MAXN][MAXN];
const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[] = {1, -1, 0, 1, -1, 0, 1, -1};
int n, m;
int isplace(int x, int y) {
	int v = A[x][y], tx, ty;
	int unknown = 0, score = 0;
	for (int i = 0; i < 8; i++) {
		tx = x + dx[i], ty = y + dy[i];
		if (tx < 0 || ty < 0 || tx >= n || ty >= m)
			continue;
		if (solv[tx][ty])	score += g[tx][ty];
		else				unknown++;
	}
	if (v < 3)					return -1;
	if (v > 8)					return 1;
	if (score + unknown < v)	return 1;
	if (score + 4 > v)			return -1;
	return 0; // not sure.
}
int main() {
	int testcase;
	int t;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &m);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				scanf("%d", &A[i][j]);
			}
		}
		memset(solv, 0, sizeof(solv));
		int test = n * m;
		while (test) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (solv[i][j])	continue;
					int t = isplace(i, j);
					if (t) {
						test--;
						g[i][j] = t > 0;
						solv[i][j] = 1;
					}
				}
			}
			
		}
		for (int i = 0; i < n; i++, puts("")) {
			for (int j = 0; j < m; j++) {
				if (solv[i][j])
					putchar(g[i][j] ? 'L' : '-');
				else {
					assert(false);
				}
			}
		}
	}
	return 0;
}
/*
9999
3 4
2 6 3 2
7 5 7 5
6 7 3 2
3 3
7 9 7
9 12 9
7 9 7
3 1
0
0
0
*/
Read More +
解題區►解題區 - UVa

UVa 12431 - Happy 10/9 Day

Problem

計算 base B 下，每一個 digit 都是 d 的情況，長度為 N，mod M 的結果為何？

Sample Input

1
2
1
3 10 2 10

Sample Output

1
Case 1: 2

Solution

找到

$$d B^{0} + d B^{1} + ... + d B^{N-1} \text{ mod } M \\ \Rightarrow d \frac{B - 1}{B^{N} - 1} \text{ mod } M$$

由於 M 超過 int，運算起來仍有機會 overflow，因此要使用模乘法，也就是相當於直式乘法的運算，防止 (a*b) mod M 溢位。

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
#include <stdio.h> 
long long mul(long long a, long long b, long long mod) { 
	long long ret = 0; 
	for( ; b != 0; b>>=1, (a<<=1)%=mod) 
		if(b&1) (ret += a) %= mod; 
	return ret; 
}
long long mpow(long long x, long long y, long long mod) {
	long long ret = 1;
	while (y) {
		if (y&1)
			ret = mul(ret, x, mod);
		y >>= 1, x = mul(x, x, mod);
	}
	return ret;
}
long long solve(long long n, long long b, long long d, long long m) {
	// d * (b^n - 1) / (b - 1) mod m
	long long ret;
	ret = mpow(b, n, (b - 1) * m); // b^n mod (b-1) * m
	ret = (ret + (b - 1) * m - 1)/ (b - 1);
	ret = mul(ret, d, m);
	return ret;
}
int main() {
	int testcase, cases = 0;
	scanf("%d", &testcase);
	while (testcase--) {
		long long n, b, d, m, ret;
		scanf("%lld %lld %lld %lld", &n, &b, &d, &m);
		ret = solve(n, b, d, m);
		printf("Case %d: %lld\n", ++cases, ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12425 - Best Friend

Problem

給一個整數 N，接著詢問 x，有多少 gcd(i, N) <= x。

Sample Input

1
2
3
4
5
6
7
8
2
30 3
1
2
10
11 2
1
2

Sample Output

1
2
3
4
5
6
7
Case 1
8
16
28
Case 2
10
10

Solution

先把 N 的因數 f 全部找出，原則上不超過 2000 個，然後建出 phi(N/f[i])。

當要知道 gcd(i, N) = x 時，相當於找到 gcd(i/x, N/x) = 1，任何與 N/x 互質的個數。建造完後，對於每次詢問二分答案即可。

很多地方忘記用 long long，吃了不少 Runtime error。

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
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define maxL (1000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
int P[100000], Pt = 0;
int phi[1048576];
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 1000000;
    for (i = 1; i <= n; i++)
    	phi[i] = i;
    for (i = 2; i <= n; i++) {
        if(!GET(i)) {
            for (k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            for (j = i; j <= n; j += i)
            	phi[j] = phi[j]/i * (i-1);
            P[Pt++] = i;
        }
    }
}
vector< pair<long long, int> > factor(long long n) {
	long long on = n;
	vector< pair<long long, int> > R;
	
	for(int i = 0, j; i < Pt && (long long)P[i] * P[i] <= n; i++) {
		if(n%P[i] == 0) {		
			for(j = 0; n%P[i] == 0; n /= P[i], j++);
			R.push_back(make_pair((long long)P[i], j));
		}
	}
	if(n != 1)	R.push_back(make_pair(n, 1));
	return R;
}
void make(int idx, int n, long long m, vector< pair<long long, int> > &v, vector<long long> &ret) {
	if(idx == v.size()) {
		ret.push_back(m);
		return;
	}
	long long a = m, b = v[idx].first;
	for(int i = v[idx].second; i >= 0; i--)
		make(idx + 1, n, a, v, ret), a *= b;
}
long long getPhi(long long n) {
	if (n < 1000000)	return phi[n];
	vector< pair<long long, int> > f = factor(n);
	for (int i = 0; i < f.size(); i++)
		n = n / f[i].first * (f[i].first - 1);
	return n;
}
int main() {
	sieve();
	int testcase, cases = 0, Q;
	long long N, X;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%lld %d", &N, &Q);
		vector< pair<long long, int> > f = factor(N);
		vector<long long> fa;
		vector<long long> sum;
		make(0, N, 1, f, fa);
		sum.resize(fa.size(), 0);
		sort(fa.begin(), fa.end());
		for (int i = 0; i < fa.size(); i++) {
			if (i)
				sum[i] = sum[i-1] + getPhi(N / fa[i]);
			else
				sum[i] = getPhi(N / fa[i]);
		}
		printf("Case %d\n", ++cases);
		for (int i = 0; i < Q; i++) {
			scanf("%lld", &X);
			if (X <= 0) {
				puts("0");
				continue;
			}
			long long ret = 0;
			int pos = (int)(lower_bound(fa.begin(), fa.end(), X) - fa.begin());
			if (pos >= fa.size() || fa[pos] > X)	pos--;
			ret = sum[pos];
			printf("%lld\n", ret);
		}
	}
	return 0;
}
/*
2
30 3
1
2
10
11 5
0
1
2
11
15
*/
Read More +