B4158 [BCSP-X 2024 12 月小学高年级组] 质数补全题解
题目# B4158 [BCSP-X 2024 12 月小学高年级组] 质数补全## 题目描述Alice 在纸条上写了一个质数第二天再看时发现有些地方污损看不清了。- 在大于 $1$ 的自然数中除了 $1$ 和它本身以外不再有其他因数的自然数称为质数请你帮助 Alice 补全这个质数若有多解输出数值最小的若无解输出 $-1$。例如纸条上的数字为 $\tt{1*}$$\tt{*}$ 代表看不清的地方那么这个质数有可能为 $11, 13, 17, 19$其中最小的为 $11$。## 输入格式第一行 $1$ 个整数 $t$代表有 $t$ 组数据。接下来 $t$ 行每行 $1$ 个字符串 $s$ 代表 Alice 的数字仅包含数字或者 $\tt{*}$并且保证首位不是 $\tt{*}$ 或者 $0$。## 输出格式输出 $t$ 行每行 $1$ 个整数代表最小可能的质数或者 $-1$ 代表无解。## 输入输出样例 #1### 输入 #1101*3**7**83*722626**129*7889*777*225*### 输出 #1113077018317-1601129178893-12251## 输入输出样例 #2### 输入 #2104039***2***5*5409996125**7577***0**1***00*41811*96***0*78***1**6561*59### 输出 #24039019-140999612509757700000310000034181129600004780001016561259## 说明/提示### 样例 3-6参考附件中的样例。### 数据范围$|s|$ 代表 $s$ 串的长度对于所有数据$1 \leq t \leq 10, 1 \leq |s| \leq 7$$s$ 中仅包含数字或者 $\tt{*}$并且保证首位不是 $\tt{*}$ 或者 $0$。本题采用捆绑测试你必须通过子任务中的所有数据点以及其依赖的子任务才能获得子任务对应的分数。| 子任务编号 | 分值 | $\mid s\mid$ | 特殊性质 | 子任务依赖 || :----------: | :----------: | :----------: | :----------: | :----------: || $1$ | $35$ | $\leq 7$ | $s$ 中没有 $\tt{*}$ | || $2$ | $30$ | $\leq 4$ | | || $3$ | $24$ | $\leq 7$ | $s$ 中至多包含 $1$ 个 $\tt{*}$ | $1$ || $4$ | $11$ | $\leq 7$ | | $1,2,3$ |————————————————————————————————————————AC代码cpp# include bits/stdc.h# define ll long longusing namespace std;string s[15]{};ll f10,dw0;bool f(int x){if(x1) return 0;for(int i2; isqrt(x); i){if(x%i0) return 0;}return 1;}void dfs(int w,int q,int c,unsigned ll d){if(f1) return;if(cw){if(f(d)){dwd;f11;}return;}if(s[q][c]*){for(int i0; i9; i){dfs(w,q,c1,d*10i);}}else{dfs(w,q,c1,d*10(s[q][c]-0));}}int main(){int n;cin n;for(int i1; in; i){cin s[i];}for(int i1; in; i){dfs(s[i].size(),i,0,0);if(dw0) cout -1endl;else cout dwendl;dw0; f10;}return 0;}___________________________________________________________________分步1.定义cppstring s[15]{};ll f10,dw0;cppint n;2.输入cppcin n;for(int i1; in; i){cin s[i];}3.质数筛从2到sqrt(n)去筛基础cppbool f(int x){if(x1) return 0;for(int i2; isqrt(x); i){if(x%i0) return 0;}return 1;}4.dfs从最小便利可以比暴力算快好多重点难点cppdfs(s[i].size(),i,0,0);cppvoid dfs(int w,int q,int c,unsigned ll d){if(f1) return;if(cw){if(f(d)){dwd;f11;}return;}if(s[q][c]*){for(int i0; i9; i){dfs(w,q,c1,d*10i);}}else{dfs(w,q,c1,d*10(s[q][c]-0));}}5.输出for(int i1; in; i){//dfs(s[i].size(),i,0,0);if(dw0) cout -1endl;else cout dwendl;dw0; f10;}6.总结本题dfs很难用简单方法过

相关新闻

多轨道片段怎么精准替换

多轨道片段怎么精准替换

在剪映专业版的多轨道剪辑中,精准替换不满意片段同时保留现有整体编排,是二次创作中常见的实际需求。已确认的多轨道AI二次生成功能,支持在已排好的时间线上对单个不满意片段单独发起生成替换,自动保留其他轨道和整体剪辑结构&…

2026/11/17 11:32:21 阅读更多 →
Vlog调色工具怎么选

Vlog调色工具怎么选

Vlog通常会混合不同设备拍摄、在室内外多种光源环境下录制,调色工具的选择需要匹配素材原始条件和最终想要的统一风格,核心逻辑是先校正基础问题,再精细化调整色彩,最后匹配不同镜头的色调一致性。不存在适合所有Vlog的通用工具&a…

2026/11/5 3:29:14 阅读更多 →
AI生成镜头怎么统一色彩

AI生成镜头怎么统一色彩

AI生成多个视频镜头时,由于模型采样随机性、提示词描述差异或生成批次不同,很容易出现镜头间白平衡偏移、整体色调不一致、饱和度差异等问题,影响成片整体观感。要统一AI生成镜头的色彩,可以通过「选参考定调 → 批量色彩克隆 → …

2026/11/16 22:43:25 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/17 8:22:52 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/16 6:41:34 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/16 8:22:12 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/17 11:26:33 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/16 7:30:18 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/16 8:22:12 阅读更多 →

日新闻

周新闻

月新闻