阿風的學業紀錄: 2022

2022年12月4日星期日

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!

2022年7月18日星期一

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

2022年6月14日星期二

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

2022年6月13日星期一

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

2022年6月12日星期日

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

2022年6月11日星期六

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

2022年6月10日星期五

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

2022年6月9日星期四

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

2022年3月7日星期一

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

2022年3月6日星期日

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

2022年3月5日星期六

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

2022年3月3日星期四

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

2022年2月28日星期一

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

2022年2月23日星期三

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

2022年2月21日星期一

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

2022年2月20日星期日

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

2022年2月19日星期六

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

2022年2月17日星期四

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

2022年2月16日星期三

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

2022年2月15日星期二

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

2022年2月14日星期一

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

2022年2月11日星期五

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

2022年2月7日星期一

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

2022年2月6日星期日

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

2022年2月4日星期五

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

2022年2月3日星期四

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

2022年2月2日星期三

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

2022年2月1日星期二

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

2022年1月29日星期六

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

2022年1月28日星期五

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

2022年1月27日星期四

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

2022年1月25日星期二

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

2022年1月24日星期一

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

2022年1月20日星期四

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

2022年1月19日星期三

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

2022年1月18日星期二

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

訂閱：文章 (Atom)

2022年12月4日 星期日

2022年7月18日 星期一

2022年6月14日 星期二

2022年6月13日 星期一

2022年6月12日 星期日

2022年6月11日 星期六

2022年6月10日 星期五

2022年6月9日 星期四

2022年3月7日 星期一

2022年3月6日 星期日

2022年3月5日 星期六

2022年3月3日 星期四

2022年2月28日 星期一

2022年2月23日 星期三

2022年2月21日 星期一

2022年2月20日 星期日

2022年2月19日 星期六

2022年2月17日 星期四

2022年2月16日 星期三

2022年2月15日 星期二

2022年2月14日 星期一

2022年2月11日 星期五

2022年2月7日 星期一

2022年2月6日 星期日

2022年2月4日 星期五

2022年2月3日 星期四

2022年2月2日 星期三

2022年2月1日 星期二

2022年1月29日 星期六

2022年1月28日 星期五

2022年1月27日 星期四

2022年1月25日 星期二

2022年1月24日 星期一

2022年1月20日 星期四

2022年1月19日 星期三

2022年1月18日 星期二

2022年12月4日星期日

2022年7月18日星期一

2022年6月14日星期二

2022年6月13日星期一

2022年6月12日星期日

2022年6月11日星期六

2022年6月10日星期五

2022年6月9日星期四

2022年3月7日星期一

2022年3月6日星期日

2022年3月5日星期六

2022年3月3日星期四

2022年2月28日星期一

2022年2月23日星期三

2022年2月21日星期一

2022年2月20日星期日

2022年2月19日星期六

2022年2月17日星期四

2022年2月16日星期三

2022年2月15日星期二

2022年2月14日星期一

2022年2月11日星期五

2022年2月7日星期一

2022年2月6日星期日

2022年2月4日星期五

2022年2月3日星期四

2022年2月2日星期三

2022年2月1日星期二

2022年1月29日星期六

2022年1月28日星期五

2022年1月27日星期四

2022年1月25日星期二

2022年1月24日星期一

2022年1月20日星期四

2022年1月19日星期三

2022年1月18日星期二