2026年【江苏“信息与未来”编程思维】真题及题解（T2：快递无人机）
题目描述
Dr. X 制作了一台快递无人机，正在测试投送包裹。
投送的目标区域是一个圆形空地，它的边界在地图上用星号*标出。地图上的空白区域用半角点号.表示，每个包裹的落点用小写字母o标记。下图是一个例子：
........o ...***... ..*****.. ..*...*.. ..*.o.*.. ..*...*.. ..*****.. ...***... .........上图中，*围成的区域代表圆形空地。包裹o如果落在边界围成的区域内部，就是一次正确投送。Dr. X 想请你统计正确投送的包裹数量。包裹要么在圆内，要么在圆外，保证不会在圆形的边界上。
输入格式
输入第一行包含两个空格分隔的整数n nn和m mm，表示地图的行数和列数。接下来n nn行，每行m mm个字符，描述整张地图。字符只包含*（边界）、.（空白） 和o（包裹）。保证*恰好围成一个闭合的环形边界，且地图中至少有一个o。
输出格式
输出一个整数，表示落在圆形区域内的包裹数量。
输入输出样例 1
输入 1
9 9 ........o ...***... ..*****.. ..*...*.. ..*.o.*.. ..*...*.. ..*****.. ...***... .........输出 1
1输入输出样例 2
输入 2
12 13 ............. .....***..... ...*******... ...*.....*... ..*...o...*.. ..*.......*.. ..*..o.o..*.. ..*.......*.. ...*.....*... ...*******... .....***..... o............输出 2
3数据规模
- 对于40 % 40\%40%的数据，满足n , m ≤ 10 n, m \le 10n,m≤10。
- 对于100 % 100\%100%的数据，满足3 ≤ n , m ≤ 50 3 \le n, m \le 503≤n,m≤50。
思路分析
- 圆形是凸图形，所以每一行与圆形内部的交都是一段连续的区间。
- 这一行的左端点由最左边的
*标出，右端点由最右边的*标出。 - 因此，对于第
i行，只要找到该行最左星号列l和最右星号列r，那么列坐标满足l < j < r的包裹o就一定在圆内。 - 如果某一行没有星号，则这一行没有圆形内部区域，直接跳过即可。
代码实现
#include<bits/stdc++.h>usingnamespacestd;intn,m;intmain(){cin>>n>>m;//读地图大小vector<string>a(n);for(inti=0;i<n;i++)cin>>a[i];//读每一行intans=0;for(inti=0;i<n;i++){intl=m,r=-1;//本行最左、最右星号列for(intj=0;j<m;j++){if(a[i][j]=='*'){if(l==m)l=j;//首次星号作为左边界r=j;//每次星号更新右边界}}for(intj=0;j<m;j++){if(a[i][j]=='o'&&l<j&&j<r)ans++;//在左右星号之间就是在圆内}}cout<<ans;//输出答案return0;}功能分析
- 逐行扫描地图，记录每行最左边和最右边的星号位置。
- 利用圆的凸性：该行内部区域一定位于这两个星号之间。
- 统计所有满足
l < j < r的包裹o，即为正确投送到圆形区域内的包裹数量。 - 时间复杂度：
O(n * m)，空间复杂度：O(n * m)。
更多内容请关注专栏：信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
https://edu.csdn.net/course/detail/41081 点击跳转
3、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转
4、csp信奥赛冲刺一等奖有效刷题题解：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
