2026年【江苏“信息与未来”编程思维】真题及题解（T2：快递无人机）

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。

思路分析

1. 圆形是凸图形，所以每一行与圆形内部的交都是一段连续的区间。
2. 这一行的左端点由最左边的*标出，右端点由最右边的*标出。
3. 因此，对于第i行，只要找到该行最左星号列l和最右星号列r，那么列坐标满足l < j < r的包裹o就一定在圆内。
4. 如果某一行没有星号，则这一行没有圆形内部区域，直接跳过即可。

代码实现

#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;}