Programming學習筆記: 3月 2014

Longest Increased/Decreased Subsequence
想法：
替數列建LIS和LDS表，然後在從表中找出共同最大的數字。例如：
數列： 1 2 3 4 5 3 2
LIS： 0 1 2 3 4 0 0
LDS： 0 0 0 0 2 1 0
因此數字'5'的LIS為4,LDS為2，所以'5'為中心組成Wavio Sequence的長度就是min(4,2)*2+1=5。因此本題就從LIS和LDS表中找出最長的Wavio Seq長度。
至於求LDS我是由後面往前作LIS，因此這題就是做兩次LIS，另外要注意如果用O(n^2)演算法可能會TLE。

2014年3月20日星期四

UVa 437 The Tower of Babylon

題目：
LuckyCat中文翻譯
想法：
Longest Increased Subsequence題型，每種Block都有6種組合，所以每次讀入一組L,W,H，就存6種組合，等到全部讀完，就將全部的組合進行排序。因為我是打算將Block由小疊到大(做LIS，與題目相反)，所以排序方式就依L由小到大排，如果L一樣在依W排，然後就做LIS演算法。

UVa 836 Largest Submatrix

想法：
這題是2維MSS(minimum subarray sum)，基本上第一個for loop先選出submatrix的垂直邊長，第二個for loop選定這條邊起始位置，然後向右做MMS。

UVa 507 Jill Rides Again

Minimum Subarray Sum
想法：
這題求最大MSS值的區間，注意output說明，如果MSS一樣的話，要選擇最大的區間長度(j-i盡可能大)，如果區間長度又一樣長的話，那麼要選擇先出現的那個。

區間長度盡可能大：第18行要用">="
選擇最大區間長度：第24行的判斷式

UVa 231 Testing the CATCHER

Longest Decreased Subsequence
題意：
Ruby兔中文翻譯
想法：
由後往前用LIS。

UVa 111 History Sorting

題意：
Luckycat中文翻譯。
想法：
這題有個陷阱，以Sample input舉例：
10
3 1 2 4 9 5 10 6 8 7
4 7 2 3 10 6 9 1 5 8

由這行來看：3 1 2 4 9 5 10 6 8 7
"事件1在位置3"，"事件2在位置1"，"事件3在位置2"......"事件10在位置7"。

因此事件真正的排序是
10
2 3 1 4 6 8 10 9 5 7
8 3 4 1 9 6 2 10 7 5
然後再用LCS找出最大的長度。

2014年3月19日星期三

UVa 10684 The jackpot

Maximum Sub-array Sum
想法：
用DP做，設MSS為累加到目前的値，如果MSS是負的，那麼MSS=num，否則MSS+=num。

UVa 531 Compromise

Longest Common Subsequence題型
想法：
用pre[i][j]來記錄LCS[i][j]是從哪個方向來的，再從pre[N-1][M-1]開始逆向走回並保存答案。

POJ 2421 Constructing Roads

想法：
與POJ 1751是一樣的，先依題目將已連結的點連起來，剩下的再用Kruskal做最小生成樹，並累積最小生成樹的邊長和。

POJ 2395 Out of Way

想法：
這題與POJ 1861一模一樣，求最小生成樹的最大邊長而已。

POJ 1861 Network

題意&想法：
要找出最小生成樹MST，先輸出MST最長的邊長，再輸出MST有幾條邊(就是N-1)，然後在一一輸出這些邊的點。用Kruskal演算法找出MST，並依題輸出答案。
ps.這題Sample Output有誤，4個點只需要3條邊就可以產生MST。

POJ 2533 Longest Orderded Subsequence

Longest Increasing Sub-sequence(LIS)題目
想法：
這裡提供兩種方法：

把已經讀入的數字存起來，每次讀一個新的數字i的時候，就把LIS[i]設成1，然後把現在這個新數字i與以前已經讀入的數字j做比較，如果i比j大且LIS[i]<LIS[j]+1，就把LIS[i]=LIS[j]+1。最後輸出最大的LIS值即可。
與上面不同，LIS[]是存讀入的數字，一開始LIS[]是空的，慢慢放數字，每次讀入一個新的數字，從i=0，如果該數字>LIS[i]，就讓i++，直到在LIS表裡上不去為止，然後看該數字是否比LIS[i]小，如果是則更新LIS[i]的値。

POJ 1751 Highways

題意：
依序給你N個城市的座標，然後接下M行說明哪些城市已經相連，題目要求盡可能用最短的距離把所有的城市連起來。
想法：
先把兩兩城市的距離算出來，共有C(N,2)條邊長，將這些邊由小大到排序，然後做Kruskal演算法，將所有城市連起來。
原本49~53行原本我是打算如果總共已經做了(N-1)條邊就跳出for loop，但是WA，後來想想應該是測資給的已經存在的邊會形成一個環(cycle)，所以就不可能為最小生成樹，邊長總數會大於(N-1)條。

2014年3月17日星期一

POJ 1703 Find them, Catch them

想法：
Disjoint Set題目，開兩倍陣列Set[2*N]，然後Set[i]表示與i是同Set，Set[i+N]表示與i為敵人，初始化先將Set[i]=i, Set[i+N]=0，其他詳細看底下Code。

2014年3月16日星期日

UVa 11747 Heavy Cycle Edges

題意&想法：
本題就是要把多餘的邊去除掉使得該graph變成最小生成樹，因此我們可以用Kruskal直接做出最小生成樹，然後把沒有用到的邊由小到大輸出即可。

UVa 10369 Arctic Network

題意：
有S個衛星，以及P個城市，如果兩個城市都有衛星的話，那麼不管距離多遠都能通訊，否則就只能靠radio通訊，而靠radio通訊的最遠的兩個城市距離為D，現在求如果每個城市都要通訊的話，那麼D最小為多少?
以Sample Input舉例：
(0,300)~(0,600)=300之間，各使用一個satellite，透過satellite來溝通，(0,100)~(0,300)=200和(0,600)~(150,750)=212.13則使用radio，因此D至少要212.13

想法：
P個城市代表有(P-1)條邊，而用Kruskal演算法做出最小生成樹，做Kruskal的過程中將邊長記錄下來，共有(P-1)條，然後把其中最長的(S-1)條邊分配給衛星，剩下的邊的最大値就是D。

UVa 10034 Freckles

題意：
給你N個二維點座標，要找出把這N個點連在一起成一個Set的最短路徑
想法：
先將點與點兩兩之間的邊長先算出來並排序，然後用Kruskal演算法，找出最小生成樹，並在找的時候同時將邊長累加起來最後即是答案。

2014年3月11日星期二

淺談Backtracking演算法與其應用

一般遞迴是把所有可能的路徑走過，也就是一一把答案枚舉(列舉)出來，然後再檢查答案的是否正確，但一一枚舉會非常耗時，而且常常枚舉出來的數量遠多於所需要的答案，原因在於在遞迴進行到一半的時候，如果該路徑是錯的，還是會不斷往下繼續遞迴，但其實我們可以在發現這條路徑不可能為答案的時候，就不要再往下遞迴下去，這就是Backtracking演算法。

2014年3月10日星期一

POJ 1094 Sorting It All Out

題意：
給定N表示有N個點，M表示底下有M行關係式，然後一行一行讀取關係式：

如果在第i行發現已經能明確將所有點排出順序(也就是只有一種答案)，輸出Sorted sequence determined after i relations: ...(順序)
如果在第i行發現和之前的關係式有衝突(形成一個環，例如A>B>C>A)，則輸出Inconsistency found after i relations.
如果讀取到最後關係都沒有衝突但也找不到唯一答案，則輸出Sorted sequence cannot be determined.

想法：

每次讀取關係式的時候就檢查是否有衝突(形成一個環)，如果沒有再去找topological sort，topological sort這function裡面要判斷是否為唯一解，因此只能選一條路徑往下遞迴，最後判斷答案優先順序為1.先看有沒有衝突2.看有沒有解，再依題目敘述輸出即可，詳細看底下code。

POJ 2367 Genealogical tree

