小公司怎么做免费网站,内容营销的核心,在线效果图设计,网站怎么换模板前言 题解
这是第三届大学生算法大赛(第二届为清华社杯)的赛前练习赛一.
这是上界比赛的体验报告: 2023第二届“清华社杯”大学生算法大赛 解题报告(流水账版) | 珂学家#xff0c;个人还是非常推荐这个比赛。
难度分布#xff1a;4 easy/4 mid-hard/2 hard
赛前练习赛一…
前言 题解
这是第三届大学生算法大赛(第二届为清华社杯)的赛前练习赛一.
这是上界比赛的体验报告: 2023第二届“清华社杯”大学生算法大赛 解题报告(流水账版) | 珂学家个人还是非常推荐这个比赛。
难度分布4 easy/4 mid-hard/2 hard
赛前练习赛一出自题库的每日一题相对比较简单又特别偏数学题。
所以这个练习赛一感觉代表性不是那么强但是又能代表官方的一种出题倾向吧。 A. 区间内的真素数 思路质数筛/质数判定
因为数据范围不是很大所以两类思路都可以
用欧拉筛的时候需要注意范围翻转会变大
区间筛也可以试试
#include bits/stdc.husing 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;// 欧拉筛vectorint primes;vectorbool 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;}}functionbool(int) checker [](int v) {int rv 0;while (v 0) {int r v % 10;rv rv * 10 r;v / 10;}return vis[rv];};vectorint 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_i1) x∏aipiphi(x)∏(pi1)
这边采用调和级数做法
#include bits/stdc.husing namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n;cin n;// 调和级数 nlognvectorint arr(n 1, 1);for (int i 1; i n; i) {for (int j i; j n; ji) {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.husing 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.husing namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int y, m;cin y m;functionbool(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.husing 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;
}写在最后
