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

2026年【江苏“信息与未来”编程思维】真题及题解T2快递无人机题目描述Dr. X 制作了一台快递无人机正在测试投送包裹。投送的目标区域是一个圆形空地它的边界在地图上用星号*标出。地图上的空白区域用半角点号.表示每个包裹的落点用小写字母o标记。下图是一个例子........o ...***... ..*****.. ..*...*.. ..*.o.*.. ..*...*.. ..*****.. ...***... .........上图中*围成的区域代表圆形空地。包裹o如果落在边界围成的区域内部就是一次正确投送。Dr. X 想请你统计正确投送的包裹数量。包裹要么在圆内要么在圆外保证不会在圆形的边界上。输入格式输入第一行包含两个空格分隔的整数n nn和m mm表示地图的行数和列数。接下来n nn行每行m mm个字符描述整张地图。字符只包含*边界、.空白 和o包裹。保证*恰好围成一个闭合的环形边界且地图中至少有一个o。输出格式输出一个整数表示落在圆形区域内的包裹数量。输入输出样例 1输入 19 9 ........o ...***... ..*****.. ..*...*.. ..*.o.*.. ..*...*.. ..*****.. ...***... .........输出 11输入输出样例 2输入 212 13 ............. .....***..... ...*******... ...*.....*... ..*...o...*.. ..*.......*.. ..*..o.o..*.. ..*.......*.. ...*.....*... ...*******... .....***..... o............输出 23数据规模对于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就一定在圆内。如果某一行没有星号则这一行没有圆形内部区域直接跳过即可。代码实现#includebits/stdc.husingnamespacestd;intn,m;intmain(){cinnm;//读地图大小vectorstringa(n);for(inti0;in;i)cina[i];//读每一行intans0;for(inti0;in;i){intlm,r-1;//本行最左、最右星号列for(intj0;jm;j){if(a[i][j]*){if(lm)lj;//首次星号作为左边界rj;//每次星号更新右边界}}for(intj0;jm;j){if(a[i][j]oljjr)ans;//在左右星号之间就是在圆内}}coutans;//输出答案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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}