題意：
第一行N表示有N個數(編號1~N)，接下來N行每行有幾個數字，第i行表示數字i需要在第i行那些數前面，例如Sample Input的4 5 1 0表示數字2需要在4,5,1的前面，以數字0代表該行的終止。

想法：
建立graph，從起點(沒有其他點連入)開始用DFS走遍整個graph，並記下走過的順序，最後再逆向輸出就是一個topological sort。

UVa 872 Ordering

想法：
這題是backtracking內融合了topological sort，基本上就是第一格, 第二格, ....依序填入，每次填的時後判斷哪些node可以填(表示需要在該node前出現的node已經出現過了)，詳細見底下code。

2014年3月9日星期日

UVa 604 The Boggle Game

題意：
在一個4x4 board裡找出所有符合的4個字元的單字，該單字須符合剛好只有2個母音('Y'也算母音)，每次Case有兩個board，找出這兩個board交集的所有單字。

想法：
用DFS+backtracking先分別找出一個board的所有符合的單字，然後再將兩個board找出來的單字作交集：

UVa 193 Graph Coloring

題意：
黑色不能相鄰，白色則不限制，如果編號最大的點是黑色的，則稱這個填入方法為optimal。題目給定一個graph，求填入最多黑色的方法，如果有多個答案，則盡可能選擇optimal的那種。

想法：
MaxNum為填入最多黑色的點的數量，透過backtracking找出多種填入的方式，並不斷刷新MaxNum，並將該填法記錄下來，最後輸出最大MaxNum的填入方式，詳細見底下code。

UVa 10503 The dominoes solotarie

題意：

給定N表示起點和終點之間要填入N個骨牌，給定M表示除了起點和終點外還有M個骨牌，每個骨牌兩端高度不一樣，因此一個骨牌用(p,q)來表示其兩端的高度。在放骨牌的時候，其相鄰的骨牌連接的那端高度需一致(例如一段骨牌放置如(a,b),(b,c),(c,d),(d,e))。起點(i1,i2)和終點(d1,d2)這兩個骨牌的兩端是不能交換的(不能變成(i2,i1))，而其它M個骨牌在放入的時候兩端是能交換的，因此這題要確認是否能在(i1,i2)和(d1,d2)之間放入N個骨牌。

想法：

用backtracking確認是否能在起點和終點間放入N個骨牌。

	#include <cstdio>
	using namespace std;

	int N, M;
	int i1, i2, d1, d2, p[20], q[20];
	int choosed[20];

	bool backtracking(int Len, int num)
	{
	if (Len == N) {
	if (num == d1) return true;
	return false;
	}
	for (int i = 0; i < M; ++i) {
	if (choosed[i]) continue;
	if (p[i] == num \|\| q[i] == num) {
	choosed[i] = 1;

	bool ok;
	if (p[i] == num) ok = backtracking(Len + 1, q[i]);
	else ok = backtracking(Len + 1, p[i]);
	if (ok) return true;

	choosed[i] = 0;
	}
	}
	return false;
	}
	int main()
	{
	while (scanf("%d %d", &N, &M) && N) {
	scanf("%d %d %d %d", &i1, &i2, &d1, &d2);
	for (int i = 0; i < M; ++i) {
	scanf("%d %d", &p[i], &q[i]);
	choosed[i] = 0;
	}

	if (backtracking(0, i2)) puts("YES");
	else puts("NO");
	}
	return 0;
	}

view raw [UVa] 10503 The dominoes solitaire.cpp hosted with ❤ by GitHub

UVa 291 The House Of Santa Claus

想法：
這題的答案只從'1'當做起點，並將答案做遞增排序，用backtracking依序將答案找出。

	#include <cstdio>
	#include <vector>
	using namespace std;

	vector<int> toNxt[6] = {{}, {2,3,5}, {1,3,5}, {1,2,4,5}, {3,5}, {1,2,3,4}};
	bool choosed[6][6] = {0};
	int ans[9];

	void func(int n, int Len)
	{
	if (Len == 9) {
	for (int &a : ans)
	printf("%d", a);
	putchar('\n');
	}
	for (int nxt : toNxt[n]) {
	if (choosed[n][nxt] == 0 && choosed[nxt][n] == 0) {
	choosed[n][nxt] = 1, choosed[nxt][n] = 1;
	ans[Len] = nxt;

	func(nxt, Len + 1);

	choosed[n][nxt] = 0, choosed[nxt][n] = 0;
	}
	}
	}
	int main()
	{
	ans[0] = 1;
	func(1,1);
	}

	// Ans
	/*
	123153452
	123154352
	123451352
	123453152
	123513452
	123543152
	125134532
	125135432
	125315432
	125345132
	125431532
	125435132
	132153452
	132154352
	132534512
	132543512
	134512352
	134512532
	134521532
	134523512
	134532152
	134532512
	135123452
	135125432
	135215432
	135234512
	135432152
	135432512
	152134532
	152135432
	152345312
	152354312
	153123452
	153125432
	153213452
	153254312
	153452132
	153452312
	154312352
	154312532
	154321352
	154325312
	154352132
	154352312
	*/

view raw [UVa] 291 The House of Santa Claus.cpp hosted with ❤ by GitHub

UVa 598 Bundling Newspapers

題意：
參考Lucky Cat。
想法：
這題比較麻煩的部分在於輸入，輸入完成後就用backtracking把每個Size的答案找出來，詳細看底下code。

	#include <cstdio>
	#include <string>
	#include <map>
	#include <vector>
	using namespace std;

	int N;
	char News[15][40];
	int ans[20];
	bool choosed[20] = {0};

	int Input1(int &, int &);
	int Input2();
	void Combination(int &Size, int Len, int pos);

	int main()
	{
	int Case;
	scanf("%d ", &Case);

	while (Case--) {
	int a = 0, b = 0;
	int Mode = Input1(a, b);
	N = Input2();

	if (Mode == 1) b = a;
	else if (Mode == 3) a = 1, b = N;

	for (int i = a; i <= b; ++i) {
	printf("Size %d\n", i);
	Combination(i, 0, 0);
	putchar('\n');
	}
	if (Case) putchar('\n');
	}
	}
	int Input1(int &a, int &b)
	{
	char line[20];
	int Mode = 1;

	gets(line);

	if (line[0] == '*') Mode = 3;
	else {
	int i = 0;
	while (line[i] != '\0' && line[i] != ' ')
	a = a * 10 + (line[i++] - '0');
	if (line[i] == ' ') {
	Mode = 2, ++i;
	while (line[i])
	b = b * 10 + (line[i++] - '0');
	}
	}
	return Mode;
	}
	int Input2()
	{
	int n = 0;
	while (gets(News[n]) && News[n][0] != '\0') ++n;
	return n;
	}
	void Combination(int &Size, int Len, int pos)
	{
	if (Len == Size) {
	printf("%s", News[ans[0]]);
	for (int i = 1; i < Size; ++i)
	printf(", %s", News[ans[i]]);
	putchar('\n');
	return;
	}
	for (int i = pos; i < N; ++i) {
	ans[Len] = i;
	Combination(Size, Len + 1, i + 1);
	}
	}

view raw [UVa] 598 Bumdling Newspapers.cpp hosted with ❤ by GitHub

UVa 574 Sum It Up

