git: push a folder to an empty repo

git init

git add .

git remote add origin https://gitlab.com/username/repo.git

git commit -m "your message"

git push -u origin master

Done!

i524: 11988: Broken Keyboard (a.k.a. Beiju Text)

程式碼

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

int main()
{
	string s;
	while (cin >> s)
	{
		string ans = "";
		int index = 0;
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] == '[')
			{
				index = 0;
			}
			else if (s[i] == ']')
			{
				index = ans.size() ;
				if (index < 0) index = 0;
			}
			else
			{
				ans.insert(index, string(1, s[i]));
				index++;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

h033: 雜訊移除 (Noise)

程式碼

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int main()
{
	string s;
	int n;
	cin >> s >> n;
	int i = 0;
	while (i != s.size())
	{
		if (s[i] - '0' == n)
		{
			s.erase(i, 1);
		}
		else
			i++;
	}
	bool flag = true;
	for (int i = 0; i < s.size() / 2; i++)
	{
		if (s[i] != s[s.size() - i - 1])
		{
			flag = false;
			break;
		}
	}
	if (flag) cout << "Yes";
	else cout << "No";
	return 0;
}

h081: 1. 程式交易

解題心得

題目中的利潤跟我認知的不一樣，整題花在理解題意上面的時間最久。

程式碼

#include<iostream>
using namespace std;

int main()
{
	int n, d, a[101] = { 0 }, sum = 0, current = -1;
	bool flag = false;
	cin >> n >> d;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		if (i == 0)
		{
			current = a[i];
			flag = true;
		}
		else if (flag && a[i] >= current + d)
		{
			sum += a[i] - current;
			current = a[i];
			flag = false;
		}
		else if (!flag && a[i] <= current - d) // 當下沒有持有股票
		{
			current = a[i];
			flag = true;
		}
	}
	cout << sum;
	return 0;
}

g796: 檔案分類 (Files)

程式碼

#include<iostream>
using namespace std;

int main()
{
	int n, file[100] = { 0 }, index = 0;
	string s;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		index = (s[3] - '0') * 10 + (s[4] - '0');
		file[index] ++ ;
	}
	for (int i = 0; i < 100; i++)
	{
		if (file[i])
		{
			cout << i << " " << file[i] << endl;
		}
	}
	return 0;
}

i399: 1. 數字遊戲

程式碼

#include<iostream>
using namespace std;

int main()
{
	int index[10] = { 0 }, maxTime = 0, n;
	for (int i = 0; i < 3; i++)
	{
		cin >> n;
		index[n]++;
	}
	for (int i = 0; i < 10; i++)
	{
		if (index[i] > maxTime)
			maxTime = index[i];
	}
	cout << maxTime << " ";
	for (int i = 9; i >= 0; i--)
	{
		if (index[i])
		{
			cout << i;
			maxTime--;
			if (3 - maxTime != 0) cout << " ";
		}
	}
	return 0;
}

i071: 風景 (Landscape)

解題心得

往左看一次，往右也看一次。

程式碼

#include<iostream>
using namespace std;

int main()
{
	int n, m, arr[1001], sum = 0, height;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	m -= 1;
	height = arr[m];
	for (int i = m - 1; i >= 0; i--)
	{
		if (arr[i] > height)
		{
			height = arr[i];
			sum++;
		}
	}
	height = arr[m];
	for (int i = m + 1; i < n; i++)
	{
		if (arr[i] > height)
		{
			height = arr[i];
			sum++;
		}
	}
	cout << sum;
	return 0;
}

h659: 計程車 (Taxi)

解題心得

想了一下才想到如何判斷區間QQ

程式碼

#include<iostream>
using namespace std;

int main()
{
	int k, w, s, e, sum = 0;
	cin >> k >> w >> s >> e;

	if (k < 2)
		sum += 20;
	else
		sum += 20 + (k - 2) * 5;
	sum += (w / 2) * 5;
	bool time[24] = { false };
	for (int i = s; i <= e; i++)
		time[i] = true;

	if (time[18] && time[19]) sum += 185;
	if (time[19] && time[20]) sum += 195;
	if (time[20] && time[21]) sum += 205;
	if (time[21] && time[22]) sum += 215;
	if (time[22] && time[23]) sum += 225;
	cout << sum;
	return 0;
}

h658: 捕魚 (Fishing)

程式碼

#include<iostream>
using namespace std;

int main()
{
	int x, y, n, fishX[501] = { 0 }, fishY[501] = { 0 }, ansX = 0, ansY = 0;
	cin >> x >> y >> n;
	
	for (int i = 0; i < n; i++)
	{
		cin >> fishX[i] >> fishY[i];
		int now = abs(x - fishX[i]) * abs(x - fishX[i]) + abs(y - fishY[i]) * abs(y - fishY[i]);
		int best = abs(x - fishX[ansX]) * abs(x - fishX[ansX]) + abs(y - fishY[ansY]) * abs(y - fishY[ansY]);
		if (now < best)
		{
			ansX = i;
			ansY = i;
		}
	}
	cout << fishX[ansX] << " " << fishY[ansY];
	return 0;
}

f679: 公會成員

解題心得

原本left<=right沒有加等號，加上後就過了。

程式碼

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

