試題 A: 跑步訓練

答案：65

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	int n = 10000, i;
	for (i = 0; n > 0; i++) {
		if (i % 2 == 0) {
			n -= 600;
		} else {
			n += 300;
		}
	}
	cout << i << endl;
	
	return 0;
}

試題 B: 紀念日

答案：52038720

可以通過excel來計算出，兩個日期相差36138天

所以答案為：36138*24*60=52038720

試題 C: 合併檢測

答案：10

假設有n個人，需要使用的試劑盒有
$$n/k+0.01\ast n\ast k$$

提取n，有
$$n\ast (1/k+0.01\ast k)$$

所以，當k=10時，有最小值

試題 D: REPEAT 程式

這個還不會 QAQ

試題 F: 整除序列

模擬

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(void)
{
	ll n;
	cin >> n;
	cout << n;
	n /= 2;
	
	while (n > 0) {
		cout << " " << n;
		n /= 2;
	}
	cout << endl;
	
	return 0;
}

試題 G: 解碼

模擬，將簡寫的字串展開

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(void)
{
	string s;
	cin >> s;
	int n = s.size(), num;
	for (int i = 0; i < n; i++) {
		if (i != n - 1 && s[i + 1] >= '1' && s[i + 1] <= '9') {
			num = s[i + 1] - '0';
			while (num--) {
				cout << s[i];
			}
			i++;
		} else {
			cout << s[i];
		}
	}
	cout << endl;
	
	return 0;
}

試題 H: 走方格

簡單的動態規劃

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int dp[35][35];

int main(void)
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		dp[i][1] = dp[1][i] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 2; j <= m; j++) {
			if (i % 2 == 0 && j % 2 == 0)
				dp[i][j] = 0;
			else
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		}
	}
	cout << dp[n][m] << endl;
	
	return 0;
}

試題 I: 整數拼接

直接進行拼接的複雜度為 $O(n^2)$，需要進行優化
如果 x 和 y 進行拼接，拼接後個位上的數為 y 個位上的數
可以先計算出 k 的 0——9 倍個位上的數，並記錄到陣列裡
如果 y 個位上的數存在於陣列，說明拼接後的數位有可能是 k 的倍數，從而進行拼接判斷
如果 y 個位上的數不在陣列內，說明拼接後的陣列不可能是 k 的倍數，直接跳過即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;

ll a[N], num[15];
bool vis[15];

ll connect(ll a, ll b)
{
	ll bb = b;
	while (bb != 0) {
		a *= 10;
		bb /= 10;
	}
	a += b;
	
	return a;
} 

int main(void)
{
	int n, k, res = 0;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	
	for (int i = 0; i <= 9; i++)
		vis[(i * k) % 10] = 1;
	
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			ll x = a[i], y = a[j];
			if (vis[y % 10] && connect(x, y) % k == 0)
				res++;
			if (vis[x % 10] && connect(y, x) % k == 0)
				res++;
		}
	}
	cout << res << endl;
	
	return 0;
}

試題 J: 網路分析

這道題我只會用並查集的暴力做法，複雜度為$O(nm)$
如果是1，就用並查集進行合併。如果是2，就遍歷所有元素，如果在一個集合內，就加上對應的值。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5;

int n, m;
ll fa[N], sum[N];

void init()
{
	for (int i = 1; i <= n; i++)
		fa[i] = i;
}

int find(int x)
{
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}

void unite(int x, int y)
{
	x = find(x), y = find(y);
	fa[x] = y;
}

int main(void)
{
	int t, a, b;
	cin >> n >> m;
	init();
	while (m--) {
		cin >> t >> a >> b;
		if (t == 1) {
			unite(a, b);
		} else {
			for (int i = 1; i <= n; i++) {
				if (find(a) == find(i)) {
					sum[i] += b;
				}
			}
		}
	}
	for (int i = 1; i <= n - 1; i++)
		cout << sum[i] << " ";
	cout << sum[n] << endl;
	
	return 0;
}