想法：
用Backtracking找出所有答案(包括這些答案可能重複)，之後在將這些答案依照遞減排序，再輸出，輸出時要確定這個答案之前是否已經存在了。

	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;

	int T, N, List[20];
	vector<int> ans[10000];
	int nOfans;

	void backtracking(int pos, int sum)
	{
	if (sum == T) {
	ans[nOfans+1] = ans[nOfans];
	++nOfans;
	return;
	}
	for (int i = pos; i < N; ++i) {
	if (sum + List[i] <= T) {
	sum += List[i];
	ans[nOfans].push_back(List[i]);

	backtracking(i + 1, sum);

	sum -= List[i];
	ans[nOfans].pop_back();
	}
	}
	}
	bool cmp(vector<int> a, vector<int> b)
	{
	for (int i = 0; i < a.size(); ++i) {
	if (a[i] == b[i]) continue;
	return a[i] > b[i];
	}
	return a.size() > b.size();
	}
	void PrintOut(vector<int> &V)
	{
	printf("%d", V[0]);
	for (int i = 1; i < V.size(); ++i)
	printf("+%d", V[i]);
	printf("\n");
	}
	int main()
	{
	while (scanf("%d %d", &T, &N) && N) {
	for (int i = 0; i < N; ++i) {
	scanf("%d", &List[i]);
	}
	for (auto &v : ans) v.clear();
	nOfans = 0;

	backtracking(0, 0);

	printf("Sums of %d:\n", T);
	if (nOfans == 0)
	puts("NONE");
	else {
	sort(ans, ans + nOfans, cmp);
	PrintOut(ans[0]);
	for (int i = 1;i < nOfans; ++i)
	if (ans[i] != ans[i-1]) // 確認答案是否已經存在
	PrintOut(ans[i]);
	}
	}
	}

view raw [UVa] 574 Sum It Up.cpp hosted with ❤ by GitHub

UVa 524 Prime Ring Problem

想法：
用backtracking找出各種可能的組合方式，詳細看底下code：

	#include <cstdio>
	using namespace std;
	int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41};
	int N, Case = 0, ans[20] = {1};
	bool isPrime(int a)
	{
	for (int n : prime)
	if (n == a) return true;
	return false;
	}
	void backtracking(int L, bool visit[])
	{
	if (L == N) {
	if (!isPrime(ans[N-1] + 1)) // 確認頭+尾是否為質數
	return;
	printf("1");
	for (int i = 1; i < N; ++i)
	printf(" %d", ans[i]);
	printf("\n");
	return;
	}
	for (int i = 2; i <= N; ++i) {
	if (visit[i]) continue;
	if (isPrime(i + ans[L - 1])) {
	visit[i] = 1;
	ans[L] = i;

	backtracking(L + 1, visit);

	visit[i] = 0;
	}
	}
	}
	int main()
	{
	while (scanf("%d", &N) != EOF) {
	if (Case++) putchar('\n');
	printf("Case %d:\n", Case);
	bool visit[20] = {0};
	backtracking(1, visit);
	}
	}

view raw [UVa] 524 Prime Ring Problem.cpp hosted with ❤ by GitHub

UVa 11085 Back to the 8-Queens

想法：
先建表，把可能的位置存下來(共92種)，然後再看哪種位置所需要的Move數量最低。話說原本不知道Queen原來像象棋的車，移動一步可以任意距離，害我吃了WA@_@

	#include <cstdio>
	#include <vector>
	using namespace std;

	int Container[8];
	int Queens_row[100][8];
	int nOfQueens = 0;
	// col[i]表示該欄是否已經被選, 同理left表示左斜線, right表示右斜線
	bool row[8] = {0}, left[15] = {0}, right[15] = {0};
	// 底下 r表示row c表示colum
	void Eight_Queens(int c)
	{
	if (c == 8) {
	for (int i = 0; i < 8; ++i)
	Queens_row[nOfQueens][i] = Container[i] + 1; //+1是因為題目的row是從1開始
	++nOfQueens;
	return;
	}
	for (int r = 0; r < 8; ++r) {
	int ld = c - r + 7;
	int rd = c + r;
	if (!row[r] && !left[ld] && !right[rd]) {
	row[r] = 1, left[ld] = 1, right[rd] = 1;
	Container[c] = r;

	Eight_Queens(c + 1);

	row[r] = 0, left[ld] = 0, right[rd] = 0;
	}
	}
	}
	int main()
	{
	Eight_Queens(0);

	int row_position[8], Case = 1;

	while (scanf("%d", &row_position[0]) != EOF) {
	for (int i = 1; i < 8; ++i)
	scanf("%d", &row_position[i]);

	int Min = 99999;

	for (int i = 0; i < nOfQueens; ++i) {
	int Move = 0;
	for (int c = 0; c < 8; ++c)
	if (Queens_row[i][c] != row_position[c])
	++Move;
	if (Move < Min) Min = Move;
	}
	printf("Case %d: %d\n", Case++, Min);
	}
	}

view raw [UVa] 11085 Back to the 8-Queens.cpp hosted with ❤ by GitHub

UVa 624 CD

想法：
在小於等於限制的情況下一直遞迴找能放入的數字，並不斷刷新Maxsum(最接近限制的和)，詳細看底下。

	#include <cstdio>
	#include <vector>
	using namespace std;

	int track[21];
	int N, T; // T is number of tracks
	vector<int> Container; // 遞迴時暫存track
	vector<int> Ans;
	int Maxsum;
	void combination(int pos, int sum);

	int main()
	{
	while (scanf("%d %d", &N, &T) != EOF) {
	for (int i = 0; i < T; ++i)
	scanf("%d", &track[i]);
	Container.clear();

	Maxsum = 0;
	combination(0, 0);

	int sum = 0;
	for (int n : Ans) {
	printf("%d ", n);
	sum += n;
	}
	printf("sum:%d\n", sum);
	}
	}
	void combination(int pos, int sum)
	{
	if (sum > Maxsum) { // 不斷刷新Maxsum,使得Maxsum更接近N
	Ans = Container;
	Maxsum = sum;
	}

	for (int i = pos; i < T; ++i) {
	if (track[i] + sum <= N) {
	sum += track[i];
	Container.push_back(track[i]);

	combination(i + 1, sum);

	sum -= track[i];
	Container.pop_back();
	}
	}
	}

view raw [UVa] 624 CD.cpp hosted with ❤ by GitHub

UVa 989 Su Doku

想法：

每次要填入一個數字時，確認該行與該列和該九宮格(box)裡面是否已經有這個數字，如果能填入，則繼續遞迴下去填下一格。

	#include <cstdio>
	using namespace std;

	int board[9][9];
	int n, N; // n是較小的邊長, N = n * n
	bool backtracking(int r, int c);

	int main()
	{
	int Case = 0;
	while (scanf("%d", &n) != EOF) {
	if (Case++) putchar('\n');
	N = n * n;
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < N; ++j)
	scanf("%d", &board[i][j]);
	if (backtracking(0, 0)) {
	for (int i = 0; i < N; ++i) {
	for (int j = 0; j < N - 1; ++j)
	printf("%d ", board[i][j]);
	printf("%d\n", board[i][N-1]);
	}
	}
	else puts("NO SOLUTION");
	}
	}
	bool backtracking(int r, int c)
	{
	if (r >= N)
	return true;

	if (board[r][c] == 0) {
	bool col[10] = {0};
	bool row[10] = {0};
	bool box[10] = {0};
	//找出該欄與該列已經填過哪些數字
	for (int i = 0; i < N; ++i) {
	if (board[r][i]) row[board[r][i]] = 1;
	if (board[i][c]) col[board[i][c]] = 1;
	}
	//找出所在位置的九宮格裡已經填過哪些數字
	int rr = r - (r % n);
	int cc = c - (c % n);
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < n; ++j)
	if (board[rr+i][cc+j]) box[board[rr+i][cc+j]] = 1;
	//確認1~9哪些數字能填在這格,如果能填則繼續遞迴
	for (int num = 1; num <= 9; ++num) {
	if (!col[num] && !row[num] && !box[num]) {
	board[r][c] = num;

	int nxt_r = r, nxt_c = c + 1;
	if (nxt_c == N) ++nxt_r, nxt_c = 0; //換行
	bool hasAns = backtracking(nxt_r, nxt_c);
	if (hasAns) return true;

	board[r][c] = 0;
	}
	}
	}
	else { // board[r][c] != 0
	int nxt_r = r, nxt_c = c + 1;
	if (nxt_c == N) ++nxt_r, nxt_c = 0;
	bool hasAns = backtracking(nxt_r, nxt_c);
	if (hasAns) return true;
	}
	return false;
	}

view raw [UVa] 989 Su Doku.cpp hosted with ❤ by GitHub

2014年3月7日星期五

