本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
洛谷：[P3958 NOIP 2017 提高组] 奶酪 - 洛谷
【题目描述】
现有一块大奶酪，它的高度为h hh，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为z = 0 z = 0z=0，奶酪的上表面为z = h z = hz=h。
现在，奶酪的下表面有一只小老鼠 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-一维#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int定义为long long类型constintN=1005;// 最大空洞数量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{// 读取测试用例数量cin>>t;// 处理每个测试用例while(t--){// 读取空洞数量、奶酪高度、空洞半径cin>>n>>h>>r;// 读取每个空洞的坐标for(inti=1;i<=n;i++){cin>>x[i]>>y[i]>>z[i];}// BFS队列，用于遍历连通空洞queue<int>q;// 初始化访问标记数组memset(vis,0,sizeof(vis));// 将所有与底面接触的空洞加入队列for(inti=1;i<=n;i++){// 判断空洞是否与底面接触：空洞下边缘(z[i]-r) <= 0if(z[i]-r<=0){q.push(i);}}intmaxh=-1;// 记录从底面可达的最高高度// BFS遍历所有连通空洞while(!q.empty()){intt=q.front();// 获取队首空洞q.pop();// 标记当前空洞为已访问vis[t]=true;// 更新可达的最大高度：当前空洞的上边缘(z[t]+r)maxh=max(maxh,z[t]+r);// 检查所有未访问的空洞，看是否与当前空洞连通for(inti=1;i<=n;i++){if(vis[i])// 如果空洞i已访问过，跳过{continue;}// 判断空洞i是否与当前空洞t连通：// 两空洞中心距离平方 <= (2r)^2，即两空洞相交或相切if(calc(i,t)<=(2*r)*(2*r)){q.push(i);// 连通，加入队列}}}// 判断是否可以穿过奶酪：// 如果从底面可达的最大高度 >= 奶酪高度h，则可以穿过if(maxh>=h){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}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