int main()
{
	long long int n, q, x, t;
	vector<long long int> v;

	cin >> n >> q;
	for (int i = 0; i < n; i++)
	{
		cin >> x;
		v.push_back(x);
	}
	while (q--)
	{
		cin >> t;
		int left = 0, right = v.size() - 1, mid = (left + right) / 2;
		bool flag = false;
		while (left <= right)
		{
			if (v[mid] == t)
			{
				flag = true;
				break;
			}
			else if (v[mid] < t)
			{
				left = mid + 1;
			}
			else
			{
				right = mid - 1;
			}
			mid = (left + right) / 2;
		}
		if (flag) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	
	return 0;
}

f327: 刪除欄位

解題心得

跟這題有點像。

程式碼

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

int main()
{
	string s1, s2;
	int base = 0, col1 = 0, col2 = 0;
	cin >> s1 >> s2;
	for (int i = s1.size() - 1; i >= 0; i--)
	{
		col1 += (s1[i] - 'A' + 1) * pow(26, base);
		base++;
	}
	base = 0;
	for (int i = s2.size() - 1; i >= 0; i--)
	{
		col2 += (s2[i] - 'A' + 1) * pow(26, base);
		base++;
	}
	cout << abs(col1 - col2) + 1;
	return 0;
}

f291: 試算表大小

解題心得

AAA3 = AAA(col) * 3(row)

AAA = A * 26^2 + A * 26^1 + A

程式碼

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

int main()
{
	string s;
	int col = 0, row = 0, base = 1;
	cin >> s;
	while (isdigit(s.back()))
	{
		row += base * (s.back() - '0');
		s.pop_back();
		base *= 10;
	}
	base = 0;
	for (int i = s.size() - 1; i >= 0; i--)
	{
		col += (s[i] - 'A' + 1) * pow(26, base);
		base++;
	}
	cout << col * row;
	return 0;
}

f418: Word Search Puzzle

程式碼

#include<iostream>
using namespace std;

int main()
{
	int h, w, r1, c1, r2, c2;
	cin >> h >> w >> r1 >> c1 >> r2 >> c2;
	r1 -= 1; c1 -= 1; r2 -= 1; c2 -= 1;
	char puzzle[20][50];
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			cin >> puzzle[i][j];
	if (r1 == r2)
	{
		for (int i = c1; i <= c2; i++)
			cout << puzzle[r1][i];
	}
	else if (c1 == c2)
	{
		for (int i = r1; i <= r2; i++)
			cout << puzzle[i][c1];
	}
	else
	{
		for (int i = 0; i <= abs(r1 - r2); i++)
			cout << puzzle[r1 + i][c1 + i];
	}
	return 0;
}

f821: nAnB ( 正常版 )

程式碼

#include<iostream>
using namespace std;

int main()
{
	string ans, s;
	int m;
	cin >> ans >> m;
	while (m--)
	{
		cin >> s;
		int a = 0, b = 0;
		for (int i = 0; i < s.size(); i++)
		{
			for (int j = 0; j < s.size(); j++)
			{
				if (ans[i] == s[j])
				{
					if (i == j) a++;
					else b++;
				}
			}
		}
		cout << a << "A" << b << "B" << endl;
	}
	return 0;
}

f640: 函數運算式求值

解題心得

用stack，把字串倒著看。

程式碼

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

int main()
{
	int x, y, z;
	stack<int> st;
	vector<string> v;
	string s;
	while (cin >> s)
		v.push_back(s);
	for (int i = v.size() - 1; i >= 0; i--)
	{
		if (v[i] == "f")
		{
			x = st.top(); st.pop();
			x = 2 * x - 3;
			st.push(x);
		}
		else if (v[i] == "g")
		{
			x = st.top(); st.pop();
			y = st.top(); st.pop();
			x = 2 * x + y - 7;
			st.push(x);
		}
		else if (v[i] == "h")
		{
			x = st.top(); st.pop();
			y = st.top(); st.pop();
			z = st.top(); st.pop();
			x = 3 * x - 2 * y + z;
			st.push(x);
		}
		else
		{
			st.push(stoi(v[i]));
		}
	}
	cout << st.top();
	return 0;
}

g308: pB. 跳跳布朗尼(Brownie)

程式碼

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

int main()
{
	int n, t, brownie[1001] = { 0 }, info[1001] = { 0 }, sum = 0;
	bool isVisited[1001] = { false };

	cin >> n >> t;
	for (int i = 0; i < n; i++)
		cin >> info[i];
	for (int i = 0; i < n; i++)
		cin >> brownie[i];

	while (!isVisited[t])
	{
		sum += brownie[t];
		isVisited[t] = true;
		t = info[t];
	}
	cout << sum;
	return 0;
}

g307: pA. 為了好吃的蘋果派(Apple Pie)

解題心得

照著題目敘述即可。

程式碼

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

int main()
{
	int n, k, t, arr[1001] = { 0 };
	bool flag = false;

	cin >> n >> k >> t;
	for (int r = 0; r < n; r++)
	{
		for (int i = 0; i < k; i++)
			cin >> arr[i];
		sort(arr, arr + k);
		int sum = 0;
		for (int i = 1; i < k - 1; i++)
			sum += arr[i];
		if ((double)sum / (k - 2) >= t)
		{
			cout << r << endl;
			flag = true;
		}
	}
	if (!flag) cout << "A is for apple." << endl;
	return 0;
}

h660: 躲避球 (DodgeBall)

解題心得

照著題目說明做就好了。

程式碼

#include <iostream>
using namespace std;

int main()
{
	int x, r, v, n, p, s;
	cin >> x >> r >> v >> n;
	while (n--)
	{
		cin >> p >> s;
		if (x - r <= p && p <= x + r && v >= s)
			x = p;
		else if (x - r <= p && p <= x + r && v < s)
		{
			if (p < x) x += 15;
			else x -= 15;
		}
	}
	cout << x;
	return 0;
}

g488: COVID-101

解題心得

事先算好，直接輸出。

程式碼

#include <iostream>
using namespace std;

int main()
{
	long long int x[201] = { 0, 1 };
	for (int i = 2; i <= 200; i++)
	{
		x[i] = x[i - 1] + i * i - i + 1;
	}

	int n;
	cin >> n;
	cout << x[n];
	return 0;
}

i213: stack 練習

解題心得

就很基本的stack(?

程式碼

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

int main()
{
	int n, k, x;
	stack<int> st;
	
	cin >> n;
	while (n--)
	{
		cin >> k;
		if (k == 1)
		{
			cin >> x;
			st.push(x);
		}
		else if (k == 2)
		{
			if (st.empty()) cout << -1 << endl;
			else cout << st.top() << endl;
		}
		else if (k == 3)
		{
			if (!st.empty())
				st.pop();
		}
	}
	return 0;
}

f447: 12918 - Lucky Thief

解題心得

這題滿簡單的，想不到會在第四題。

只要稍微推一下就知道是連續數字的相加，代入公式就好，但沒想到CPE測資比ZJ嚴格。

程式碼

#include <iostream>
using namespace std;

int main()
{
	long long int t, n, m;
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		cout << (m - 1 + m - n) * n / 2 << endl;
	}
	return 0;
}

f446: 1237 - Expert Enough

解題心得

每次有新的query，就掃過所有車種，看有幾個符合，以及記錄符合的index。

如果有零個或不只一個，那就不對。如果只有一個，那就可以用index找到車種名稱了。

程式碼

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

struct carInfo
{
	string name;
	int low, high;
};
carInfo db[10000];
int main()
{
	int t, d, l, h, q, p;
	string m;
	cin >> t;
	while (t--)
	{
		cin >> d;

		for (int i = 0; i < d; i++)
			cin >> db[i].name >> db[i].low >> db[i].high;
		cin >> q;
		while (q--)
		{
			cin >> p;
			int flag = 0, index = -1;
			for (int i = 0; i < d; i++)
			{
				if (db[i].low <= p && p <= db[i].high)
					flag++, index = i;
			}
			if (flag != 1) cout << "UNDETERMINED" << endl;
			else cout << db[index].name << endl;
		}
		
		if (t != 0) cout << endl;
	}
	return 0;
}

f445: 263 - Number Chains

解題心得

照著題目敘述做就好。

程式碼

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

int descending(int n)
{
	int arr[10] = { 0 }, ans = 0;
	while (n)
	{
		arr[n % 10]++;
		n /= 10;
	}
	for (int i = 9; i >= 0; i--)
	{
		while (arr[i] != 0)
		{
			ans = ans * 10 + i;
			arr[i]--;
		}
	}
	return ans;
}
int ascending(int n)
{
	int arr[10] = { 0 }, ans = 0;
	while (n)
	{
		arr[n % 10]++;
		n /= 10;
	}
	for (int i = 0; i < 10; i++)
	{
		while (arr[i] != 0)
		{
			ans = ans * 10 + i;
			arr[i]--;
		}
	}
	return ans;
}
int main()
{
	int n;
	while (cin >> n && n)
	{
		vector<int> v;
		cout << "Original number was " << n << endl;
		while (true)
		{
			int ascend = ascending(n), descend = descending(n), result = descend - ascend;
			cout << descend << " - " << ascend << " = " << result << endl;
			
			if (v.size() != 0 && find(v.begin(), v.end(), result) != v.end())
				break;
			v.push_back(result);
			n = result;
		}
		cout << "Chain length " << v.size() + 1 << endl << endl;
		
	}
	return 0;
}

f444: 10268 - 498-bis

解題心得

CPE 的系統跟 zerojudge 的測資格式不太一樣，後者好像不是用 \n 換行，只好再用別的方法寫。

程式碼

[for CPE]

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int main()
{
	long long int x, a;
	while (cin >> x)
	{
		vector<long long int> bits;
		long long int ans = 0;
		while (cin >> a && getchar() != '\n')
			bits.push_back(a);
		for (int i = 0; i < bits.size(); i++)
		{
			bits[i] *= bits.size() - i;
			ans += bits[i] * pow(x, bits.size() - 1 - i);
		}
		cout << ans << endl;
	}
	return 0;
}

[for ZJ]

#include <iostream>
#include <vector>
#include <sstream>
#include <math.h>
#include <string>
using namespace std;

int main()
{
	long long int x, a;
	string s;
	while (cin >> x)
	{
		vector<long long int> bits;
		long long int ans = 0;
		cin.ignore();
		getline(cin, s);
		stringstream ss(s);
		while (ss >> a)
			bits.push_back(a);
		bits.pop_back();
		for (int i = 0; i < bits.size(); i++)
		{
			bits[i] *= bits.size() - i;
			ans += bits[i] * pow(x, bits.size() - 1 - i);
		}
		cout << ans << endl;
	}
	return 0;
}

f439: 10191 - Longest Nap

解題心得

這題不難，只是很多瑣碎的地方要弄。

基本上就是把開始跟結束時間轉換成分鐘，然後用陣列來記錄哪些時候有空或沒空，最後再從頭掃到尾找最長的空檔。因為是10:00開始，把所有轉換後的時間減10*60分鐘。

寫完後覺得寫很醜，如果用開始跟結束時間作為標記，不知道會不會好看一點。

程式碼

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

int t[480] = { 0 };

int to_int(string s)
{
	int n = 0;
	n = stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3, 2)) - 600;
	return n;
}