UVa 441 Lotto

想法：
排列組合中的組合，因此每次挑選的時候只能比之前挑的數字還要大，用遞迴做Backtraking，詳細見底下code:

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N, S[100], choosed[100], ans[100];
	void func(int len, int pos)
	{
	if (len == 6){
	for (int i = 0; i < 5; ++i)
	printf("%d ", ans[i]);
	printf("%d\n", ans[5]);
	return;
	}
	for (int i = pos; i < N; ++i) {
	if (!choosed[i]) {
	choosed[i] = 1;
	ans[len] = S[i];
	func(len+1, i + 1);
	choosed[i] = 0;
	}
	}
	}
	int main()
	{
	int Case = 0;
	while (scanf("%d", &N) && N) {
	if (Case++) printf("\n");
	for (int i = 0; i < N; ++i){
	scanf("%d", &S[i]);
	choosed[i] = 0;
	}
	func(0,0);
	}
	}

view raw [UVa] 441 Lotto.cpp hosted with ❤ by GitHub

UVa 167 The Sultan's Successors

想法：
這是一個八皇后問題，可以先將所有可能方式先記下來(共92種)，之後再輸入測資檢查這92種哪一種最大即可，如果還想更快的話，直接把這92種先輸出，然後直接寫在code裡XD。

	#include <cstdio>
	#include <vector>
	using namespace std;

	int P[1000][9];
	int tmp[8];
	int n = 0;
	// col[i]表示該欄是否已經被選, 同理left表示左斜線, right表示右斜線
	bool col[8] = {0}, left[15] = {0}, right[15] = {0};
	// 底下 r表示row c表示colum
	void func(int r)
	{
	if (r == 8) {
	for (int i = 0; i < 8; ++i)
	P[n][i] = tmp[i];
	++n;
	return;
	}
	for (int c = 0; c < 8; ++c) {
	int ld = (c - r) + 7;
	int rd = c + r;
	if (!col[c] && !left[ld] && !right[rd]) {
	col[c] = 1, left[ld] = 1, right[rd] = 1;
	tmp[r] = c;

	func(r + 1);

	col[c] = 0, left[ld] = 0, right[rd] = 0;
	}
	}
	}
	int main()
	{
	func(0);

	int Case;
	int board[8][8];
	scanf("%d", &Case);
	while (Case--) {
	for (int i = 0; i < 8; ++i)
	for (int j = 0; j < 8; ++j)
	scanf("%d", &board[i][j]);

	int ans = 0;

	for (int i = 0; i < n; ++i) {
	int sum = 0;
	for (int j = 0; j < 8; ++j)
	sum += board[j][P[i][j]];
	if (sum > ans) ans = sum;
	}
	printf("%5d\n", ans);
	}
	}

view raw UVa 167 The Sultan's Successors.cpp hosted with ❤ by GitHub

UVa 10305 Ordering Tasks

想法：
輸出只要符合是一個topological sort即可，因此可以從起點(沒有被任何點連入的點)用DFS走遍，並同時記錄走遍的點，最後再逆向輸出這些點就是一個topological sort。

	#include <cstdio>
	#include <vector>
	using namespace std;
	void DFS(int n, int visit[], vector<int> toNode[], vector<int> &ans);
	int main()
	{
	int N, M, a, b;
	while (scanf("%d %d", &N, &M) && (N \|\| M)) {
	vector<int> toNode[101];
	vector<int> ans;
	bool connect[101] = {0};
	int visit[101] = {0};
	while (M--) {
	scanf("%d %d", &a, &b);
	toNode[a].push_back(b);
	connect[b] = 1;
	}
	for (int i = 1; i <= N; ++i) {
	if (!connect[i])
	DFS(i ,visit, toNode, ans);
	}
	for (auto iter = ans.end() - 1; iter != ans.begin(); --iter)
	printf("%d ", *iter);
	printf("%d\n", *ans.begin());
	}
	}
	void DFS(int n, int visit[],vector<int> toNode[], vector<int> &ans)
	{
	if (visit[n] == 1) return;
	visit[n] = 1;

	for (int nxt : toNode[n]) {
	if (visit[nxt] != 2)
	DFS(nxt, visit, toNode, ans);
	}
	visit[n] = 2;
	ans.push_back(n);
	}

view raw [UVa] 10305 Ordering Tasks.cpp hosted with ❤ by GitHub

UVa 11606 Pick up sticks

想法：

把放在最上面(也就是這個點沒有其他點連入)的stick當做起點，用DFS走遍，並將走遍的經過的點記錄下來，最後逆向輸出這些記錄的點就是一個topological sort。

	#include <iostream>
	#include <cstdio>
	#include <string>
	#include <vector>
	using namespace std;

	vector<char> ans;
	vector<char> toPoint[100];
	int visit[100] = {0};
	int deg[100] = {0}; // deg[i]=1:沒有被其他點連入 deg[i]=2:被其他點連入
	void DFS(char n);

	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	string a, b;
	cin >> a;
	while (cin >> b && b != "#") {
	int L = (a.size() > b.size()) ? b.size() : a.size();
	for (int i = 0; i < L; ++i) {
	if (deg[a[i]] == 0) deg[a[i]] = 1;
	if (deg[b[i]] == 0) deg[b[i]] = 1;
	if (b[i] != a[i]) {
	toPoint[a[i]].push_back(b[i]);
	deg[b[i]] = 2;
	break;
	}
	}
	a = b;
	}
	for (char i = 'A'; i <= 'Z'; ++i)
	if (deg[i] == 1)
	DFS(i);

	for (auto iter = ans.rbegin(); iter != ans.rend(); ++iter)
	cout << *iter;
	cout << endl;
	}
	void DFS(char n)
	{
	if (visit[n] == 1) return;
	visit[n] = 1;

	for (char nxt : toPoint[n])
	if (visit[nxt] != 2)
	DFS(nxt);
	visit[n] = 2;
	ans.push_back(n);
	}

view raw [UVa] 200 Rare Order.cpp hosted with ❤ by GitHub

UVa 200 Rare Order

題意：
　　Input給的那些字串是每個index的名稱，而這些Index是照"某個字典序"由小到大排好的(就像一般的目錄是從A~Z排好)，我們要從Input裡面判斷這些字的字典序。例如Sample Input：
XWY
ZX
ZXY
ZXW
YWWX
我們可以從XWY和ZX判斷X<Z，ZXY和ZXW判斷Y<W，ZXW和YWWX判斷Z<Y，所以可以得到X<Z<Y<W。

**本題測資只有一個**

想法：
　　一次兩行判斷，找出誰<誰，記錄完之後，從沒有被連入的點當做起點，使用DFS走遍並記下走遍的點，將記下的點逆向輸出就是一個topological sort。

	#include <iostream>
	#include <cstdio>
	#include <string>
	#include <vector>
	using namespace std;

	vector<char> ans;
	vector<char> toPoint[100];
	int visit[100] = {0};
	int deg[100] = {0}; // deg[i]=1:沒有被其他點連入 deg[i]=2:被其他點連入
	void DFS(char n);

	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	string a, b;
	cin >> a;
	while (cin >> b && b != "#") {
	int L = (a.size() > b.size()) ? b.size() : a.size();
	for (int i = 0; i < L; ++i) {
	if (deg[a[i]] == 0) deg[a[i]] = 1;
	if (deg[b[i]] == 0) deg[b[i]] = 1;
	if (b[i] != a[i]) {
	toPoint[a[i]].push_back(b[i]);
	deg[b[i]] = 2;
	break;
	}
	}
	a = b;
	}
	for (char i = 'A'; i <= 'Z'; ++i)
	if (deg[i] == 1)
	DFS(i);

	for (auto iter = ans.rbegin(); iter != ans.rend(); ++iter)
	cout << *iter;
	cout << endl;
	}
	void DFS(char n)
	{
	if (visit[n] == 1) return;
	visit[n] = 1;

	for (char nxt : toPoint[n])
	if (visit[nxt] != 2)
	DFS(nxt);
	visit[n] = 2;
	ans.push_back(n);
	}

