公众号申请网站wordpress 登录集成
前言
题解
这是第三届大学生算法大赛(第二届为清华社杯)的赛前练习赛一.
这是上界比赛的体验报告: 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
思路：调和级数/欧拉函数
属于思维题，但是背后还是数学
有两种思路
- 调和级数
其复杂度为 n l o g n nlogn nlogn
- 欧拉函数
就是求某个数的因子个数
x = ∏ a i p i = > p h i ( x ) = ∏ ( p i + 1 ) x = \prod a_i^{p_i} => phi(x)=\prod (p_i+1) x=∏aipi=>phi(x)=∏(pi+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;
}
写在最后