int main()
{
	int testcase, counter = 1;
	while (cin >> testcase)
	{
		cin.ignore();
		for (int i = 0; i < 480; i++) t[i] = 0;
		for (int days = 1; days <= testcase; days++)
		{
			string s, start, end;
			getline(cin, s);
			start = s.substr(0, 5);
			end = s.substr(6, 5);
			for (int i = to_int(start); i <= to_int(end); i++)
				t[i] = 1;

			//cout << to_int(start) << " " << to_int(end) << endl;
		}
		int prev = -1, count = 0, maxCount = 0, curTime = 0, time = 0;
		for (int i = 0; i < 480; i++)
		{
			if (t[i] == 0)
				count++;
			if ((t[i] == 1 && prev == 0) || i == 479)
			{
				if (curTime == 0) count--;
				if (count + 1 > maxCount)
				{
					maxCount = count + 1;
					time = curTime;
				}
				count = 0;
				//cout << "update: " << maxCount << endl;
			}
			if (t[i] == 0 && prev == 1)
				curTime = i - 1;
			prev = t[i];
		}
		cout << "Day #" << counter++ << ": the longest nap starts at " << (time + 600) / 60 << ":";
		if ((time + 600) % 60 < 10) cout << "0" << (time + 600) % 60 ;
		else cout << (time + 600) % 60;
		cout << " and will last for ";
		if (maxCount < 60) cout << maxCount << " minutes.\n";
		else cout << maxCount / 60 << " hours and " << maxCount % 60 << " minutes.\n";

	}
	return 0;
}
// 18*60 - 10*60 = 8*60 = 480

f438: 855 - Lunch in Grid City

解題心得

最後好像也沒用到s跟a的值。

程式碼

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


int main()
{
	int t, s, a, f;
	cin >> t;
	while (t--)
	{
		int arrS[50001], arrA[50001];
		cin >> s >> a >> f;
		for (int i = 0; i < f; i++)
			cin >> arrS[i] >> arrA[i];
		sort(arrS, arrS + f);
		sort(arrA, arrA + f);

		if (f % 2 == 1) cout << "(Street: " << arrS[f / 2] << ", Avenue: " << arrA[f / 2] << ")" << endl;
		else cout << "(Street: " << arrS[f / 2 - 1] << ", Avenue: " << arrA[f / 2 - 1] << ")" << endl;
	}
	return 0;
}

a941: 10041 - Vito's large family

解題心得

vito family的進化版(?)，如果直接重跑過一遍s[]把距離加起來會tle。

但最後還是用了黑魔法的那兩行才過的。

程式碼

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

int s[2000000] = { 0 },record[30001] = { 0 };

int main()
{
	cin.sync_with_stdio(false), cin.tie(0);
	int t, r;
	cin >> t;
	while (t--)
	{
		cin >> r;
		for (int i = 0; i < 30001; i++)
			record[i] = 0;
		for (int i = 0; i < r; i++)
		{
			cin >> s[i];
			record[s[i]]++;
		}
		sort(s, s + r);
		int mid = 0;
		long long int d = 0;
		if (r % 2 == 1) mid = s[r / 2];
		else mid = s[r / 2 - 1];
		for (int i = 0; i <= 30000; i++)
		{
			d += abs(i - mid) * record[i];
		}
		cout << d << " " << mid << endl;
	}
	return 0;
}

d501: 第二題：數列最小值

解題心得

很像高中數學曾經學過的題目，印象中解法是：

1. 當 n 為奇數，則答案為中位數

2. 當 n 為偶數，則答案為區間內的所有整數

程式碼

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

int n, arr[1000000] = { 0 };

int main()
{
	while (cin >> n)
	{
		for (int i = 0; i < n; i++)
			cin >> arr[i];
		sort(arr, arr + n);
		if (n % 2 == 1)
			cout << "A=" << arr[n / 2] << endl;
		else
		{
			cout << "A=";
			for (int i = arr[n / 2 - 1]; i <= arr[n / 2]; i++)
			{
				if (i != arr[n / 2])
					cout << i << "、";
				else
					cout << i << endl;
			}
		}
		
	}
	return 0;
}

f437: 1368 - DNA Consensus String

解題心得

要找到第 i 個會是哪個字母，就去統計所有的字串的第 i 個都是哪些字母，找出現最多的那個。如果出現次數相同，則按照字典序順序，所以判斷式的等於才會那樣寫。

要計算 hamming 距離，就是統計不符合的字元次數。

程式碼

#include <iostream>
using namespace std;

int main()
{
	int t, m, n;
	string s[50];
	cin >> t;
	while (t--)
	{
		cin >> m >> n;
		for (int i = 0; i < m; i++)
			cin >> s[i];
		string ans = "";
		int d = 0;
		for (int i = 0; i < n; i++)
		{
			int countA = 0, countT = 0, countC = 0, countG = 0;
			for (int j = 0; j < m; j++)
			{
				if (s[j][i] == 'A') countA++;
				else if (s[j][i] == 'T') countT++;
				else if (s[j][i] == 'C') countC++;
				else if (s[j][i] == 'G') countG++;
			}
			if (countA >= countC && countA >= countG && countA >= countT)
				ans += "A", d += countC + countG + countT;
			else if (countC > countA && countC >= countG && countC >= countT)
				ans += "C", d += countA + countG + countT;
			else if (countG > countA && countG > countC && countG >= countT)
				ans += "G", d += countC + countA + countT;
			else
				ans += "T", d += countC + countG + countA;
		}
		cout << ans << endl << d << endl;
	}
	return 0;
}

11498: Division of Nlogonia

解題心得

沒有心得。

程式碼

#include <iostream>
using namespace std;

int main()
{
	int t, n, m, x, y;
	while (cin >> t && t)
	{
		cin >> n >> m;
		while (t--)
		{
			cin >> x >> y;
			if (x > n && y > m)
				cout << "NE" << endl;
			else if (x < n && y > m)
				cout << "NO" << endl;
			else if (x > n && y < m)
				cout << "SE" << endl;
			else if (x < n && y < m)
				cout << "SO" << endl;
			else
				cout << "divisa" << endl;
		}
	}
	return 0;
}

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;
}

d289: 多元一次方程式

解題心得

