文章目录

• 试题 A: 跑步训练
• 试题 B: 纪念日
• 试题 C: 合并检测
• 试题 D: REPEAT 程序
• 试题 F: 整除序列
• 试题 G: 解码
• 试题 H: 走方格
• 试题 I: 整数拼接
• 试题 J: 网络分析

试题 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 ∗ n ∗ k n/k+0.01*n*k n/k+0.01∗n∗k

提取n，有
n ∗ ( 1 / k + 0.01 ∗ k ) n*(1/k+0.01*k) n∗(1/k+0.01∗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 ) O(n^2) O(n2)，需要进行优化
如果 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 ( n m ) O(nm) 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;
}