第十五届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组个人题解

记录一下我的算法学习心路并且回顾一下错题一、握手问题标签填空题、数学问题描述小蓝组织了一场算法交流会议总共有 50 人参加了本次会议。在会议上大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进行一次握手 (且仅有一次)。但有 7 个人这 7 人彼此之间没有进行握手 (但这 7 人与除这 7 人以外的所有人进行了握手)。请问这些人之间一共进行了多少次握手?注意 A 和 B 握手的同时也意味着 B 和 A 握手了所以算作是一次握手。答案提交这是一道结果填空的题你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。运行限制语言最大运行时间最大运行内存C1s256MC1s256MJava3s512MPython310s512MPyPy33s512MGo5s512MJavaScript5s512M题目分析简单数学题本质是计算除去这七个人之外的43人握手次数再加上7*43。AC代码如下。#includebits/stdc.h using namespace std; int main() { int n 43; int ans 0; while (n--) { ans n; } cout ans7*43; }二、小球反弹标签填空题、数学、思维问题描述有一长方形长为 343720 单位长度宽为 233333 单位长度。在其内部左上角顶点有一小球 (无视其体积)其初速度如图所示且保持运动速率不变分解到长宽两个方向上的速率之比为 dx:dy15:17。小球碰到长方形的边框时会发生反弹每次反弹的入射角与反射角相等因此小球会改变方向且保持速率不变如果小球刚好射向角落则按入射方向原路返回。从小球出发到其第一次回到左上角顶点这段时间里小球运动的路程为多少单位长度答案四舍五入保留两位小数。答案提交这是一道结果填空的题你只需要算出结果后提交即可。本题的结果为一个小数在提交答案时只填写这个小数填写多余的内容将无法得分。运行限制语言最大运行时间最大运行内存C1s256MC1s256MJava3s512MPython310s512MPyPy33s512MGo5s512MJavaScript5s512M题目分析这道题第一眼可能会想到暴力模拟但再思考一下就可以想到把矩形折开从而让小球的弹射路径变成直线这个时候我们只需要关注小球本身的横向纵向速度比和矩形原本边的关系就行了因为若小球刚好射向角落则按入射方向原路返回这一特性得出最后的直线路径在横向上应该可以整除343720纵向上应该可以整除233333因为这样才能保证小球最后实际的落点正好是落在矩形角落里从而能够原路返回同时这段直线路径还应该保持小球原本1517的速度比。于是答案呼之欲出把小球的运动路径看作直线路径的话应该有一个数t使得15t可以整除343720、17t可以整除233333然后运用勾股定理就能顺利求解了。代码如下。#include bits/stdc.h using namespace std; int main() { long long t1,x343720,y233333; while((15*t)%x!0||(17*t)%y!0){ t; } printf(%.2f,2*sqrt(15*t*15*t17*t*17*t)); }三、好数标签暴力、数学问题描述一个整数如果按从低位到高位的顺序奇数位 (个位、百位、万位 ⋯⋯ ) 上的数字是奇数偶数位 (十位、千位、十万位 ⋯⋯ ) 上的数字是偶数我们就称之为 “好数”。给定一个正整数 N请计算从 1 到 N 一共有多少个好数。输入格式一个整数 N。输出格式一个整数代表答案。评测用例规模与约定对于 10% 的评测用例1≤N≤100 。对于 100% 的评测用例1≤N≤107 。运行限制语言最大运行时间最大运行内存C1s256MC1s256MJava3s512MPython310s512MPyPy33s512MGo5s512MJavaScript5s512M题目分析很无聊的一题按照题目模拟就好了。AC代码如下。#includebits/stdc.h using namespace std; bool isGood(int a) { bool od false; while (a) { int b a % 10; if ((odb%2!0)||(!odb%20)) { return false; } a / 10; od !od; } return true; } int main() { int num; cin num; int ans 0; while (num--) { if (isGood(num)num0) { ans; } } cout ans; return 0; }四、R格式标签高精度、模拟问题描述小蓝最近在研究一种浮点数的表示方法R 格式。对于一个大于 0 的浮点数 d可以用 R 格式的整数来表示。给定一个转换参数 n将浮点数转换为 R 格式整数的做法是:将浮点数乘以 2n四舍五入到最接近的整数。输入格式一行输入一个整数 n 和一个浮点数 d分别表示转换参数和待转换的浮点数。输出格式输出一行表示答案d 用 R 格式表示出来的值。评测用例规模与约定对于 50% 的评测用例1≤n≤10,1≤ 将 d 视为字符串时的长度 ≤15。对于 100%100% 的评测用例1≤n≤1000,1≤ 将 d 视为字符串时的长度 ≤1024保证 d 是小数即包含小数点。运行限制语言最大运行时间最大运行内存C1s256MC1s256MJava3s512MPython310s512MPyPy33s512MGo5s512MJavaScript5s512M题目分析写这一题的时候看快了直接模拟了qwq#include bits/stdc.h using namespace std; int n; double d; int main() { cinnd; double num d*pow(2,n); cout(long long)(num0.5); return 0; }不出所料这是一道高精度题目一般来说高精度题目都是利用数组或者字符串来模拟大数的运算那么只需要模拟四舍五入和乘以2^n的运算这一题就能顺利解决了。代码如下。#includebits/stdc.h using namespace std; int n; string d;//用于读入初始浮点数 vectorintb;//用于进行模拟运算 int sum 0, dot 0; int main(){ cin n d; for (int i d.size() - 1; i 0; i--) { if (d[i] ! .) b.push_back(d[i] - 0);//这里b存的数字顺序是反过来的要注意 else dot sum; sum; } //进行第一步乘以2^n模拟乘法 for (int i 0 ; i n; i) { int t 0; for (int j 0; j b.size(); j) { b[j] b[j] * 2 t; if (b[j] 10) t 0; else { t b[j] / 10; b[j] b[j]%10; } } if (t) { //模拟进位 b.push_back(t); } } if (b[dot-1] 5) { //五入 b[dot]; for (int i dot ; i b.size()-1 b[i]9; i) { b[i] b[i] % 10; b[i 1]; } if (b.back() 9) { b[b.size()] b[b.size()] % 10; b.push_back(1); } } for (int i b.size() - 1; i dot; i--) cout b[i]; return 0; }五、宝石组合标签数学、LCM问题描述在一个神秘的森林里住着一个小精灵名叫小蓝。有一天他偶然发现了一个隐藏在树洞里的宝藏里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力可以发出不同强度的闪光。小蓝共找到了 N 枚宝石第 i 枚宝石的 “闪亮度” 属性值为 Hi​小蓝将会从这 N 枚宝石中选出三枚进行组合组合之后的精美程度 S 可以用以下公式来衡量其中 LCM 表示的是最小公倍数函数。小蓝想要使得三枚宝石组合后的精美程度 S 尽可能的高请你帮他找出精美程度最高的方案。如果存在多个方案 S 值相同优先选择按照 H 值升序排列后字典序最小的方案。输入格式第一行包含一个整数 N 表示宝石个数。第二行包含 N 个整数表示 N 个宝石的 “闪亮度”。输出格式输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。评测用例规模与约定对于 30% 的评测用例3≤N≤100,1≤Hi≤1000 。对于 60% 的评测用例3≤N≤2000 。对于 100% 的评测用例3≤N≤105,1≤Hi≤105 。运行限制语言最大运行时间最大运行内存C1s256MC1s256MJava3s512MPython310s512MPyPy33s512MGo5s512MJavaScript5s512M题目分析首先看到这种题目想到的应该是化简公式但我在自己写的时候也没有什么化简的思路于是只能暴力遍历想拿点分所以这里我借用一下蓝桥云课上的一些题解记住这两个公式就可以得出原式化简为到这一步如果在比赛没时间了就可以直接模拟拿点分数跑路了(●◡●)但都到这一步了距离完美解决也很近了一开始我想的是枚举宝石组合但又感觉太麻烦了所以采用枚举S值的方式也可以写出AC代码从高到低枚举S值并且按照字典顺序枚举每个宝石的H值根据上述的简化公式找出枚举的H值中前三个符合题目要求的就可以了代码如下#include bits/stdc.h using namespace std; #define N 500010 int gem[N],num[N],n; int main(){ cinn; int maxs0; for(int i0;in;i){ cingem[i];//记录每个宝石的闪亮度 num[gem[i]];//记录每种宝石数量 maxs max(maxs,gem[i]); } for(int i maxs;i0;i--){ int cnt 0; int res[3]; int a 0; for(int j i;jmaxs;ji){//寻找i的所有倍数 if(num[j]){ cntnum[j]; int b num[j]; while(b--a3){ res[a] j; } } if(cnt3) { break; } } if(cnt3){ for(int t 0;t3;t){ coutres[t] ; } break; } } return 0; }六、数字接龙标签暴力、模拟、DFS问题描述小蓝最近迷上了一款名为《数字接龙》的迷宫游戏游戏在一个大小为 N×N 的格子棋盘上展开其中每一个格子处都有着一个 0…K−1 之间的整数。游戏规则如下从左上角 (0,0) 处出发目标是到达右下角 (N−1,N−1) 处的格子每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。对于路径经过的棋盘格子按照经过的格子顺序上面的数字组成的序列要满足0,1,2,…,K−1,0,1,2,…,K−1,0,1,2… 。途中需要对棋盘上的每个格子恰好都经过一次仅一次。路径中不可以出现交叉的线路。例如之前有从 (0,0) 移动到 (1,1) 那么再从 (1,0) 移动到 (0,1) 线路就会交叉。为了方便表示我们对可以行进的所有八个方向进行了数字编号如下图 2 所示因此行进路径可以用一个包含 0…7 之间的数字字符串表示如下图 1 是一个迷宫示例它所对应的答案就是41255214。现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径输出字典序最小的那一个如果不存在任何一条路径则输出 −1。输入格式第一行包含两个整数 N,K 。接下来输入 N 行每行 N 个整数表示棋盘格子上的数字。输出格式输出一行表示答案。如果存在答案输出路径否则输出 −1。评测用例规模与约定对于 80% 的评测用例1≤N≤5 。对于 100% 的评测用例1≤N≤10,1≤K≤10 。运行限制语言最大运行时间最大运行内存C1s256MC1s256MJava3s512MPython310s512MPyPy33s512MGo5s512MJavaScript5s512M题目分析从题目来看这题很适合用DFS来做但是实际操作时我有一个难点就是怎么判断是不是有重复路线呢仔细想想就能知道实际遍历时只有两条相互垂直的“对角线”才有可能交叉所以我们在遍历时记录一下每一条边。代码如下#include bits/stdc.h using namespace std; const int N 11; int dx[8] {-1,-1,0,1,1,1,0,-1}; int dy[8] {0,1,1,1,0,-1,-1,-1}; int n,k; vectorint path; int g[N][N]; bool vis[N][N]; bool edge[N][N][N][N]; bool dfs(int x , int y){ if(x n-1y n-1) { if(path.size() n*n-1){ return 1; }else return 0; } vis[x][y] true; for(int i 0;i8;i){ int nx x dx[i]; int ny y dy[i];//计算当前遍历方向后的坐标 if(nx0||nxn||ny0||nyn||vis[nx][ny]) continue; //检验合法性 if(g[nx][ny]!(g[x][y]1)%k) continue; if (i % 2 (edge[x][ny][nx][y] || edge[nx][y][x][ny])) continue; edge[x][y][nx][ny] true; path.push_back(i); if (dfs(nx, ny)) return true; path.pop_back(); edge[x][y][nx][ny] false; } vis[x][y] false; return false; } int main() { cin n k; for (int i 0; i n; i) { for (int j 0; j n; j) cin g[i][j]; } if (!dfs(0, 0)) cout -1 endl; else for(int i 0;ipath.size();i){ cout path[i]; } return 0; }七、拔河标签双指针、二分、STL问题描述小明是学校里的一名老师他带的班级共有 n 名同学第 i 名同学力量值为 ai​。在闲暇之余小明决定在班级里组织一场拔河比赛。为了保证比赛的双方实力尽可能相近需要在这 nn 名同学中挑选出两个队伍队伍内的同学编号连续{al1,al11,…,ar1−1,ar1} 和 {al2,al21,…,ar2−1,ar2}其中 l1​≤r1​l2​≤r2​。两个队伍的人数不必相同但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。输入格式输入共两行。第一行为一个正整数 n。第二行为 n 个正整数 ai​。输出格式输出共一行一个非负整数表示两个队伍力量值之和的最小差距。评测用例规模与约定对于 20% 的评测用例保证 n≤50 。对于 100% 的评测用例保证 n≤103,ai​≤109 。运行限制语言最大运行时间最大运行内存C1s256MC1s256MJava3s512MPython310s512MPyPy310s512MGo5s512MJavaScript5s512M题目分析这题我一开始看到的想法是试图直接暴力遍历左区间这个题目数据不大要维护这样的数组也不难。但这样有个缺点就是无法有效分别原本带有重叠甚至包含的子区间于是我们可以引入一个分割点左区间在分割点左边按照区间长度遍历并储存右区间在右边紧靠着分割点这样就可以同时遍历左区间和右区间。代码如下#include bits/stdc.h using namespace std; typedef long long LL; const int N 1005; int n; LL a[N]; LL s[N]; int main() { cin n for (int i 1; i n; i) { cin a[i]; s[i] s[i - 1] a[i]; } LL res -1; setLL left_sums; for (int i 1; i n; i) { for (int l 1; l i; l) { left_sums.insert(s[i] - s[l - 1]); } for (int r i 1; r n; r) { LL right_sum s[r] - s[i]; auto it left_sums.lower_bound(right_sum); if (it ! left_sums.end()) { LL diff *it - right_sum; if (res -1 || diff res) res diff; } if (it ! left_sums.begin()) { LL diff right_sum - *(--it); if (res -1 || diff res) res diff; } if (res 0) { cout 0 endl; return 0; } } } cout res endl; return 0; }结语这是我第一次试着去发表一个分享自己学习过程的博客感觉自己收获颇丰以后也许会常发一些吧多谢大家