试题 A: 跑步训练
答案：3880
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
int n = 10000, minu, sec;
for (int i = 0; ; i++) {
if (i % 2 == 0) {
// 跑
if (n > 600) {
n -= 600;
} else {
// 体力不足跑完一分钟
minu = i;
sec = n / 10;
break;
}
} else {
// 休息
n += 300;
}
}
cout << (minu * 60 + sec) << 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;
}
转载：https://blog.csdn.net/weixin_43772166/article/details/108237718
查看评论