f677: FJCU_109_Winter_Day3_Lab1 並查集練習

解題心得

為了方便直接看 num[0] 就知道是答案， union 的時候要讓 index 大的指到小的。

程式碼

#include <iostream>
using namespace std;

int p[1000] = { 0 }, num[1000] = { 0 };
int find_set(int u)
{
	if (p[u] == u) return u;
	return p[u] = find_set(p[u]);
}
int main()
{
	int n, m, a, b;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		p[i] = i, num[i] = 1;
	while (m--)
	{
		cin >> a >> b;
		a = find_set(a), b = find_set(b);
		if (a != b)
		{
			if (b > a)
				swap(a, b);
			p[a] = b; // a 指到 b
			num[b] += num[a];
		}
	}
	cout << num[0] << endl;
	return 0;
}

f260: 愛八卦的同學

解題心得

這題沒給 n 的大小，好像不合理.....

而且最後用黑魔法才過的。

程式碼

#include <iostream>
using namespace std;

int f[10000] = { 0 }, Size[10000] = { 0 };

int find_set(int v)
{
	if (f[v] == v) return v;
	return f[v] = find_set(f[v]);
}
void union_by_size(int u, int v)
{
	/*if (Size[u] > Size[v])
		swap(u, v);
	Size[v] += Size[u];*/
	f[u] = v;
}
int main()
{
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	int n, k, a, b;
	while (cin >> n >> k)
	{
		int group = n; // 幾個小圈圈
		for (int i = 0; i < n; i++)
			f[i] = i, Size[i] = 1;
		while (k--)
		{
			cin >> a >> b;
			a = find_set(a), b = find_set(b);
			if (a != b)
			{
				group--;
				union_by_size(a, b);
			}
		}
		cout << group << endl;
	}
	return 0;
}

d831: 畢業旅行

解題心得

額外開一個陣列來記錄該 set 的數量，要找 root(老大) 才是最新的數量。

程式碼

#include <iostream>
using namespace std;

int n, p[1000000] = { 0 }, num[1000000] = { 0 };

int find_set(int v)
{
	if (p[v] == v) return v;
	return p[v] = find_set(p[v]);
}
void init()
{
	for (int i = 0; i < 1000000; i++)
		p[i] = i, num[i] = 1;
}

int main()
{
	int m, a, b;
	while (cin >> n >> m)
	{
		int ans = 1;
		init();
		while (m--)
		{
			cin >> a >> b;
			a = find_set(a), b = find_set(b);
			if (a != b)
			{
				num[b] += num[a];
				p[a] = b; // a 指向 b
				ans = max(ans, num[b]);
			}
		}
		cout << ans << endl;
	}

	return 0;
}

a445: 新手訓練系列- 我的朋友很少

解題心得

disjoint set 練習。

完成 union(a,b), find_set(v), same_set(u, v) 就差不多能過了，只是 find_set 可以再進一步優化。

程式碼

#include <iostream>
using namespace std;

int n, m, q, f[10001] = { 0 };

void Union(int a, int b)
{
	f[a] = b;
}
int find_set(int v)
{
	while (f[v] != v)
		v = f[v];
	return f[v];
}
bool same_set(int a, int b)
{
	return find_set(a) == find_set(b);
}
int main()
{
	int a, b;
	cin >> n >> m >> q;

	for (int i = 1; i <= n; i++)
		f[i] = i;
	while (m--)
	{
		cin >> a >> b;
		Union(find_set(a), find_set(b));
	}
	while (q--)
	{
		cin >> a >> b;
		if (same_set(a, b))
			cout << ":)" << endl;
		else
			cout << ":(" << endl;
	}
	return 0;
}

d432: 第四題：通關密語 (pwd)

解題心得

跟上一題差不多。

程式碼

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

map<char, int> m;
string inOrder, postOrder;

void printPreorder(int start, int end)
{
	if (start > end) return;

	int val = -1, flag = -1;
	for (int i = start; i <= end; i++)
	{
		if (m[inOrder[i]] > val)
		{
			val = m[inOrder[i]];
			flag = i;
		}
	}
	cout << inOrder[flag];

	printPreorder(start, flag - 1);
	printPreorder(flag + 1, end);
}

int main()
{
	cin >> inOrder >> postOrder;
	for (int i = 0; i < postOrder.length(); i++)
		m[postOrder[i]] = i;
	printPreorder(0, postOrder.length() - 1);
	return 0;
}

d861: NOIP2001 3.求先序排列

解題心得

首先，先搞清楚中序跟後序等表示法。

中序: 左子樹、自己、右子樹；後序: 左子樹、右子樹、自己；前序: 自己、左子樹、右子樹。

因此要找「自己」，也就是前序表示法，要參考中序與後序提供的資訊。

要找到當前字串的「自己」，很明顯就是最右邊的字母。接下來要分別往左右子樹搜尋，則要利用中序字串來切割，遞迴下去。

所以每次都要找當前中序字串位於後序表達式中最右邊的字母，找到以後以它為基準，在中序字串中往左跟往右遞迴搜尋。為了方便計算，提前記錄好字母的位置，用一個大小為26的陣列紀錄所有大寫字母。

因為不存在於輸入的字母不會被存取到，直接擺零即可。

我都是看別人教學才會。

程式碼

#include <iostream>
using namespace std;

