本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷[P3958 NOIP 2017 提高组] 奶酪 - 洛谷【题目描述】现有一块大奶酪它的高度为h hh它的长度和宽度我们可以认为是无限大的奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系在坐标系中奶酪的下表面为z 0 z 0z0奶酪的上表面为z h z hzh。现在奶酪的下表面有一只小老鼠 Jerry它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交则 Jerry 可以从其中一个空洞跑到另一个空洞特别地如果一个空洞与下表面相切或是相交Jerry 则可以从奶酪下表面跑进空洞如果一个空洞与上表面相切或是相交Jerry 则可以从空洞跑到奶酪上表面。位于奶酪下表面的 Jerry 想知道在不破坏奶酪的情况下能否利用已有的空洞跑到奶酪的上表面去?空间内两点P 1 ( x 1 , y 1 , z 1 ) P_1(x_1,y_1,z_1)P1​(x1​,y1​,z1​)、P 2 ( x 2 , y 2 , z 2 ) P_2(x_2,y_2,z_2)P2​(x2​,y2​,z2​)的距离公式如下d i s t ( P 1 , P 2 ) ( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 ( z 1 − z 2 ) 2 \mathrm{dist}(P_1,P_2)\sqrt{(x_1-x_2)^2(y_1-y_2)^2(z_1-z_2)^2}dist(P1​,P2​)(x1​−x2​)2(y1​−y2​)2(z1​−z2​)2​【输入】每个输入文件包含多组数据。第一行包含一个正整数T TT代表该输入文件中所含的数据组数。接下来是T TT组数据每组数据的格式如下 第一行包含三个正整数n , h , r n,h,rn,h,r两个数之间以一个空格分开分别代表奶酪中空洞的数量奶酪的高度和空洞的半径。接下来的n nn行每行包含三个整数x , y , z x,y,zx,y,z两个数之间以一个空格分开表示空洞球心坐标为( x , y , z ) (x,y,z)(x,y,z)。【输出】T TT行分别对应T TT组数据的答案如果在第i ii组数据中Jerry 能从下表面跑到上表面则输出Yes如果不能则输出No。【输入样例】3 2 4 1 0 0 1 0 0 3 2 5 1 0 0 1 0 0 4 2 5 2 0 0 2 2 0 4【输出样例】Yes No Yes【算法标签】#BFS-一维#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将int定义为long long类型constintN1005;// 最大空洞数量intt;// 测试用例数量intn,h,r;// n: 空洞数量, h: 奶酪高度, r: 空洞半径intx[N],y[N],z[N];// 存储每个空洞的坐标boolvis[N];// 标记数组记录空洞是否被访问过// 计算两个空洞之间的直线距离平方intcalc(intp1,intp2){return(x[p1]-x[p2])*(x[p1]-x[p2])(y[p1]-y[p2])*(y[p1]-y[p2])(z[p1]-z[p2])*(z[p1]-z[p2]);}signedmain()// 因为定义了#define int long long所以需要用signed main{// 读取测试用例数量cint;// 处理每个测试用例while(t--){// 读取空洞数量、奶酪高度、空洞半径cinnhr;// 读取每个空洞的坐标for(inti1;in;i){cinx[i]y[i]z[i];}// BFS队列用于遍历连通空洞queueintq;// 初始化访问标记数组memset(vis,0,sizeof(vis));// 将所有与底面接触的空洞加入队列for(inti1;in;i){// 判断空洞是否与底面接触空洞下边缘(z[i]-r) 0if(z[i]-r0){q.push(i);}}intmaxh-1;// 记录从底面可达的最高高度// BFS遍历所有连通空洞while(!q.empty()){inttq.front();// 获取队首空洞q.pop();// 标记当前空洞为已访问vis[t]true;// 更新可达的最大高度当前空洞的上边缘(z[t]r)maxhmax(maxh,z[t]r);// 检查所有未访问的空洞看是否与当前空洞连通for(inti1;in;i){if(vis[i])// 如果空洞i已访问过跳过{continue;}// 判断空洞i是否与当前空洞t连通// 两空洞中心距离平方 (2r)^2即两空洞相交或相切if(calc(i,t)(2*r)*(2*r)){q.push(i);// 连通加入队列}}}// 判断是否可以穿过奶酪// 如果从底面可达的最大高度 奶酪高度h则可以穿过if(maxhh){coutYesendl;}else{coutNoendl;}}return0;}【运行结果】3 2 4 1 0 0 1 0 0 3 Yes 2 5 1 0 0 1 0 0 4 No 2 5 2 0 0 2 2 0 4 Yes