view raw [UVa] 200 Rare Order.cpp hosted with ❤ by GitHub

UVa 11060 Becerages

想法：
　　記錄每個點被其他點連入的數量(Ex: A->B, C->B，則beConnected[B]=2)，和記錄各個點連到哪些點。

每次從頭找beConnected[i]==0(表示沒有點連到i)的Node
將這個Node輸出
同時將beConnected[i]改成-1表示這Node已經輸出過了
然後其他每個被Node i連入的Node j，把beConnected[j]--
執行1~4 N次，把每個Node都輸出過

	#include <iostream>
	#include <string>
	#include <map>
	#include <vector>
	using namespace std;

	map<string, int> Map;
	string Name[105];
	vector<int> toNxt[105];
	int beConnected[105]; //該node被其他點連入的數量

	void Initial(int N)
	{
	Map.clear();
	for (int i = 0; i < N; ++i) {
	toNxt[i].clear();
	beConnected[i] = 0;
	}
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	int N, M, Case = 1;
	string s1, s2;
	while (cin >> N) {
	Initial(N);
	for (int i = 0; i < N; ++i)
	cin >> s1, Map[s1] = i, Name[i] = s1;

	cin >> M;
	for (int i = 0; i < M; ++i) {
	cin >> s1 >> s2;
	toNxt[Map[s1]].push_back(Map[s2]);
	++beConnected[Map[s2]];
	}
	cout << "Case #" << Case++ << ": Dilbert should drink beverages in this order:";
	for (int i = 0; i < N; ++i) {
	int pos = 0;
	while (beConnected[pos] != 0) ++pos;

	beConnected[pos] = -1;
	cout << ' ' << Name[pos];

	for (int nxt : toNxt[pos])
	--beConnected[nxt];
	}
	cout << '.' << endl << endl;
	}
	}

view raw [UVa] 11060 Beverages.cpp hosted with ❤ by GitHub

POJ 2442 Sequence

想法：
　　這題與UVa 11997一樣，差別只在於UVa那題是K行K個數字，這題是M行N個數字，詳細過程我寫在UVa 11997 K Smallest Sums。

	#include <cstdio>
	#include <algorithm>
	#include <queue>
	using namespace std;
	struct custom_type {
	int val;
	int pos;

	bool operator < (const custom_type &B) const {
	return val > B.val; // min heap
	}
	};
	int main()
	{
	int T ,M, N, L1[2001], L2[2001];
	scanf("%d", &T);
	while (T--) {
	scanf("%d %d", &M, &N);
	for (int i = 0; i < N; ++i) scanf("%d", &L1[i]);
	sort(L1, L1 + N);

	for (int k = 1; k < M; ++k) {
	for (int i = 0; i < N; ++i) scanf("%d", &L2[i]);
	sort(L2, L2 + N);

	priority_queue<custom_type> PQ;
	for (int i = 0; i < N; ++i)
	PQ.push({L1[i] + L2[0], 0});

	for (int i = 0; i < N; ++i) {
	custom_type tmp = PQ.top();
	PQ.pop();
	L1[i] = tmp.val;
	if (tmp.pos+1 < N)
	PQ.push({tmp.val - L2[tmp.pos] + L2[tmp.pos+1], tmp.pos + 1});
	}
	}
	for (int i = 0; i < N - 1; ++i)
	printf("%d ", L1[i]);
	printf("%d\n", L1[N-1]);
	}
	}

view raw [POJ] 2442 Sequence.cpp hosted with ❤ by GitHub

UVa 11997 K Smallest Sums

題意：
有K行，每行有K個數字，從每行裡面各選出1個數字並加起來共有K^K種組合的和，輸出最小的K個和。

想法：
我們可以先將第一行和第二行求出前K小的和，因此兩行數字就變成了一行數字，這一行數字再和第三行求出前K小的和，兩行又合併成一行，一直重複將兩行合併成一行，最後就是答案。
因此現在關鍵是如何有效率求出兩行的數字前K個最小的和，如果暴力解的話為O(K^2)，很可能會TLE，用priority queue來解這題只要O(K)，過程如下：
*假設第一行數字陣列為L1，第二行數字陣列為L2，
*要丟進priority queue(底下簡稱PQ)裡的structure裡面含有兩個元素，第一個為val: 表示L1某個數+L2某個數的和，第二個為pos: 表示L2某個數在L2的位置(index)。

將L1遞增排序
將L2遞增排序。
然後把L1裡面每個數字和L2[0]加起來，val=L1[i]+L2[0]和pos=0放到PQ裡面。
L1的數字就不會用到了
之後每次從PQ裡面拿出第一個(最小的val)，將這個val放入L1(覆蓋以重複利用L1)，然後將這個val=(val-L2[pos]+L2[pos+1])和pos=pos+1丟回PQ裡
重複步驟5 K次，L1裡面就有K個數字，表示這兩行已經合併成功
讀入下一個L2，並重複步驟2~7，直到將K行合併成一行
輸出L1

用這方法將兩行合併成一行的時候，只要做K次即可，因為我們已經將L1都丟進PQ裡面，然後每次都選最小和出來，並同時把可能的答案丟入PQ。

	#include <cstdio>
	#include <algorithm>
	#include <queue>
	using namespace std;
	struct custom_type {
	int val;
	int pos;

	bool operator < (const custom_type &B) const {
	return val > B.val; // min heap
	}
	};
	int main()
	{
	int K, L1[800], L2[800];
	while (scanf("%d", &K) != EOF) {
	for (int i = 0; i < K; ++i) scanf("%d", &L1[i]);
	sort(L1, L1 + K);

	for (int k = 1; k < K; ++k) {
	for (int i = 0; i < K; ++i) scanf("%d", &L2[i]);
	sort(L2, L2 + K);

	priority_queue<custom_type> PQ;
	for (int i = 0; i < K; ++i)
	PQ.push({L1[i] + L2[0], 0});

	for (int i = 0; i < K; ++i) {
	custom_type tmp = PQ.top();
	PQ.pop();
	L1[i] = tmp.val;
	if (tmp.pos+1 < K)
	PQ.push({tmp.val - L2[tmp.pos] + L2[tmp.pos+1], tmp.pos + 1});
	}
	}
	for (int i = 0; i < K - 1; ++i)
	printf("%d ", L1[i]);
	printf("%d\n", L1[K-1]);
	}
	}

view raw [UVa] 11997 K Smallest Sums.cpp hosted with ❤ by GitHub

2014年3月5日星期三

POJ 2255 Tree Recovery

想法：
　　原本的字串是整棵Tree，我們可先找到這個Tree的Root，再將其分為左右Sub Tree，一直遞迴下去直到Sub Tree只剩一個元素。
　　具體做法是：

先用Preorder String找出Root(P_root)，再透過P_root找到Inorder String的Root(I_root)
然後用I_root分別找出左右Sub Tree在Inorder String的左右界(會有4個index：左子樹的左右界和右子樹的左右界)，再用剛才4個index的結果來找出左右子樹在Preoder String的左右界(一樣有4個index)。
依照Post Order的順序：

先遞迴左子樹
再遞迴右子樹
輸出Root