這題就是零錢問題，或者說零錢問題的本質就是解不等式(?

程式碼

#include <iostream>
using namespace std;

int prices[8] = { 1,13,33,43,139,169,1309,2597 };
int ans[8001] = { 1,0 };

int main()
{
	for (int i = 0; i < 8; i++)
	{
		for (int j = prices[i]; j < 8001; j++)
			ans[j] += ans[j - prices[i]];
	}

	int l;
	while (cin >> l)
		cout << ans[l] << endl;
	return 0;
}

d253: 00674 - Coin Change

解題心得

想法類似於：前一種金額的方法數加一(?)

參考這裡

程式碼

#include <iostream>
using namespace std;

int prices[5] = { 1,5,10,25,50 };
int c[7490] = { 1,0 };


int main()
{
	for (int i = 0; i < 5; i++)
	{
		for (int j = prices[i]; j <= 7489; j++)
			c[j] += c[j - prices[i]];
	}
	int n;
	while (cin >> n)
		cout << c[n] << endl;
	return 0;
}

d904: 換零錢

解題心得

price放幣值種類，大小順序不重要。

每次單看一種種類的幣值，把1~c的目標金額都算過一次，如果新的(也就是扣掉自己的那個金額再加一)比現在需要的硬幣少，就更新。

參考這個跟這個網站。

程式碼

#include <iostream>
using namespace std;

int price[11] = { 0 }, money[1001] = { 0 };

int main()
{
	int c, n;
	while (cin >> c >> n)
	{
		for (int i = 0; i < n; i++)
			cin >> price[i];
		for (int i = 1; i < 1001; i++)
			money[i] = 1000000;
		for (int i = 0; i < n; i++)
		{
			for (int j = price[i]; j <= c; j++)
			{
				money[j] = min(money[j], money[j - price[i]] + 1);
			}
		}
		if (money[c] != 1000000) cout << money[c] << endl;
	}
	return 0;
}

d887: 1.山脈種類(chain)

解題心得

連續寫了幾題，對怎麼分析好像稍微有點感覺了。雖然還是不會寫。

DP的精神就是切割成小問題，這題的切法是想：曲線第一次的落地點在哪？

山的總長度為2n，因此落地可在2n, 2n-2, 2n-4, ......, 0。

程式碼

#include <iostream>
using namespace std;

int main()
{
	long long int memo[26] = { 1,0 }, n;
	for (int i = 1; i < 26; i++)
	{
		for (int j = 0; j < i; j++)
			memo[i] += memo[j] * memo[i - 1 - j];
	}
	while (cin >> n)
	{
		cout << memo[n] << endl;
	}
	return 0;
}

a111: 12149 - Feynman

解題心得

總是沒辦法自己想出來......紀錄一下推導。

以 4*4 的方形為例，會有：

1*1 的方形，共 16 個

2*2 的方形，共 9 個

3*3 的方形，共 4 個

4*4 的方形，共 1 個

基本邏輯就是把1~n邊長都找過一遍，看這樣的情況下能有幾種可能。又長度為i的情況下，會有(n-i)*(n-i)的可能，也就剛好是1^2+2^2+3^3+.....+n^2了。

用dp的話，就把每次結果存起來，算當下的就是把前一個加上自己的n^2就好。

程式碼 

#include <iostream>
using namespace std;

int main()
{
	int memo[101] = { 0,1 }, n;
	for (int i = 2; i < 101; i++)
		memo[i] = memo[i - 1] + i * i;
	while (cin >> n && n != 0)
		cout << memo[n] << endl;
	return 0;
}

d054: 11310 - DELIVERY DEBACLE

解題心得

參考了這個網站

程式碼

#include <iostream>
using namespace std;

int main()
{
	long long int memo[41] = { 1,1,5 };
	for (int i = 3; i <= 40; i++)
		memo[i] = memo[i - 1] + 4 * memo[i - 2] + 2 * memo[i - 3];
	int t, n;
	cin >> t;
	while (t--)
	{
		cin >> n;
		cout << memo[n] << endl;
	}
	return 0;
}

d038: 00900 - Brick Wall Patterns

解題心得

這題的本質就是 fib ，原因是要找 n 能有幾種拼法，就是把 n-1 的所有方法再加上直立的一個磚塊，以及 n-2 的所有方法再加上兩個平躺磚塊。

網路上的解法比較多是事先建表。我的寫法是每次都會查表，而若以前做過就不會重做。

程式碼

#include <iostream>
using namespace std;

long long int memo[51] = { 0 };
long long int f(int n)
{
	if (memo[n] != 0) return memo[n];
	if (n <= 2) return n;
	memo[n] = f(n - 1) + f(n - 2);
	return memo[n];
}
int main()
{
	int n;
	while (cin >> n)
	{
		if (n == 0) break;
		cout << f(n) << endl;
	}
	return 0;
}

e550: 00722 - Lakes

解題心得

輸入很麻煩的題目。

程式碼

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

struct Point
{
	int x, y;
};

char map[100][100];
int main()
{
	int T, dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
	cin >> T;
	while (T--)
	{
		int i, j, n = 0, m = 0, area = 0;
		string s;
		cin >> i >> j;
		i -= 1, j -= 1;
		getline(cin, s);

		while (getline(cin,s) && s.size())
		{
			for (int i = 0; i < s.size(); i++)
				map[m][i] = s[i];
			n = s.size();
			m++;
		}
		Point start, now;
		queue<Point> q;
		start.x = i, start.y = j;
		map[start.x][start.y] = '@';
		q.push(start);
		while(!q.empty())
		{
			now = q.front(); q.pop();
			//cout << now.x << " " << now.y << endl;
			area++;
			for (int i = 0; i < 4; i++)
			{
				Point p;
				p.x = now.x + dx[i], p.y = now.y + dy[i];
				//cout << "--" << p.x << " " << p.y << endl;
				if (p.x >= 0 && p.x < m && p.y >= 0 && p.y < n && map[p.x][p.y] == '0')
				{
					map[p.x][p.y] = '@';
					q.push(p);
				}
			}
		}
		cout << area << endl;
	}
	return 0;
}

c129: 00572 – Oil Deposits

解題心得

因為沒有固定的起始點，所以這樣寫(?

程式碼

#include <iostream>
using namespace std;

char map[101][101];
bool isVisited[101][101] = { false };
int m, n;

void bfs(int x, int y, char c)
{
	map[x][y] = 'x';
	isVisited[x][y] = true;
	int dx[8] = { -1,-1,-1,0,0,1,1,1 } , dy[8] = { -1,0,1,-1,1,-1,0,1 };
	for (int i = 0; i < 8; i++)
	{
		int nextX = x + dx[i], nextY = y + dy[i];
		if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && map[nextX][nextY] == c && !isVisited[nextX][nextY])
			bfs(nextX, nextY, c);
	}
}
int main()
{
	int counter = 1;
	

	while (cin >> m >> n)
	{
		if (m == 0 && n == 0) break;
		for (int i = 0; i < 101; i++)
			for (int j = 0; j < 101; j++)
				isVisited[i][j] = false;
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				cin >> map[i][j];

		int ans = 0;
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (map[i][j] == '@' && !isVisited[i][j])
					bfs(i, j, '@'), ans++;
			}
		}
		cout << ans << endl;
	}

	return 0;
}

d406: 倒水時間

解題心得

在dfs的「探索相鄰節點」步驟除了一一列舉外，還有更簡潔的寫法，就是將座標所需的位移裂成矩陣，迴圈檢查合法與否即可。

程式碼

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

int map[101][101] = { 0 };
struct Point
{
	int x, y, step = -1;
};

int main()
{
	int s, n, m, counter = 1;
	while (cin >> s)
	{
		cin >> n >> m;
		bool isVisited[101][101] = { false };
		Point start, now;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				cin >> map[i][j];
				if (i == 0 && map[i][j] == 1)
					start.x = i, start.y = j;
			}
		}
		queue<Point> q;
		isVisited[start.x][start.y] = true;
		start.step = 1;
		q.push(start);
		int dx[4] = { 1,0,0,-1 }, dy[4] = { 0,1,-1,0 }; // 最後一個是往上
		while (!q.empty())
		{
			now = q.front(); q.pop();
			for (int i = 0; i < 4; i++)
			{
				if (i == 3 && s == 2) break;
				Point p;
				p.x = now.x + dx[i]; p.y = now.y + dy[i];
				if (p.x >= 0 && p.x < n && p.y >= 0 && p.y < m && map[p.x][p.y] != 0 && !isVisited[p.x][p.y])
				{
					isVisited[p.x][p.y] = true;
					p.step = now.step + 1;
					map[p.x][p.y] = p.step;
					q.push(p);
				}
				
			}
			isVisited[now.x][now.y] = true;
		}
		cout << "Case " << counter++ << ":" << endl;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (map[i][j] != 0 && !isVisited[i][j]) cout << 0;
				else cout << map[i][j];
				if (j != m - 1) cout << " ";
				else cout << endl;
			}
		}
	}
	return 0;
}

c124: 00532 - Dungeon Master

解題心得

除了東西南北外，多考慮上下的bfs。

程式碼

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

struct Point
{
	int level, x, y, step = -1;
};
int l, r, c;
char map[31][31][31];


int main()
{
	
	while (cin >> l >> r >> c)
	{
		if (l == 0 && r == 0 && c == 0) break;

		bool isVisit[31][31][31] = { false };
		Point start, end, now;
		for (int i = 0; i < l; i++)
		{
			for (int j = 0; j < r; j++)
			{
				for (int k = 0; k < c; k++)
				{
					cin >> map[i][j][k];
					if (map[i][j][k] == 'S')
						start.level = i, start.x = j, start.y = k;
					if (map[i][j][k] == 'E')
						end.level = i, end.x = j, end.y = k;
				}
			}
			cin.ignore();
		}
		
		queue<Point> q;
		start.step = 0;
		q.push(start);
		isVisit[start.level][start.x][start.y] = true;
		bool isValid = false;
		while (!q.empty())
		{
			now = q.front(); q.pop();
			//cout << now.level << " " << now.x << " " << now.y << " " << now.step << endl;
			if (map[now.level][now.x][now.y] == 'E')
			{
				cout << "Escaped in " << now.step << " minute(s)." << endl;
				isValid = true;
				break;
			}
			if (now.x - 1 >= 0 && map[now.level][now.x - 1][now.y] != '#' && !isVisit[now.level][now.x - 1][now.y])
			{
				isVisit[now.level][now.x - 1][now.y] = true;
				Point p; p.level = now.level; p.x = now.x - 1; p.y = now.y;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.x + 1 < r && map[now.level][now.x + 1][now.y] != '#' && !isVisit[now.level][now.x + 1][now.y])
			{
				isVisit[now.level][now.x + 1][now.y] = true;
				Point p; p.level = now.level; p.x = now.x + 1; p.y = now.y;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.y - 1 >= 0 && map[now.level][now.x][now.y - 1] != '#' && !isVisit[now.level][now.x][now.y - 1])
			{
				isVisit[now.level][now.x][now.y - 1] = true;
				Point p; p.level = now.level; p.x = now.x; p.y = now.y - 1;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.y + 1 < c && map[now.level][now.x][now.y + 1] != '#' && !isVisit[now.level][now.x][now.y + 1])
			{
				isVisit[now.level][now.x][now.y + 1] = true;
				Point p; p.level = now.level; p.x = now.x; p.y = now.y + 1;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.level - 1 >= 0 && map[now.level - 1][now.x][now.y] != '#' && !isVisit[now.level - 1][now.x][now.y])
			{
				isVisit[now.level- 1][now.x][now.y ] = true;
				Point p; p.level = now.level - 1; p.x = now.x; p.y = now.y;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.level + 1 < l && map[now.level + 1][now.x][now.y] != '#' && !isVisit[now.level + 1][now.x][now.y])
			{
				isVisit[now.level + 1][now.x][now.y] = true;
				Point p; p.level = now.level + 1; p.x = now.x; p.y = now.y;
				p.step = now.step + 1;
				q.push(p);
			}
			isVisit[now.level][now.x][now.y] = true;
		}
		if (!isValid) cout << "Trapped!" << endl;
	}
	return 0;
}

