第十五届蓝桥杯CC++大学B组

第十五届蓝桥杯CC大学B组官方试题合集蓝桥杯大赛历届真题_蓝桥杯 - 蓝桥云课题目A握手问题思路这道题还是很简单的7个人特殊就让他们排到最后握手其余人两两握。题解#include iostream #include algorithm #include vector #include cmath using namespace std; int main() { int sum 0; for (int n 1; n 42; n) { sum n; } sum 7 * 43; cout sum; return 0; }题目B小球反弹思路暴力这道题没做过的还真很难做出来。先看看暴力怎么写速率比是15:17那路程比也肯定是15:17。回到原点那么说明路程一定是长或宽的偶数倍。题解暴力#includebits/stdc.h using namespace std; int main() { //暴力 for(long long i2; i10000; x2) for(long long j2; j100000; y2) if(15*233333*j17*343720*i) { coutsqrt((343720*i)*(343720*i)(233333*j)*(233333*j))//勾股定理; return 0; } return 0; }思路方程其实对于填空题直接暴力最省时间。碰撞之后分速度大小不变但是某个分速度会相反。如果碰到下边v下-v上v右不变。相当于将长方形沿下边翻折。如果碰到右边相当于将长方形沿右边翻折。我们知道路程比 dx : dy 那么Y * dx X * dy令Y y * 2 * aX x * 2 * b求ab的最小值。所以我们可以先求 X 和 Y 的最小公倍数。题解方程int main() { double sum 0; long long y 233333; long long x 343720; long long dy 17; long long dx 15; int a 0; int b 0; // y * 2 * dx * a x * 2 * dy * b; // 先求最大公约数 long long g __gcd(dx * y * 2, dy * x * 2); // 再求最小公倍数 long long t y * 2 * dx / g * x * 2 * dy; a t / (y * 2 * dx); b t / (x * 2 * dy); sum sqrt((y * a * 2) * (y * a * 2) (x * b * 2) * (x * b * 2)); cout fixed setprecision(2) sum; return 0; }LCM(a,b) a*b / GCD(a,b)最小公倍数 两个数的乘积 / 最大公约数题目C好数思路直接挨个算的时间复杂度也是常数级的直接暴力就行。题解1int main() { int N; cin N; int count 0; for (int i 1; i N; i) { int n i; for (int j 1; n 0; j, n / 10) { if (j % 2 ! (n % 10) % 2) { break; } } if (n 0) { count; } } cout count; return 0; }题解2#includebits/stdc.h using namespace std; int n; int ans 0; bool t; int main(){ cin n; for(int i 1;i n;i){ int j i; int c 1; t true; while(j 0){ int m j % 10; if(m % 2 ! c % 2){ t false; break; } c; j / 10; } if (t){ ans; } } cout ans; }题目DR格式思路一开始想到快速幂运算// 快速幂计算 a^nn 0 long long fastPower(long long a, long long n) { long long result 1; // 结果初始化为1任何数的0次方为1 long long base a; // 当前底数初始为a while (n 0) { // 如果指数二进制最后一位是1将当前底数乘到结果中 if (n % 2 1) { result * base; } // 底数平方对应指数二进制左移一位 base * base; // 指数右移一位等价于 n n / 2 n / 2; } return result; }// 快速幂位运算优化版 long long fastPowerBit(long long a, long long n) { long long result 1; long long base a; while (n 0) { // 位运算判断最后一位是否为1替代 n%21 if (n 1) { result * base; } base * base; // 位运算右移一位替代 n / 2 n 1; } return result; }但是不行因为快速幂适用于整数运算如果是浮点数会放大误差。必须用高精度B站链接【高精度算法全套加减乘除全网最详细】https://www.bilibili.com/video/BV1LA411v7mt/?share_sourcecopy_webvd_sourcec78a410f12ade1fd5af50917e0f2b35d题解详细注释using namespace std; int n; // 转换参数n用于计算乘以2的n次方 int num[100005];// 存储浮点数的每一位数字高精度数组 string s; // 输入的浮点数字符串 int l; // 存储数字串的有效长度 int main() { // 1. 输入转换参数n和浮点数字符串s cin n; cin s; // 反转字符串方便从低位到高位处理如123.45反转为54.321 reverse(s.begin(), s.end()); // 找到反转后字符串中小数点的位置 int p s.find(.); // 移除小数点将字符串转为纯数字串如54.321转为54321 s.erase(p, 1); // 更新有效长度为移除小数点后的字符串长度 l s.size(); // 将字符串的每一位字符转为数字存入num数组num[0]是最低位 for (int i 0; i l; i) { num[i] s[i] - 0; } // 2. 模拟乘以2的n次方循环n次每次整体乘以2并处理进位 for (int i 0; i n; i) { // 第一步当前所有位乘以2 for (int j 0; j l; j) { num[j] * 2; } // 第二步处理每位的进位满10进1 for (int j 0; j l; j) { if (num[j] 10) { num[j 1] num[j] / 10; // 进位到高位 num[j] % 10; // 保留当前位的个位 } } // 如果最高位有进位扩展有效长度 if (num[l] 0) { l; } } // 3. 四舍五入处理判断原小数点后对应位是否≥5若是则进1 if (num[p - 1] 5) { num[p]; // 向高位进1 } // 处理四舍五入后的进位仅判断p1位原逻辑有局限 if (num[p 1] 10) { for (int j p; j l; j) { if (num[j] 10) { num[j 1] num[j] / 10; num[j] % 10; } else { break; // 无进位则停止处理 } } } // 若最高位因进位产生新数字扩展有效长度 if (num[l] 0) { l; } // 4. 输出结果从最高位到原小数点位置的所有位整数部分 for (int i l - 1; i p; i--) { cout num[i]; } return 0; }需要注意的是四舍五入是需要再遍历一下左边因为小数的四舍五入有可能会影响到最左高位如 99.5 - 100题目E宝石组合思路S可以化简为 S gcd ( Ha , Hb , Hc )选三个H让他们的最大公因数最大如果现在直接暴力肯定超时。第一种思路将每个数的公因数都存储下来然后挨个遍历找到最大的出现三次的公因数并记录这三个数。再优化一下用一个数组来计数统计某个数作为公因数出现的次数代码段int N; cin N; vectorint ns; int n 100000; int nss[n] {0}; for (int i 0; i N; i) { int j; cin j; ns.push_back(j); for (int k 1; k*k j; k) { if (j % k 0) { nss[k]; if (k*k ! j) { nss[j/k]; } } } }再倒着找到最先出现3次的公因数 M然后再遍历一下排序后的原数组寻找是这个 M 公倍数的数字知道找够3个。题解using namespace std; int n; int num[100005]; string s; int l; int main() { int N; cin N; vectorint ns; int n 100000; int nss[n] {0}; for (int i 0; i N; i) { int j; cin j; ns.push_back(j); for (int k 1; k*k j; k) { if (j % k 0) { nss[k]; if (k*k ! j) { nss[j/k]; } } } } sort(ns.begin(), ns.end()); int M; vectorint ans; for (int i n - 1; i 0; i--) { if (nss[i] 3) { M i; break; } } for (int i 0; i N; i) { if (ns[i] % M 0) { ans.push_back(ns[i]); if (ans.size() 3) { break; } } } cout ans[0] ans[1] ans[2] endl; return 0; }题目F数字接龙思路这道题比较难。如果不会用方向数组可能做不出来。首先根据提议写出方向数组代码段int dy[] {-1, -1, 0, 1, 1, 1, 0, -1}; int dx[] {0, 1, 1, 1, 0, -1, -1, -1};首先用一个二维数组存储地图一个二维数组存储地图各个地方是否走到过。然后DFS递归8个方向。并且需要越界判断防止交叉搜索是否符合移动规则回溯题解using namespace std; string ans; int dx[] {-1, -1, 0, 1, 1, 1, 0, -1}; int dy[] {0, 1, 1, 1, 0, -1, -1, -1}; int n, k; int a[11][11]; bool vis[11][11]; bool dfs(int x, int y, int pre, string s, int d) // x,y为当前坐标,pre为上一个数字,s为方向字符串,d深度 { if (x n y n d n * n) { ans s; return true; } // 从0到7枚举方向对应8个方向保证字典序最小 for (int i 0; i 8; i) { // 随机移动后的坐标 int nx x dx[i]; int ny y dy[i]; // 越界判断 if (nx 1 || nx n || ny 1 || ny n) { continue; } if (vis[nx][ny]) { continue; } // 防止交叉搜索 if (i 1 vis[x - 1][y] a[x][y 1]) { continue; } else if (i 3 vis[x 1][y] vis[x][y 1]) { continue; } else if (i 5 vis[x][y - 1] a[x 1][y]) { continue; } else if (i 7 vis[x - 1][y] a[x][y - 1]) { continue; } // 判断是否符合移动规则 if ((a[nx][ny] pre 1 a[nx][ny] k) || (a[nx][ny] 0 pre k - 1)) { // 标记为已访问 vis[nx][ny] true; dfs(nx, ny, a[nx][ny], s to_string(i), d 1); // 剪枝 if (!ans.empty()) { return true; } // 回溯 vis[nx][ny] false; } } } int main() { cin n k; vis[1][1] true; for (int i 1; i n; i) { for (int j 1; j n; j) { cin a[i][j]; } } string s; dfs(1, 1, 0, s, 1); if (ans.empty()) { cout -1; } else { cout ans; } }题目G爬山思路肯定要有限使用 P 魔法啊。刚开始就想到用 multiset 其实用堆更好一点题解multisetusing namespace std; int n, P, Q; multisetint H; int ans; int main() { cin n P Q; for (int i 0; i n; i) { int j; cin j; H.insert(j); } for(int i 0;iP;i){ int j *H.rbegin(); H.erase(H.find(j)); H.insert(sqrt(j)); } for(int i 0;iQ;i){ int j *H.rbegin(); H.erase(H.find(j)); H.insert(j/2); } for (auto num : H) { ans num; } cout ans; return 0; }题解堆using namespace std; int n, P, Q; int ans; priority_queueint H; // 使用堆实现 int main() { cin n P Q; for (int i 0; i n; i) { int j; cin j; H.push(j); } for(int i 0;iP;i){ int j H.top(); H.pop(); H.push(sqrt(j)); } for(int i 0;iQ;i){ int j H.top(); H.pop(); H.push(j/2); } while (!H.empty()) { H.pop(); ans H.top(); } cout ans; return 0; }题目H拔河思路两个小队的成员必须是连续不间断的但是我一开始只考虑了部分的情况[ 1,2,3]和[ 5,6] 这种没有考虑 [ 2,3] 和 [ 5] 这种也就是每一队总是包含头和尾是不全面的。用 lsum [ i ] 存储从首到 i 位置的力量和rsum [ i ] 存储从 i 到尾的力量和。然后两个 for 循环遍历求解。代码int main() { int n; cin n; vectorint nums; for (int i 0; i n; i) { int j; cin j; nums.push_back(j); } vectorint lsum; vectorint rsum; int pre 0; for (int i 0; i n; i) { pre nums[i]; lsum.push_back(pre); } pre 0; for (int i n - 1; i 0; i--) { pre nums[i]; rsum.push_back(pre); } int m INT_MAX; for (int i 0; i n; i) { for (int j i 1; j n; j) { m min(m, abs(lsum[i] - rsum[n - j - 1])); } } cout m; return 0; }所以我们需要考虑更多的情况但是还按照这个思路看定超时。需要新的思路我们肯定需要前缀和后缀和 总和 - 前缀和。并有前缀和计算出所有的组合的和。所有的组合肯定有很多种我们用 multiset 而不是 set 。特性setmultiset重复元素不允许自动去重允许可存多个相同值插入逻辑行通知只能存一个相同值全部存储erase值行为删除所有该值的元素删除所有该值的元素erase迭代器行为删除迭代器指向的元素删除迭代器指向的元素查找 find值返回第一个匹配的迭代器无则 end然后以 i 为左队和右队的分界点从 1 开始遍历i 属于左队并进行// 从S中删除「所有以i为起点的子数组和」 for (int j i; j n; j) { // 以迭代器的方式删除避免删除全部相同元素 auto p S.find(a[j] - a[i - 1]); S.erase(p); // 删除第一个匹配元素 }因为这些数肯定不属于右队。而左队我们可以用前缀和遍历得到 k 然后再在剩下的multiset中其实也就是右队所有可能的组合和因为我们依次进行这样的操作能够把multiset中的左队删掉只剩下右队的组合和这是关键。然后// 枚举所有以i为终点的子数组和 for (int j 1; j i; j) { long long k a[i] - a[j - 1]; // 找到大于等于k的第一个元素的迭代器 auto p S.lower_bound(k); if (p ! S.end()) // 如果找到 ans min(ans, abs(*p - k)); if (p ! S.begin()) // 如果找到且不是第一个元素 // 比较前一个元素与k的差值(可能更小) p--, ans min(ans, abs(*p - k)); }题解正解#include bits/stdc.h using namespace std; const int maxn 1e3 10; int n; long long a[maxn], ans 1e9; multisetlong long S; // 没有使用set int main() { cin n; for (int i 1; i n; i) { cin a[i], a[i] a[i - 1] a[i]; // 前缀和维护 } for (int i 1; i n; i) { for (int j i; j n; j) { S.insert(a[j] - a[i - 1]); // 全部插入 } } for (int i 1; i n; i) { // 从S中删除「所有以i为起点的子数组和」 for (int j i; j n; j) { // 以迭代器的方式删除避免删除全部相同元素 auto p S.find(a[j] - a[i - 1]); S.erase(p); // 删除第一个匹配元素 } // 枚举所有以i为终点的子数组和 for (int j 1; j i; j) { long long k a[i] - a[j - 1]; // 找到大于等于k的第一个元素的迭代器 auto p S.lower_bound(k); if (p ! S.end()) // 如果找到 ans min(ans, abs(*p - k)); if (p ! S.begin()) // 如果找到且不是第一个元素 // 比较前一个元素与k的差值(可能更小) p--, ans min(ans, abs(*p - k)); } } cout ans; return 0; }