底下有附詳細註解的Code：

	#include <cstdio>
	#include <cstring>
	using namespace std;

	char Preorder[30], Inorder[30];

	void Postorder(int PL, int PR, int IL, int IR);
	int FindInorderRoot(char c, int L, int R);

	int main()
	{
	while (scanf("%s %s", Preorder, Inorder) == 2) {
	Postorder(0, strlen(Preorder)-1, 0, strlen(Inorder)-1);
	putchar('\n');
	}
	return 0;
	}
	void Postorder(int PL, int PR, int IL, int IR) // PL, PR: Preorder的左右界 IL, IR: Inorder的左右界
	{
	if (PL == PR) { // 左界等於右界,
	printf("%c", Preorder[PL]);
	return;
	}
	// P_root, I_root: 目前這個Tree的root的index
	int P_root = PL;
	int I_root = FindInorderRoot(Preorder[P_root], IL, IR);

	// 要分成左右子樹, P_Lsub_L, P_Lsub_R: 為左子樹在Preorder的左右界,反之另外兩個為右子樹左右界
	int P_Lsub_L, P_Lsub_R, P_Rsub_L, P_Rsub_R;

	// I_Lsub_L, I_Lsub_R: 為左子樹在Inorder的左右界,另外兩個為右子樹的左右界
	int I_Lsub_L, I_Lsub_R, I_Rsub_L, I_Rsub_R;

	bool hasLsub = 1, hasRsub = 1; //確認左右子樹是否存在

	I_Lsub_L = IL;
	I_Lsub_R = I_root - 1;
	if (I_Lsub_L > I_Lsub_R) hasLsub = 0;

	I_Rsub_L = I_root + 1;
	I_Rsub_R = IR;
	if (I_Rsub_L > I_Rsub_R) hasRsub = 0;

	if (hasLsub) {
	P_Lsub_L = P_root + 1;
	P_Lsub_R = P_Lsub_L + (I_Lsub_R - I_Lsub_L);
	}
	if (hasRsub) {
	P_Rsub_L = (hasLsub) ? P_Lsub_R + 1 : P_root + 1;
	P_Rsub_R = PR;
	}

	//若左(右)子樹存在,則繼續遞迴分割,直到元素剩下一個
	//底下三行code的順序為Postorder(Left, Right, Root)
	if (hasLsub) Postorder(P_Lsub_L, P_Lsub_R, I_Lsub_L, I_Lsub_R);
	if (hasRsub) Postorder(P_Rsub_L, P_Rsub_R, I_Rsub_L, I_Rsub_R);
	printf("%c", Preorder[P_root]);
	}
	int FindInorderRoot(char c, int L, int R)
	{
	while (Inorder[L] != c && L <= R) L++;
	return L;
	}

view raw [POJ] 2255 Tree Recovery.cpp hosted with ❤ by GitHub

2014年3月4日星期二

UVa 11987 Almost Union-Find

想法：

int Root[] : 表示i這個點存放在哪個Set(也就是Set[Root[i]]裡面可以找到i這個數字)
vector<int> Set[] : 每個Set裡面可以存放很多數字

分成三個操作：

Union：如果x和y不在同個Set，那就把元素個數較少的那個Set裡面的每個元素移動到另一個Set，並同時將Root[]重新指向。例如Set[Root[y]]元素較少，就把Set[Root[y]]內的元素加入到Set[Root[x]]，並且把Set[Root[y]]的元素n，使得Root[n]=Root[x]。
Move：如果x和y不在同個Set，就把Set[Root[x]]這個Set內的元素x刪除，並在Set[Root[y]]加入x，記得將Root[x] = Root[y]。
Output：輸出Set[Root[x]].size()和該Set內每個元素的和。

	#include <cstdio>
	#include <vector>
	using namespace std;

	int Root[100010];
	vector<int> Set[100010];

	void Set_Initial(int N);
	void Union(int x, int y);

	int main()
	{
	int N, M, Command;
	int x , y;
	while (scanf("%d %d", &N, &M) != EOF) {
	Set_Initial(N);
	while (M--) {
	scanf("%d", &Command);
	if (Command == 1) {
	scanf("%d %d", &x, &y);
	Union(x, y);
	}
	else if (Command == 2) {
	scanf("%d %d", &x, &y);
	if (Root[x] == Root[y]) continue;

	auto iter = Set[Root[x]].begin();
	while (*iter != x) ++iter;
	Set[Root[x]].erase(iter);

	Set[Root[y]].push_back(x);
	Root[x] = Root[y];
	}
	else if (Command == 3) {
	scanf("%d", &x);
	int Sum = 0;
	for (int &n : Set[Root[x]])
	Sum += n;
	printf("%d %d\n", Set[Root[x]].size(), Sum);
	}
	}
	}
	}
	void Set_Initial(int N)
	{
	for (int i = 1; i <= N; ++i) {
	Root[i] = i;
	Set[i].clear();
	Set[i].push_back(i);
	}
	}
	void Union(int x, int y)
	{
	x = Root[x];
	y = Root[y];
	if (x == y) return;

	if (Set[x].size() >= Set[y].size()) {
	for (int &n : Set[y]) {
	Set[x].push_back(n);
	Root[n] = x;
	}
	Set[y].clear();
	}
	else {
	for (int &n : Set[x]) {
	Set[y].push_back(n);
	Root[n] = y;
	}
	Set[x].clear();
	}
	}

view raw [UVa] 11987 Almost Union-Find.cpp hosted with ❤ by GitHub

UVa 11503 Virtual Friends

想法：
　　架構與UVa 10685 Nature一樣，差別在於這題每輸入一組測資就要把該組測資所在的Set的大小輸出。

	#include <iostream>
	#include <map>
	#include <string>
	using namespace std;

	int Set[200010];
	int Num[200010];

	void Set_Initial(int N);
	int FindRoot(int x);
	void Union(int x, int y);

	int main()
	{
	ios::sync_with_stdio(false);
	int Case, F;
	cin >> Case;
	while (Case--) {
	cin >> F;
	map<string, int> Map;
	Set_Initial(2 * F);

	string A, B;
	for (int i = 0, j = 1; i < F; ++i) {
	cin >> A >> B;
	if (!Map[A]) Map[A] = j++;
	if (!Map[B]) Map[B] = j++;
	Union(Map[A], Map[B]);
	}
	}
	}
	void Set_Initial(int N)
	{
	for (int i = 0; i <= N; ++i) {
	Set[i] = i;
	Num[i] = 1;
	}
	}
	int FindRoot(int x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = FindRoot(Set[x]);
	}
	void Union(int x, int y)
	{
	x = FindRoot(x);
	y = FindRoot(y);

	if (x != y) {
	Set[x] = y;
	Num[y] += Num[x];
	}
	cout << Num[y] << endl;
	}

view raw [UVa] 11503 Virtual Friends.cpp hosted with ❤ by GitHub

UVa 10685 Nature

想法：

Set[i]表示i這個node的father node(上面一層node的編號)，Root這個node的father node還是自己。
Num[i]表示以i這個node為root的set，有幾個元素

這題與UVa 10608 Friends是一樣的，差別在於這題給的input為字串，因此我們先用map將它轉成數字編號。

	#include <iostream>
	#include <map>
	#include <string>
	using namespace std;

	map<string, int> Map;
	int Set[5010];
	int Num[5010];

	void Set_Initial(int N);
	int FindRoot(int x);
	void Union(int x, int y);
	int FindLargest(int N);

	int main()
	{
	ios::sync_with_stdio(false);
	int C, R;
	while (cin >> C >> R) {
	if (!C && !R) break;

	Set_Initial(C);

	string A, B;
	for (int i = 0; i < C; ++i) {
	cin >> A;
	Map[A] = i;
	}
	while (R--) {
	cin >> A >> B;
	Union(Map[A], Map[B]);
	}
	cout << FindLargest(C) << endl;
	}
	}
	void Set_Initial(int N)
	{
	Map.clear();
	for (int i = 0; i < N; ++i) {
	Set[i] = i;
	Num[i] = 1;
	}
	}
	int FindRoot(int x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = FindRoot(Set[x]);
	}
	void Union(int x, int y)
	{
	x = FindRoot(x);
	y = FindRoot(y);

	if (x != y) {
	Set[x] = y;
	Num[y] += Num[x];
	}
	}
	int FindLargest(int N)
	{
	int Max = 0;
	for (int i = 0; i < N; ++i)
	if (Num[i] > Max) Max = Num[i];
	return Max;
	}

view raw [UVa] 10685 Nature.cpp hosted with ❤ by GitHub

UVa 10608 Friends

