2024第三届大学生算法大赛 真题训练一 解题报告 | 珂学家

---

前言

---

题解

这是第三届大学生算法大赛(第二届为清华社杯)的赛前练习赛一.

这是上界比赛的体验报告: 2023第二届“清华社杯”大学生算法大赛 解题报告(流水账版) | 珂学家，个人还是非常推荐这个比赛。

难度分布：4 easy/4 mid-hard/2 hard

赛前练习赛一，出自题库的每日一题，相对比较简单，又特别偏数学题。

所以这个练习赛一，感觉代表性不是那么强，但是又能代表官方的一种出题倾向吧。

---

A. 区间内的真素数

思路：质数筛/质数判定

因为数据范围不是很大，所以两类思路都可以

用欧拉筛的时候，需要注意范围（翻转会变大）

区间筛也可以试试

#include <bits/stdc++.h>using namespace std;const int SZ = (int)1e6;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int l, r;cin >> l >> r;// 欧拉筛vector<int> primes;vector<bool> vis(SZ + 1, true);vis[0] = vis[1] = false;for (int i = 2; i <= SZ; i++) {if (vis[i]) {primes.push_back(i);}for (int v: primes) {if (i > SZ / v) break;vis[i * v] = false;if (i % v == 0) break;}}function<bool(int)> checker = [&](int v) {int rv = 0;while (v > 0) {int r = v % 10;rv = rv * 10 + r;v /= 10;}return vis[rv];};vector<int> res;for (int v: primes) {if (v >= l && v <= r) {if (checker(v)) {res.push_back(v);}} else if (v > r) {break;}}if (res.empty()) {cout << "No" << '\n';} else {for (int i = 0; i < res.size(); i++) {cout << res[i] << ",\n"[i == res.size() - 1];}}return 0;
}

---

B. 开关灯2

思路：调和级数/欧拉函数

属于思维题，但是背后还是数学

有两种思路

1. 调和级数

其复杂度为 $nlogn$

2. 欧拉函数
   就是求某个数的因子个数
   $$x=\prod a_i^{p_i}=>phi(x)=\prod (p_i+1)$$

这边采用调和级数做法

#include <bits/stdc++.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n;cin >> n;// 调和级数 nlognvector<int> arr(n + 1, 1);for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j+=i) {arr[j] ^= 1;}}bool flag = false;for (int i = 1; i <= n; i++) {if (arr[i] == 0) {if (flag) cout << " ";cout << i;flag = true;}}cout << '\n';return 0;
}

---

C. 判断一个数能否同时被3和5整除

题型：签到题

#include <bits/stdc++.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n;cin >> n;cout << ((n % 15 == 0) ? "Yes" : "No") << '\n';return 0;
}

---

D. 月份有几天

题型：模拟+签到

#include <bits/stdc++.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int y, m;cin >> y >> m;function<bool(int)> isYean = [](int y) {return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);};int days[2][12] = {{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},{31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},};if (isYean(y)) {cout << days[1][m - 1] << endl;} else {cout << days[0][m - 1] << endl;}return 0;
}

---

E. 数字反转

题型：签到

保证不存在 -0这样的数据存在

#include <bits/stdc++.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n;cin >> n;int rn = 0;int sign = 1;if (n < 0) {sign = -1;n = -n;}while (n > 0) {rn = rn * 10 + (n % 10);n /= 10;}cout << sign * rn << endl;return 0;
}

---

写在最后