string inOrder, postOrder;
int order[26] = { 0 };
void printPreorder(int start, int end)
{
	if (start <= end)
	{
		int flag = -1, val = -1;
		for (int i = start; i <= end; i++)
		{
			if (order[inOrder[i] - 'A'] > val)
			{
				val = order[inOrder[i] - 'A'];
				flag = i;
			}
		}
		cout << inOrder[flag];//<< start << " " << flag << " " << flag + 1 << " " << end << endl;
		printPreorder(start, flag - 1);
		printPreorder(flag + 1, end);
	}
}
int main()
{
	
	cin >> inOrder >> postOrder;
	int start = 0, end = postOrder.length() - 1;
	for (int i = 0; i < postOrder.length(); i++)
		order[postOrder[i] - 'A'] = i;
	printPreorder(start, end);
	return 0;
}

f673: FJCU_109_Winter_Day2_Lab1 樹高

解題心得

用 array 存 node，找高度從 root 往下走直到 leaf node，leaf node 要回傳 0 給 parent，parent 選最大的加一後再往上丟。

程式碼

#include <iostream>
using namespace std;

struct Node
{
	int left, right;
};
Node tree[31];

int height(int index)
{
	if (index == -1)
		return 0;
	else
	{
		int leftHeight = height(tree[index].left);
		int rightHeight = height(tree[index].right);
		if (leftHeight > rightHeight) return leftHeight + 1;
		else return rightHeight + 1;
	}
}

int main()
{
	int n, u, a, b, root = -1;
	cin >> n;
	while (n--)
	{
		cin >> u >> a >> b;
		tree[u].left = a; tree[u].right = b;

		if (root == -1) root = u;
	}
	cout << height(root) - 1 << endl;
	return 0;
}

f675: FJCU_109_Winter_Day2_Lab3 二元搜尋樹

解題心得

二元搜尋樹的練習，中規中矩。

程式碼

#include <iostream>
using namespace std;

struct Node
{
	int data;
	Node* left; Node* right;
};
Node* insert(Node* tree, int n)
{
	if (tree == NULL)
	{
		tree = new Node;
		tree->data = n;
		tree->left = tree->right = NULL;
	}
	else
	{
		if (n < tree->data)
			tree->left = insert(tree->left, n);
		else
			tree->right = insert(tree->right, n);
	}
	return tree;
}

void printInorder(Node* tree)
{
	if (tree == NULL) return;

	printInorder(tree->left);
	cout << tree->data << endl;
	printInorder(tree->right);
}
bool search(Node* tree, int val)
{
	if (tree == NULL) return false;

	if (tree->data == val) return true;
	if (val < tree->data) search(tree->left, val);
	else search(tree->right, val);
}

int main()
{
	Node* root = NULL;
	int n, val, m;
	while (cin >> n)
	{
		while (n--)
		{
			cin >> val;
			root = insert(root, val);
		}
		printInorder(root);
		cin >> m;
		if (search(root, m))
			cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

d526: Binary Search Tree (BST)

解題心得

在 insert function 要回傳 tree node 這邊卡超久，一開始沒加，還想說為什麼都沒被更新到。

後來才搞清楚丟到function裡的是a copy of pointer，兩個指標指到同樣的位置(此處為null)，如果要有預期的行為，就需要把function裡的pointer更新回去。 同理，動到left node跟right node也要接收遞迴函式的回傳值。

比對以前寫的類似的程式，才恍然大悟為什麼以前會用class寫──因為就不是copy一份過去了。

程式碼

#include <iostream>
using namespace std;
struct Node
{
	int data;
	Node* left; Node* right;
};

Node* insert(Node* tree, int val)
{
	
	if (tree == NULL)
	{
		tree = new Node;
		tree->data = val;
		tree->left = tree->right = NULL;
	}
	else
	{
		if (val < tree->data)
			tree->left = insert(tree->left, val);
		else
			tree->right = insert(tree->right, val);
	}
	return tree;
}

void printPreorder(Node* tree)
{
	if (tree == NULL) return;

	cout << tree->data << " ";
	printPreorder(tree->left);
	printPreorder(tree->right);
}

int main()
{
	int n, temp;
	while (cin >> n)
	{
		Node* root = NULL;
		while (n--)
		{
			cin >> temp;
			root = insert(root, temp);
		}
		printPreorder(root);
		cout << endl;
	}
	return 0;
}

d119: 有獎徵答：換零錢

解題心得

題目寫得很亂，就沒有仔細看了。

基本上就是零錢問題，記得字串切割跟最後答案要-1就好。

程式碼

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

int prices[10] = { 1,5,10,20,50,100,200,500,1000,2000 };
long long int ans[50001] = { 1 };

int main()
{
	for (int i = 0; i < 10; i++)
	{
		for (int j = prices[i]; j < 50001; j++)
			ans[j] += ans[j - prices[i]];
	}
	string s;
	while (getline(cin, s))
	{
		int n = 0, temp;
		stringstream ss(s);
		while (ss >> temp)
			n += temp;
		if (n == 0) break;
		cout << ans[n] - 1 << endl;
	}
	return 0;
}

b232: TOI2009 第四題：分房子

解題心得

這題也是硬幣問題(或者說解不等式問題?)，硬幣數是奇數。

記得開long long。

程式碼

#include <iostream>
using namespace std;

int prices[376];
long long int ans[751] = { 1,0 };

int main()
{
	for (int i = 0; i < 376; i++)
		prices[i] = i * 2 - 1;
	for (int i = 1; i <= 375; i++)
	{
		for (int j = prices[i]; j < 751; j++)
			ans[j] += ans[j - prices[i]];
	}
	int m, n;
	while (cin >> m)
	{
		while (m--)
		{
			cin >> n;
			cout << ans[n] << endl;
		}
		cout << endl;
	}
	return 0;
}