想法：
　　做Disjoint Set，詳細看底下Code~。

	#include <cstdio>
	using namespace std;

	int Set[30010]; // Set[i]為i這node的father node,Set最上層的Set[root]=root
	int Num[30010]; // 以N[i]為root的Set有幾個element

	void Set_Initial(int N);
	int FindRoot(int x);
	void Union(int x, int y);
	int FindLargest(int N);

	int main()
	{
	int Case, N, M, A, B;
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d %d", &N, &M);
	Set_Initial(N);
	while (M--) {
	scanf("%d %d", &A, &B);
	Union(A, B);
	}
	printf("%d\n", FindLargest(N));
	}
	}
	void Set_Initial(int N)
	{
	for (int i = 1; i <= N; ++i) {
	Set[i] = i;
	Num[i] = 1;
	}
	}
	int FindRoot(int x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = FindRoot(Set[x]);
	}
	void Union(int x, int y)
	{
	x = FindRoot(x);
	y = FindRoot(y);

	if (x != y) {
	Set[x] = y;
	Num[y] += Num[x];
	}
	}
	int FindLargest(int N)
	{
	int Max = 0;
	for (int i = 1; i <= N; ++i)
	if (Num[i] > Max)
	Max = Num[i];
	return Max;
	}

view raw [UVa] 10608 Friends.cpp hosted with ❤ by GitHub

UVa 10583 Ubiquitous Religions

做disjoint set，架構與UVa 793 Network Connections一樣。

	#include <cstdio>
	#include <set>
	using namespace std;

	int Set[50010];
	int nOfReligion;

	void Set_Initial(int N);
	int FindRoot(int x);
	void Union(int x, int y);

	int main()
	{
	int N, M, Case = 1;
	while (scanf("%d %d", &N, &M) && (N \|\| M)) {

	Set_Initial(N);
	int x, y;
	nOfReligion = N;

	while (M--) {
	scanf("%d%d", &x, &y);
	Union(x, y);
	}
	printf("Case %d: %d\n", Case++, nOfReligion);
	}
	return 0;
	}
	void Set_Initial(int N)
	{
	for (int i = 1; i <= N; ++i)
	Set[i] = i;
	}
	int FindRoot(int x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = FindRoot(Set[x]);
	}
	void Union(int x, int y)
	{
	x = FindRoot(x);
	y = FindRoot(y);

	if (x != y) {
	Set[x] = y;
	--nOfReligion;
	}
	}

view raw [UVa] 10583 Ubiquitous Religions.cpp hosted with ❤ by GitHub

2014年3月3日星期一

UVa 879 Circuit Nets

想法：
　　與UVa 793 Network Connections一樣，依題意做disjoint set，排名拿到Rank 2，可能這題做的人少吧XD

	#include <cstdio>
	using namespace std;
	int Set[100001];
	int nOfNets;

	int getNum(char line[], int &i);
	void MakeSet(int n);
	int FindSetRoot(int x);
	void Union(int x, int y);

	int main()
	{
	int Case, N;
	char line[1000];
	scanf("%d", &Case);

	while (Case--) {
	scanf("%d ", &N);

	MakeSet(N);
	nOfNets = N;

	while (gets(line)) {
	if (line[0] == '\0') break;

	for (int i = 0; line[i];) {
	int X = getNum(line, i);
	int Y = getNum(line, i);
	Union(X, Y);
	}
	}
	printf("%d\n", nOfNets);
	if (Case) putchar('\n');
	}
	}
	int getNum(char line[], int &i)
	{
	int n = 0;
	while (line[i] != ' ' && line[i] != '\0') {
	n = n * 10 + (line[i] - '0');
	++i;
	}
	while (line[i] == ' ' && line[i] != '\0') ++i;
	return n;
	}
	void MakeSet(int n)
	{
	for (int i = 1; i <= n; ++i)
	Set[i] = i;
	}
	int FindSetRoot(int x)
	{
	if (Set[x] == x)
	return x;
	return Set[x] = FindSetRoot(Set[x]);
	}
	void Union(int X, int Y)
	{
	X = FindSetRoot(X);
	Y = FindSetRoot(Y);
	if (X != Y){
	Set[X] = Y;
	--nOfNets;
	}
	}

view raw [UVa] 879 Circuit Nets.cpp hosted with ❤ by GitHub

UVa 793 Network Connections

想法：
　　建disjoint set，把連在一起的電腦放在同一個Set，在判斷兩台電腦是否在同一個Set。具體做法是，

一開始每台電腦都是一個Set(同時該Set的root就是該台電腦編號)
然後要合併兩個Set就先各別找到它們的Root，再從一邊的Root連到另一邊的Root合併成一個Set
要判斷兩台電腦是否在同一個Set也是分別找Root，如果Root一樣表示這兩台電腦在同一個Set。

	#include <cstdio>
	using namespace std;

	int Set[1000001]; // Set[i]= x, x表示i的father, 最上層root的father還是自己

	void MakeSet(int n);
	int FindSetRoot(int x);
	void Union(int x, int y);

	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case, C;
	char line[100];
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d ", &C);

	MakeSet(C);

	char Type;
	int A, B;
	int nOfSuccess = 0, nOfUnSuccess = 0;

	while (gets(line)) {
	if (line[0] == '\0') break;
	sscanf(line, "%c %d %d", &Type, &A, &B);

	if (Type == 'c') {
	Union(A,B);
	}
	else {
	if (FindSetRoot(A) == FindSetRoot(B)) //如果同一個root表示在同一個Set
	++nOfSuccess;
	else
	++nOfUnSuccess;
	}
	}
	printf("%d,%d\n", nOfSuccess, nOfUnSuccess);
	if (Case) putchar('\n');
	}
	return 0;
	}
	void MakeSet(int n) // 一開始每個數字都是一個set,自己就是root
	{
	for (int i = 0; i <= n; ++i)
	Set[i] = i;
	}
	int FindSetRoot(int x) // 一直往上找到root
	{
	if (Set[x] == x)
	return x;
	return Set[x] = FindSetRoot(Set[x]); // 前面等號賦値的用意是讓Set深度不要太深
	} // 加速之後尋找速度
	void Union(int x, int y) //將x所屬的Set和y所屬的Set合併成一個Set
	{
	x = FindSetRoot(x);
	y = FindSetRoot(y);

	if (x != y) {
	Set[y] = x;
	}
	}

view raw [UVa] 793 Network Connections.cpp hosted with ❤ by GitHub

POJ 3253 Fence Repair

想法：
　　題目雖然說是砍斷，但其實可以想成一塊一塊拼回來，兩塊兩塊拼成的長度就是收取的費用，這題跟 UVa 10954 Add All 做法一樣，用priority_queue。

	#include <cstdio>
	#include <queue>
	using namespace std;
	typedef long long int llt;
	int main()
	{
	llt N, L;
	while (scanf("%lld", &N) != EOF) {
	priority_queue<llt, vector<llt>, greater<llt> > PQ;
	for (llt i = 0; i < N; ++i) {
	scanf("%lld", &L);
	PQ.push(L);
	}
	llt sum = 0;
	while (PQ.size() > 1) {
	llt tmp = PQ.top();
	PQ.pop();
	tmp += PQ.top();
	PQ.pop();

	sum += tmp;
	PQ.push(tmp);
	}
	printf("%lld\n", sum);
	}
	return 0;
	}

view raw [POJ] 3253 Fence Repair.cpp hosted with ❤ by GitHub

2014年3月2日星期日

POJ 2431 Expedition

題意：
　　一群牛從起點要出發到城鎮(目的地)距離共L單位，每走一單位同時消耗一單位的油，一開始油箱有P單位的油量，路途中會經過幾個加油站，每個加油站會給兩個數字，1.距離城鎮多少單位，2.這個加油站能加多少油，本題問到目的最少要到幾個加油站加油，如果不可能到達目的地則輸出-1。