d453: 三、最短距離

解題心得

也是中規中矩的bfs(?

記得清空，以及題目input的座標是從1開始。

程式碼

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

struct Point
{
	int x, y, step = -1;
};
char map[101][101] = { 0 };
bool isVisited[101][101] = { false };
int main()
{
	int N, n, m;
	Point start, end, now;
	cin >> N;
	while (N--)
	{
		cin >> n >> m >> start.x >> start.y >> end.x >> end.y;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				cin >> map[i][j];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				isVisited[i][j] = false;
		start.x -= 1; start.y -= 1; end.x -= 1; end.y -= 1;
		//bfs
		queue<Point> q;
		isVisited[start.x][start.y] = true; start.step = 1;
		bool isValid = false;
		q.push(start);
		while (!q.empty())
		{
			now = q.front(); 
			q.pop();
			//cout << now.x << " " << now.y << " " << now.step << endl;
			if (now.x == end.x && now.y == end.y)
			{
				cout << now.step << endl;
				isValid = true;
				break;
			}
			if (now.x - 1 >= 0 && map[now.x - 1][now.y] == '0' && !isVisited[now.x - 1][now.y])
			{
				Point p; p.x = now.x - 1; p.y = now.y; 
				isVisited[now.x - 1][now.y] = true;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.x + 1 < n && map[now.x + 1][now.y] == '0' && !isVisited[now.x + 1][now.y])
			{
				Point p; p.x = now.x + 1; p.y = now.y;
				isVisited[now.x + 1][now.y] = true;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.y - 1 >= 0 && map[now.x][now.y - 1] == '0' && !isVisited[now.x][now.y - 1])
			{
				Point p; p.x = now.x; p.y = now.y - 1;
				isVisited[now.x][now.y - 1] = true;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.y + 1 < m && map[now.x][now.y + 1] == '0' && !isVisited[now.x][now.y + 1])
			{
				Point p; p.x = now.x; p.y = now.y + 1;
				isVisited[now.x][now.y + 1] = true;
				p.step = now.step + 1;
				q.push(p);
			}
			isVisited[now.x][now.y] = true;
		}
		if (!isValid) cout << 0 << endl;
	}
	return 0;
}

a290: 新手訓練系列 ~ 圖論

解題心得

中規中矩的題目，記得要清空graph再繼續吃新測資。

不過我是看以前上課講義的演算法寫的XD

程式碼

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

int graph[801][801] = { 0 };

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m, a, b, now;
	while (cin >> n >> m)
	{
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n; j++)
				graph[i][j] = 0;
		while (m--)
		{
			cin >> a >> b;
			graph[a][b] = 1;
		}
		cin >> a >> b;

		queue<int> q;
		bool isVisited[801] = { false }, isValid = false;
		q.push(a);
		isVisited[a] = true;
		while (!q.empty())
		{
			now = q.front();
			q.pop();
			for (int i = 1; i <= n; i++)
			{
				if (graph[now][i] == 1 && isVisited[i] == false)
				{
					isVisited[i] = true;
					q.push(i);

					if (i == b)
					{
						isValid = true;
						break;
					}
				}
			}
			isVisited[now] = true;
		}
		if (isValid) cout << "Yes!!!" << endl;
		else cout << "No!!!" << endl;
	}
	return 0;
}

d365: 10336 - Rank the Languages

解題心得

我反而不是卡bfs，而是卡再怎麼輸出好久，最開始是用map紀錄，但要依照value輸出好麻煩。

程式碼

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

int h, w;
void bfs(vector<vector<char>>& map, int x, int y, char c)
{
	map[y][x] = '@';
	if (x - 1 >= 0 && map[y][x - 1] == c) bfs(map, x - 1, y, c);
	if (x + 1 < w && map[y][x + 1] == c) bfs(map, x + 1, y, c);
	if (y - 1 >= 0 && map[y - 1][x] == c) bfs(map, x, y - 1, c);
	if (y + 1 < h && map[y + 1][x] == c) bfs(map, x, y + 1, c);
}


int main()
{
	int n;
	cin >> n;
	for (int round = 1; round <= n; round++)
	{
		cin >> h >> w;
		int dict[26] = { 0 };
		vector<vector<char>> map(h, vector<char>(w, '@'));
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
				cin >> map[i][j];
		}
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				if (map[i][j] != '@')
				{
					dict[map[i][j] - 'a']++;
					bfs(map, j, i, map[i][j]);
				}
			}
		}
		cout << "World #" << round << endl;
		int maxCount = 0;
		for (int i = 0; i < 26; i++)
			maxCount = max(maxCount, dict[i]);
		while (maxCount)
		{
			for (int i = 0; i < 26; i++)
			{
				if (maxCount == dict[i])
					cout << char('a' + i) << ": " << dict[i] << endl;
			}
			maxCount--;
		}
	}
	return 0;
}

Uva 10267: Graphical Editor

解題心得

看起來很麻煩，但基本上只要照著題目敘述做就好，最難的部分只有DFS。

程式碼

#include <iostream>
using namespace std;

char table[101][101];
int m, n;

void fill(int x, int y, char c, char currentColor)
{
	if(currentColor==c) return;
	table[y][x]=c;
	
	if(x>=2 && table[y][x-1]==currentColor) fill(x-1,y,c,currentColor);
	if(x<m && table[y][x+1]==currentColor) fill(x+1,y,c,currentColor);
	if(y>=2 && table[y-1][x]==currentColor) fill(x,y-1,c,currentColor);
	if(y<n && table[y+1][x]==currentColor) fill(x,y+1,c,currentColor);
}

int main()
{
	char cmd,c;
	int x1,x2,y1,y2;
	string name,s;
	while(cin>>cmd)
	{
		if(cmd=='I')
		{
			cin>>m>>n;
			for(int i=0;i<=n;i++)
				for(int j=0;j<=m;j++)
					table[i][j]='O';
		}
		else if(cmd=='L')
		{
			cin>>x1>>y1>>c;
			table[y1][x1]=c;
		}
		else if(cmd=='S')
		{
			cin>>name;
			cout<<name<<endl;
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=m;j++)
					cout<<table[i][j];
				cout<<endl;
			}
					
		}
		else if(cmd=='F')
		{
			cin>>x1>>y1>>c;
			fill(x1,y1,c,table[y1][x1]);
		}
		else if(cmd=='V')
		{
			cin>>x1>>y1>>y2>>c;
			if(y1>y2) swap(y1,y2);
			for(int i=y1;i<=y2;i++)
				table[i][x1]=c;
		}
		else if(cmd=='H')
		{
			cin>>x1>>x2>>y1>>c;
			if(x1>x2) swap(x1,x2);
			for(int i=x1;i<=x2;i++)
				table[y1][i]=c;
		}
		else if(cmd=='K')
		{
			cin>>x1>>y1>>x2>>y2>>c;
			for(int i=y1;i<=y2;i++)
				for(int j=x1;j<=x2;j++)
					table[i][j]=c;
		}
		else if(cmd=='C')
		{
			for(int i=0;i<101;i++)
				for(int j=0;j<101;j++)
					table[i][j]='O';
		}
		else if(cmd=='X')
			break;
		else
		{
			cin.ignore();
			getline(cin,s);
		}
	}
}

Uva 389: Basically Speaking

解題心得

先把數字轉回十進位，再轉成要求的進位制表示法。

程式碼

#include <iostream>
using namespace std;

int to_decimal(string s, int base)
{
	int ans = 0;
	for (int i = 0; i < s.size(); i++)
	{
		if ('0' <= s[i] && s[i] <= '9')
			ans = ans * base + s[i] - '0';
		else
			ans = ans * base + s[i] - 'A' + 10;
	}
	return ans;
}
string convert(int n, int base)
{
	string s = "";
	while (n > 0)
	{
		int tmp = n % base;
		if (tmp >= 10)
			s = char(tmp - 10 + 'A') + s;
		else
			s = char(tmp + '0') + s;
		n /= base;
	}
	while (s.size() < 7)
		s = "0" + s;
	while (s.size() > 7)
		s = s.erase(0, 1);
	return s;
}

int main()
{
	string origin;
	int origin_base, new_base;
	while (cin >> origin)
	{
		cin.ignore();
		cin >> origin_base >> new_base;
		int decimal = to_decimal(origin, origin_base);
		cout << convert(decimal, new_base) << endl;
	}
	return 0;
}