想法：
　　因為所有地點都在同一直線上，所以都會經過每個加油站，只是看要不要停下來加油而已。所以我們就盡可能往前走，把每個路過加油站的該站的加油量放到priority queue裡面，然後直到走到途中沒油了，就從priority queue裡面拿出第一個(最大的加油量)加到自己的油箱，因為既然要加油，就要一次加最多的油，一直反覆這個動作直到終點。

	#include <cstdio>
	#include <algorithm>
	#include <queue>
	using namespace std;
	struct fuel_stop{
	int pos;
	int amount;
	}stop[10010];
	bool cmp(fuel_stop a, fuel_stop b)
	{
	return a.pos > b.pos;
	}
	int main()
	{
	int N, L, P;
	while (scanf("%d", &N) != EOF) {
	for (int i = 0; i < N; ++i)
	scanf("%d %d", &stop[i].pos, &stop[i].amount);
	scanf("%d %d", &L, &P);

	sort(stop, stop + N, cmp);

	stop[N] = {0,0}; // 終點也當一個stop
	priority_queue<int> PQ; // PQ用來裝每個stop的油量

	int dis = L - stop[0].pos; // 起點~第一站
	int sum_dis = dis; // 總共已經走了多遠
	P -= dis;

	int i = 0; // i用來當index
	int ans = 0;
	bool OK = 1;
	while (sum_dis < L && OK) {
	while (P >= 0) { //當身上油還>=0時繼續前進
	dis = stop[i].pos - stop[i+1].pos;
	P -= dis;
	sum_dis += dis;
	PQ.push(stop[i].amount);
	++i;
	if (i == N) break;
	}
	while (P < 0 && OK) { // PQ裡面從最多油量開始挑,加入油箱
	if (PQ.empty()) OK = 0;
	else{
	P += PQ.top();
	PQ.pop();
	++ans;
	}
	}
	}
	if (OK) printf("%d\n", ans);
	else puts("-1");
	}
	}

view raw [POJ] 2431 Expedition.cpp hosted with ❤ by GitHub

UVa 12347 Binary Search Tree

想法：
真的直接造出一棵樹來~

	#include <cstdio>
	using namespace std;
	struct Tree{
	int val = 0;
	Tree *L = nullptr;
	Tree *R = nullptr;
	};
	Tree Insert(Tree H, int node)
	{
	Tree *N = new Tree;
	N->val = node;

	if (H == nullptr) return N;

	Tree T = H, nxt = H;
	while (nxt != nullptr) {
	T = nxt;
	if (node > nxt->val) nxt = nxt->R;
	else nxt = nxt->L;
	}
	if (node > T->val) T->R = N;
	else T->L = N;
	return H;
	}
	void Post_Order(Tree *Root)
	{
	if (Root == nullptr) return;
	Post_Order(Root->L);
	Post_Order(Root->R);
	printf("%d\n", Root->val);
	}
	int main()
	{
	Tree *head = nullptr;
	int node;
	while (scanf("%d", &node) != EOF)
	head = Insert(head,node);
	Post_Order(head);
	return 0;
	}

view raw [UVa] 12347 Binary Search Tree.cpp hosted with ❤ by GitHub

2014年3月1日星期六

UVa 11995 I Can Guess the Data Structure

想法：

既然C++提供STL了，那就直接拿來用，模擬實際情況，但取値或pop()的時候要注意該Container是否為empty，否則會Runtime Error。

	#include <cstdio>
	#include <stack>
	#include <queue>
	using namespace std;
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int N, Command, num;
	while (scanf("%d", &N) != EOF) {
	stack<int> S;
	queue<int> Q;
	priority_queue<int> PQ;
	bool isStack = 1, isQueue = 1, isPriQueue = 1;

	while (N--) {
	scanf("%d%d", &Command, &num);
	if (Command == 1) {
	S.push(num);
	Q.push(num);
	PQ.push(num);
	}
	else {
	if (S.empty() \|\| S.top() != num) isStack = 0;
	if (Q.empty() \|\| Q.front() != num) isQueue = 0;
	if (PQ.empty() \|\| PQ.top() != num) isPriQueue = 0;
	if (!S.empty()) S.pop();
	if (!Q.empty()) Q.pop();
	if (!PQ.empty()) PQ.pop();
	}
	}
	if (isStack + isQueue + isPriQueue > 1)
	puts("not sure");
	else if (isStack) puts("stack");
	else if (isQueue) puts("queue");
	else if (isPriQueue) puts("priority queue");
	else puts("impossible");
	}
	return 0;
	}

view raw [UVa] 11995 I Can Guess the Data Structure.cpp hosted with ❤ by GitHub

UVa 10821 Constructing BST

想法：
在最上層的時候，假設我們有數列{1,2,3,4,5,6,7}，要選出一個數字當作該層的root，例如選擇'4'，那麼{1,2,3}就被分配到左子樹，{4,5,6}到右子樹，到下一層我們一樣從{1,2,3}和{4,5,6}選出各自的root，然後繼續到下一層。
但題目有說輸出要盡可能小，所以選擇root的時候，要盡可能選靠左邊的數字，所以要讓右子樹填滿，例如現在最上層數列為{1,2,3,4,5,6}，深度H=3，代表子樹深還有2，則左右子樹各別能提供(2^2-1=3)3個空間，因此我們選擇'3'當作root，分成{1,2}和{4,5,6}到左右子樹，讓右子樹3個空間被填滿，一直遞迴下去直到分配完全部數字。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	void BST(int Left, int Right, int H);
	int main()
	{
	int Case = 1;
	int N, H;
	while (scanf("%d %d", &N, &H) && (N \|\| H)) {
	printf("Case %d:", Case++);
	if (pow(2,H) - 1 < N) {
	puts(" Impossible.");
	continue;
	}
	if (H > N) H = N; // 深度如果大於總數就讓H=N
	BST(1, N, H);
	putchar('\n');
	}
	}
	void BST(int Left, int Right, int H)
	{
	if (H == 0 \|\| Left > Right) return;
	//下一個root應盡可能靠左,所以把右子樹填滿
	int right_space = pow(2, H - 1) - 1; //右子樹空間
	int root = Right - right_space;
	if (root < Left) root = Left;

	printf(" %d", root);

	BST(Left, root - 1, H - 1);
	BST(root + 1, Right, H - 1);
	}

view raw [UVa] 10821 Constructing BST.cpp hosted with ❤ by GitHub

UVa 10954 Add All

想法：
這題不是單純由小加到大，考慮 4 5 5 6 7 這數列，4+5+5=14之後，應該要做6+7=13，之後再做13+14=27。
因此每次都選擇兩個最小的數字相加，然後變成一個數字，然後丟回數列裡面，重複至數列只剩一個數字。
借這題順便練習一下priority_queue，它有三個參數priority_queue<type, container, function>，container有兩種，可以用vector<>和deque<>，function也有兩個，less<>將最大的元素放在top，greater<>將最小的元素放在top。

	#include <cstdio>
	#include <queue>
	using namespace std;
	int main()
	{
	int N, x;
	while (scanf("%d", &N) && N) {
	priority_queue<int, vector<int>, greater<int>> PQ;
	for (int i = 0; i < N; ++i) {
	scanf("%d", &x);
	PQ.push(x);
	}
	int cost = 0;
	while (PQ.size() != 1) {
	x = PQ.top(); PQ.pop();
	x += PQ.top(); PQ.pop();
	cost += x;
	PQ.push(x);
	}
	printf("%d\n", cost);
	}
	return 0;
	}

view raw [UVa] 10954 Add All.cpp hosted with ❤ by GitHub

訂閱：文章 (Atom)

網頁

2014年3月29日 星期六

2014年3月21日 星期五

2014年3月20日 星期四

2014年3月19日 星期三

2014年3月17日 星期一

2014年3月16日 星期日

2014年3月11日 星期二

2014年3月10日 星期一

2014年3月9日 星期日

2014年3月7日 星期五

2014年3月5日 星期三

2014年3月4日 星期二

2014年3月3日 星期一

2014年3月2日 星期日

2014年3月1日 星期六

2014年3月29日星期六

2014年3月21日星期五

2014年3月20日星期四

2014年3月19日星期三

2014年3月17日星期一

2014年3月16日星期日

2014年3月11日星期二

2014年3月10日星期一

2014年3月9日星期日

2014年3月7日星期五

2014年3月5日星期三

2014年3月4日星期二

2014年3月3日星期一

2014年3月2日星期日

2014年3月1日星期六