Uva 458: The Decoder

解題心得

CPE第二題居然比第一題簡單

程式碼

#include <iostream>
using namespace std;

int main()
{
	string s;
	while(cin>>s)
	{
		for(int i=0;i<s.size();i++)
			cout<<char(s[i]-7);
		cout<<endl;
	}
	return 0;
}

Uva 10050: Hartals

解題心得

如果先判斷日期是不是週五週六，反而會超時QQ

程式碼

#include <iostream>
using namespace std;

int main()
{
	int T,n,p,h[101]={0};
	cin>>T;
	while(T--)
	{
		int ans=0;
		cin>>n>>p;
		for(int i=0;i<p;i++)
			cin>>h[i];
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<p;j++)
			{
				if(i%h[j]==0&&i%7!=0&&i%7!=6)
				{
					ans++;
					break;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

Uva 11960: Divisor Game

解題心得

原本的想法是用質數篩法建質數表，然後一個個用質因數分解找因數，因為一個數的因數數量就是質因數次方加一的乘積。

例：36 = 2^2 + 3^2，其因數數量為(2+1)*(2+1)=9。背後原因很簡單就不贅述。

不過寫完後發現會TLE，只好放棄。

參考了CPE提供的參考解法，發現解法其實很簡單。首先同樣要建表，這次建的是因數表。何謂因數？就是某數可以整除的數。反過來想，把某數的倍數與自己通通都加一，因為一定能整除。

為了近一步縮短時間，提前建好答案表。答案表紀錄從1~i的範圍內，因數數量最多的是誰。注意若數量相同，也要更新。

講起來很容易，但就是想不到啊。

程式碼

#include <iostream>
using namespace std;

#define SIZE 1000001

int table[SIZE] = { 0 }, ans[SIZE] = { 0 };

int main()
{
	for (int i = 1; i < SIZE; i++)
	{
		for (int j = i; j < SIZE; j += i)
			table[j]++;
	}
	int maxIndex = 1, maxCount = 0;
	for (int i = 1; i < SIZE; i++)
	{
		if (table[i] >= maxCount)
		{
			maxIndex = i;
			maxCount = table[i];
		}
		ans[i] = maxIndex;
	}
	
	int T, n;
	cin >> T;
	while (T--)
	{
		cin >> n;
		cout << ans[n] << endl;
	}
	return 0;
}

Uva 11536: Smallest Sub-Array

解題心得

參考網路解法才寫出來。

這題似乎要用到two pointer的概念的變化題。

先假設用一個queue來記錄所有sequence中1~k數字的index，以及countk紀錄當下蒐集到1~k中的總共幾個數字，跟一個array來記錄i最後出現的位置。

每次遇到1~k數字，就先丟進queue中。接著檢查是否第一次遇到這個數字(有沒有在queue中，也就是有沒有在highlight起來的範圍內)，若沒有，則更新countk。最後，我們要檢查highlight範圍左側是不是要變化了，判斷方法是看範圍內的最左側，若去掉該位置，依然能保有1~k的數字，那就可以放棄，一直重覆到不能為止。

那又要怎麼確保會找到最短長度呢？首先我們知道當countk==k時就是一組解，而我們的解法是從頭到尾掃過一次並且動態更新，那麼只要每次都檢查當前的解是否更小即可。

另外我在比較cpe提供的參考解法與網路其他人解法時，一開始不懂為何countk只要++，不考慮--的情況。這是因為只有一開始才是還沒找到解的狀態，只要一找到符合的解，只會不斷解查是不是要更新邊界，但也會確保始終是保持1~k數字的區間。

程式碼 

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

int seq[1000001] = { 1,2,3 };

int main()
{
	int T;
	cin >> T;
	for (int round = 1; round <= T; round++)
	{
		int n, m, k;
		cin >> n >> m >> k;

		for (int i = 3; i < n; i++)
			seq[i] = (seq[i - 1] + seq[i - 2] + seq[i - 3]) % m + 1;

		queue<int> q;
		int countK = 0, last_pos[101] = { 0 }, ans = 1000001;
		for (int i = 0; i < 101; i++) last_pos[i] = -1;
		for (int i = 0; i < n; i++)
		{
			if (seq[i] <= k)
			{
				q.push(i);
				if (last_pos[seq[i]] == -1) countK++;
				last_pos[seq[i]] = i;

				while (q.front() != last_pos[seq[q.front()]])
					q.pop();
				if (countK == k)
					ans = min(ans, i - q.front() + 1);
			}
		}
		cout << "Case " << round << ": ";
		if (ans == 1000001) cout << "sequence nai" << endl;
		else cout << ans << endl;
	}
	return 0;
}

Uva 10415: Eb Alto Saxophone Player

解題心得

暴力解

程式碼

#include <iostream>
using namespace std;

int main()
{
	string c="0111001111", d="0111001110", e="0111001100", f="0111001000", g="0111000000",
		a="0110000000", b="0100000000", C="0010000000", D="1111001110", E="1111001100",
		F="1111001000", G="1111000000", A="1110000000", B="1100000000";
	int t;
	cin>>t;
	while(t--)
	{
		string s, now="0000000000", next;
		int count[10]={0};
		cin>>s;
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='c') next=c;
			else if(s[i]=='d') next=d;
			else if(s[i]=='e') next=e;
			else if(s[i]=='f') next=f;
			else if(s[i]=='g') next=g;
			else if(s[i]=='a') next=a;
			else if(s[i]=='b') next=b;
			else if(s[i]=='C') next=C;
			else if(s[i]=='D') next=D;
			else if(s[i]=='E') next=E;
			else if(s[i]=='F') next=F;
			else if(s[i]=='G') next=G;
			else if(s[i]=='A') next=A;
			else if(s[i]=='B') next=B;
			
			for(int i=0;i<10;i++)
			{
				if(now[i]=='0'&&next[i]=='1')
					count[i]++;
			}
			now=next;
			
		}
		
		for(int i=0;i<10;i++)
		{
			if(i!=9) cout<<count[i]<<" ";
			else cout<<count[i]<<endl;
		}
	}
	return 0;
}

Uva 10188: Automated Judge Script

解題心得

比對解答與提交答案的部分，主要是一個字元一個字元檢查。如果兩個字元都一樣，那就往下一個字元繼續看；如果其中一個是空白但另一個不是，則可能是PE，就先標記起來然後跳過空白；如果字元不一樣，而且也不是因為空白，那就是WA，可以直接跳出迴圈。

比較麻煩的是換行的部分，會造成PE誤判成AC，因為好像檢查不到「\n」。我想說這種狀況，會出現在原本被判AC，但因為換行，導致解答跟提交答案的行數不同，就從這裡判斷就好了。

程式碼

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

int main()
{
	int n, m, count = 1;
	while (cin >> n)
	{
		if (n == 0) break;

		cin.ignore();
		string solution[100], team_output[100];
		int solution_len = 0;

		// read input
		for (int i = 0; i < n; i++)
		{
			getline(cin, solution[i]);
			solution_len += solution[i].size();
		}
		cin >> m;
		cin.ignore();
		for (int i = 0; i < m; i++)
			getline(cin, team_output[i]);

		// judge
		bool pe = false, wa = false;
		int i = 0, j = 0, len1 = 0, len2 = 0;
		while (i < n)
		{
			while (len1 < solution[i].size()) // && len2<team_output[i].size()
			{
				if (solution[i][len1] == team_output[j][len2])
					len1++, len2++;
				else if (solution[i][len1] == ' ' || solution[i][len1] == '\n')
				{
					len1++;
					pe = true;
				}
				else if (team_output[j][len2] == ' ' || team_output[j][len2] == '\n')
				{
					len2++;
					pe = true;
				}
				else
				{
					wa = true;
					break;
				}

				if (len2 >= team_output[j].size())
					j++, len2 = 0;
			}
			i++; len1 = 0;
		}
		cout << "Run #" << count++ << ": ";
		if (wa)
			cout << "Wrong Answer ";
		else if (pe || n!=m)
			cout << "Presentation Error ";
		else
			cout << "Accepted ";
		cout << solution_len << endl;

	}
	return 0;
}

Uva11689 Soda Surpler

解題心得

照著題目敘述寫就好了

程式碼

#include <iostream>
using namespace std;

int main()
{
	int N;
	cin>>N;
	while(N--)
	{
		int e, f, c, total=0,bottle=0;
		cin>>e>>f>>c;
		bottle = e+f;
		
		while(bottle>=c)
		{
			int tmp = bottle/c; // can buy now many soda

			bottle -= tmp*c; // use the empty bottle to buy soda
			bottle += tmp; // new empty bottle
			total += tmp; // update drink soda amount
		}
		cout<<total<<endl;
	}
	return 0;
}

b563: 3.魔法學校交換生問題

解題心得

檢查b校有沒有a校的申請，有的話案件成立數加一，沒有的話紀錄下來a校想去b校。

程式碼

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

int main()
{
	int n;
	while (cin >> n)
	{
		map<int, map<int,int>> record;
		int total = 0;
		while (n--)
		{
			int a, b;
			cin >> a >> b;
			
			if (record.count(b) && record[b].count(a) && record[b][a] > 0)
			{
				total++;
				record[b][a]--;
			}
			else
			{
				if (!record.count(a) || !record[a].count(b))
					record[a][b] = 1;
				else
					record[a][b]++;
			}
		}
		cout << total << endl;
		
	}
	return 0;
}

a121: 質數又來囉

解題心得

注意1的狀況。

程式碼

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

int main()
{
	int a, b;
	while (cin >> a >> b)
	{
		int count = 0;
		for (int i = a; i <= b; i++)
		{
			if (i == 1) continue;
			bool isPrime = true;
			for (int j = 2; j <= sqrt(i); j++)
			{
				if (i % j == 0)
				{
					isPrime = false;
					break;
				}
			}
			if (isPrime) count++;
		}
		cout << count << endl;
	}
	return 0;
}

UVA725

解題心得

一開始看到這題完全沒有頭緒，看了CPE提供的解說影片才有想法。

首先，用列舉的方式窮舉所有可能，如果該數字組合符合等式，再檢查數字是否重複。判斷等式成立與否也未必要用除的，用分母乘以N得到分子，這樣能縮小窮舉範圍。

思考到這裡，剩下的就是枚舉所有可能的分母，只要乘以N必定能讓等式成立，而分母的窮舉範圍其實可以進一步縮減到01234~98765。

太久沒解題，最後還卡在換行上XD

程式碼

#include <iostream>
using namespace std;

bool isValid(int a, int b)
{
	if(a>99999 || b>99999) return false;
	
	int count[10] = {0};
	if(a<10000) count[0]++;
	if(b<10000) count[0]++;
	while(a>0)
	{
		count[a%10]++;
		a/=10;
	}
	while(b>0)
	{
		count[b%10]++;
		b/=10;
	}
	for(int i=0;i<10;i++)
	{
		if(count[i]!=1)
			return false;
	}
	return true;
}

int main()
{
	int n;
	bool isFirst=true;
	
	while(cin>>n)
	{
		if(n==0) break;
		
		bool hasAns=false;
		
		if(isFirst) isFirst=false;
		else cout<<endl;
		
		for(int i=1234;i<=98765;i++)
		{
			int j = i * n;
			if(isValid(i, j))
			{
				hasAns=true;
				if(j<10000) cout<<"0"<<j<<" / ";
				else cout<<j<<" / ";
				if(i<10000) cout<<"0"<<i<<" = "<<n<<endl;
				else cout<<i<<" = "<<n<<endl;
			}
		}
		if(!hasAns) cout<<"There are no solutions for "<<n<<"."<<endl;
		
		
	}
	return 0;
}

UVA12218

解題心得

照著題目敘述做。

如果輪到誰，誰卻跳出迴圈，就代表輸了。

程式碼

#include <iostream>
using namespace std;

int sum_of_digits(string s)
{
	int sum=0;
	for(int i=0;i<s.length();i++)
		sum+=s[i]-'0';
	return sum;
}
int can_remove(string s)
{
	if(s.length()==0) return -1;
	
	int sum=sum_of_digits(s);
	for(int i=0;i<s.length();i++)
	{
		if((sum-(s[i]-'0'))%3==0)
			return i;
	}
	return -1;
}

int main()
{
	int T;
	cin>>T;
	
	for(int round=1;round<=T;round++)
	{
		bool isT=false; // s first
		string s;
		cin>>s;
		
		while(1){
			int index=can_remove(s);
			if(index==-1) break;
			s=s.erase(index,1);
			isT=!isT;
		}
		
		cout<<"Case "<<round<<": ";
		cout<< (isT ? "S" : "T") << endl;
	}
	return 0;
}

UVA10921

解題心得

照著題目敘述寫就好了。

程式碼

#include <iostream>
using namespace std;

int find_table(char c)
{
	if(c=='A' || c=='B' || c=='C') return 2;
	else if(c=='D' || c=='E' || c=='F') return 3;
	else if(c=='G' || c=='H' || c=='I') return 4;
	else if(c=='J' || c=='K' || c=='L') return 5;
	else if(c=='M' || c=='N' || c=='O') return 6;
	else if(c=='P' || c=='Q' || c=='R' || c=='S') return 7;
	else if(c=='T' || c=='U' || c=='V') return 8;
	else if(c=='W' || c=='X' || c=='Y' || c=='Z') return 9;
}
int main()
{
	string s;
	while(cin>>s)
	{
		int capital=0, hyphen=0;
		for(int i=0;i<s.length();i++)
		{
			if(s[i]=='-' || s[i]=='1' || s[i]=='0')
				cout<<s[i];
			else
				cout<<find_table(s[i]);
				
			if(s[i]=='-') hyphen++;
			if(isupper(s[i])) capital++; 
		}
		cout<<" "<<capital<<" "<<hyphen<<endl;
	}
	return 0;
}

UVA12019

解題心得

好久沒碰日期相關的題目了，真的好討厭這類型......

程式碼

#include <iostream>
using namespace std;

int main()
{
	int calander[366]={0}, today=6, months[13]={0,31,59,90,120,151,181,212,243,273,304,334,365};
	for(int i=1;i<=365;i++)
	{
		calander[i]=today;
		today++;
		if(today==8) today=1;
	}
	
	int T, M, D;
	cin>>T;
	
	while(T--)
	{
		cin>>M>>D;
		int day=calander[months[M-1]+D];
		if(day==1) cout<<"Monday"<<endl;
		else if(day==2) cout<<"Tuesday"<<endl;
		else if(day==3) cout<<"Wednesday"<<endl;
		else if(day==4) cout<<"Thursday"<<endl;
		else if(day==5) cout<<"Friday"<<endl;
		else if(day==6) cout<<"Saturday"<<endl;
		else cout<<"Sunday"<<endl;
	}
	return 0;
}

UVa380

程式碼

因為自己電腦用瘋狂程式寫code好像無法使用c++11的編譯器(?)，所以才自己寫了stoi。

我用 struct 來紀錄怎麼forward，用vector紀錄全部的forward資訊，以及forward的過程中經過哪些電話號碼，如果會forward到已經記錄過的就回傳9999。

至於判斷時間起迄的部分，除了一般的狀況外，還要考慮時間可能跨到明年，也就是結束時間比開始時間小的情況。

還有一個部份是要確認長長的forward鍊已經到了最後，要怎麼確認呢？我的想法是只要該輪有被更動過，下次就要再檢查一次，直到某輪把所有forward資訊看過一次都不用，那就結束。

解題心得

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

struct forward_call
{
	string source, target;
	int start, end;
};

int stoi(string s)
{
	int n=0;
	for(int i=0;i<s.length();i++)
	{
		n=n*10+s[i]-'0';
	}
	return n;
}
bool in_history(vector<string> history, string s)
{
	for(int i=0;i<history.size();i++)
	{
		if(history[i]==s)
			return true;
	}
	return false;
}

bool in_time(int start, int end, string time)
{
	if(start<=end)
		if(start<=stoi(time) && stoi(time)<=end) return true;
	else
		if(!(end<=stoi(time) && stoi(time)<=start)) return true;
	return false;
}
int main()
{
	int T;
	cin>>T;
	
	cout<<"CALL FORWARDING OUTPUT"<<endl;
	for(int round=1; round<=T; round++)
	{
		string s, t, d, target;
		string time, extension;
		vector<forward_call> sys;
		
		cout<<"SYSTEM "<<round<<endl;
		while(cin>>s)
		{
			if(s=="0000")
				break;
			cin>>t>>d>>target;
			forward_call call;
			call.source=s;call.target=target;call.start=stoi(t);call.end=stoi(t)+stoi(d);
			sys.push_back(call);
		}
		while(cin>>time)
		{
			if(time=="9000")
				break;
			cin>>extension;
			string initial_extension=extension;
			vector<string> history;
			history.push_back(initial_extension);
			
			bool isFin=true;
			
			do{
				isFin=true;
				for(int i=0;i<sys.size();i++)
				{
					if(sys[i].source==extension && 
					sys[i].start <= stoi(time) && stoi(time) <= sys[i].end)
					{
						isFin=false;
						if(in_history(history, sys[i].target))
						{
							extension = "9999";
							break;
						}
						extension=sys[i].target;
						history.push_back(sys[i].target);
					}
				}
			}while(!isFin);
			
			cout<<"AT " << time << " CALL TO " << initial_extension << " RINGS " << extension << endl;
		}
	}
	cout<<"END OF OUTPUT"<<endl;
	return 0;
}

UVa12869

解題心得

第一次解這種類型的題目。

題目問在給定範圍的階乘內數字結尾有幾個連續的零。我們都知道零代表著10，也就是2*5，如此可推論每當有一組2跟5時就會多一個零。只要能知道有多少個2、5就能知道答案，又因為5是每五個數字出現一次，2只要每2個數字就會出現一次，可知5才是主宰零出現次數的關鍵。

因此這題只要算5出現了幾次，也就是除以5就好了。

程式碼

#include <iostream>
using namespace std;

int main()
{
	long long int low, high;
	while(cin>>low>>high)
	{
		if(low==0&&high==0) break;
		
		cout<<high/5 - low/5 + 1<<endl;
	}
	return 0;
}

UVa12970

解題心得

表面上看起來很容易，但牽扯到數字約分就比較複雜。

要記得gcd怎麼寫。

程式碼

#include <iostream>
using namespace std;

long long int gcd(long long int a, long long int b)
{
	while((a%=b)!=0 && (b%=a)!=0);
	return a+b;
}
int main()
{
	int count=1;
	long long int v1, d1, v2, d2;
	while(cin>>v1>>d1>>v2>>d2)
	{
		if(v1==0 && d1==0 && v2==0 && d2==0) break;
		
		cout<<"Case #"<<count++<<": ";
		if(float(d1)/v1 < float(d2)/v2)
			cout<<"You owe me a beer!"<<endl;
		else
			cout<<"No beer for the captain."<<endl;
			
		cout<<"Avg. arrival time: ";
		long long int up, down,_gcd;
		up=d1*v2 + d2*v1;
		down=2*v1*v2;
		_gcd=gcd(up,down);
		
		up/=_gcd, down/=_gcd;
		if(down==1)
			cout<<up<<endl;
		else
			cout<<up<<"/"<<down<<endl;
	}
	return 0;
}

git 指令筆記

push a folder

git remote add origin https://gitlab.com/xxxxx/test.git

git add .

git commit -m “Initial commit”

git push -u origin master  # git push <remote-repo> <branch-name>

view repo's history

git log

git log --oneline

git log --stat # display the files that have been changed in the commit, as well as the number of lines that have been added or deleted

git log -p # display the actual changes made to a file

git log -p <SHA>

git show

git show <SHA>

git diff # see changes that have been made but haven't been committed

git log --oneline --graph --decorate --all

git log --author="Richard Kalehoff"

git log --grep="border radius issue in Safari"

branch

git branch # list all branch

git branch sidebar # create new branch called sidebar

git checkout sidebar # switch to branch sidebar

git branch -d sidebar # delete

git checkout -b footer master # create new branch and switch to it

git checkout -b footer <SHA>

merge

git merge <branch-name> # merge <branch-name> into current branch

# to fix conflict:

# open editor and fixed it

# commit again

amend commit

git commit --amend

# if  Working Directory is clean

# change the commit message

# else

# update all change within the staging area

git revert <SHA-of-commit-to-revert>

Udacity Git Commit Message Style Guide

UVa10222

解題心得

太久沒寫C++，差點忘了字串處理的部分。

程式碼

#include <iostream>
using namespace std;

int main()
{
	string table = "qwertyuiop[]\\asdfghjkl;'zxcvbnm,./";
	int T;
	cin>>T;
	cin.ignore();
	
	while(T--)
	{
		string s;
		getline(cin,s);
		
		for(int i=0;i<s.length();i++)
		{
			if(isupper(s[i])) s[i] = (s[i]-'A')+'a';
			if(s[i]==' ')
			{
				cout<<" ";
				continue;
			}
			
			for(int j=0;j<table.length();j++)
			{
				if(table[j]==s[i])
				{
					cout<<table[((j-2)+table.length())%table.length()];
				}
			}
		}
		cout<<endl;
	}
	return 0;
}

UVa12959

解題心得

沒有心得

程式碼

#include <iostream>
using namespace std;

int main()
{
	int T;
	cin>>T;
	
	while(T--)
	{
		int n, max=0, ans=-999999,temp;
		cin>>n;

		for(int i=0;i<n;i++)
		{
			cin>>temp;
			
			if(i==0)
			{
				max = temp;
				continue;
			}
			
			if(max-temp>ans)
				ans = max-temp;
			if(temp>max)
				max=temp;
		}
		cout<<ans<<endl;
	}
	return 0;
}

UVa11078

解題心得

不能用暴力解，會TLE。

可以一邊讀新的數字進來，一邊紀錄是不是目前遇到的最大值，並且把之前紀錄的最大值跟當下吃到的數字比較，如果比較大就記起來。

程式碼

#include <iostream>
using namespace std;

int main()
{
	int T;
	cin>>T;
	
	while(T--)
	{
		int n, max=0, ans=-999999,temp;
		cin>>n;

		for(int i=0;i<n;i++)
		{
			cin>>temp;
			
			if(i==0)
			{
				max = temp;
				continue;
			}
			
			if(max-temp>ans)
				ans = max-temp;
			if(temp>max)
				max=temp;
		}
		cout<<ans<<endl;
	}
	return 0;
}

UVa118

解題心得

嗚嗚

程式碼

#include <iostream>
using namespace std;

int main()
{
	int Xmax, Ymax, x, y, grid[51][51] = { 0 };
	char orient;
	string s;

	cin >> Xmax >> Ymax;
	while (cin >> x >> y >> orient)
	{
		bool isLost = false;

		cin >> s;
		for (int i = 0; i < s.length(); i++)
		{
			if (s[i] == 'L')
			{
				if (orient == 'N') orient = 'W';
				else if (orient == 'E') orient = 'N';
				else if (orient == 'S') orient = 'E';
				else if (orient == 'W') orient = 'S';
			}
			else if (s[i] == 'R')
			{
				if (orient == 'N') orient = 'E';
				else if (orient == 'E') orient = 'S';
				else if (orient == 'S') orient = 'W';
				else if (orient == 'W') orient = 'N';
			}
			else
			{
				int next_x = x, next_y = y;
				if (orient == 'N') next_y++;
				else if (orient == 'E') next_x++;
				else if (orient == 'S') next_y--;
				else if (orient == 'W') next_x--;

				if (next_x<0 || next_y<0 || next_x>Xmax || next_y>Ymax)
				{
					if (grid[x][y] == 1)
						continue;

					isLost = true;
					grid[x][y] = 1;
					break;
				}
				x = next_x, y = next_y;
			}
			
		}
		cout << x << " " << y << " " << orient;
		if (isLost)
			cout << " LOST";
		cout << endl;
	}
	return 0;
}

UVa11728

解題心得

暴力解

程式碼

#include <iostream>
using namespace std;

int factor_sum(int n)
{
	int sum = 0;
	
	for (int i = 1; i <= n; i++)
	{
		if (n % i == 0)
			sum += i;
	}
	return sum;
}

int main()
{
	int S, count = 1;
	while (cin >> S)
	{
		if (S == 0) break;
		cout << "Case " << count++ << ": ";

		int ans = -1;
		for (int i = 1; i < S; i++)
		{
			if (factor_sum(i) == S)
			{
				ans = i;
			}
		}
		if (S == 1)
			ans = 1;
		cout << ans << endl;
	}
	return 0;
}

UVa1260

解題心得

沒有心得

程式碼

#include <iostream>
using namespace std;

int main()
{
	int T, n;
	cin>>T;
	while(T--)
	{
		cin>>n;
		int sales[1001]={0};
		for(int i=0;i<n;i++)
		{
			cin>>sales[i];
		}
		int ans=0;
		for(int i=1;i<n;i++)
		{
			for(int j=0;j<i;j++)
			{
				if(sales[j]<=sales[i])
					ans++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

UVa12650

解題心得

沒有心得

程式碼

#include <iostream>
using namespace std;

int main()
{
	int N,R;
	while(cin>>N>>R)
	{
		int card[N+1]={0}, flag=0;
		for(int i=0;i<R;i++)
		{
			cin>>flag;
			card[flag]=1;
		}
		if(N==R)
			cout<<"*"<<endl;
		else
		{
			for(int i=1;i<=N;i++)
			{
				if(card[i]==0)
					cout<<i<<" ";
			}
			cout<<endl;
		}
	}
	return 0;
}