信息学奥赛一本通 2110:【例5.1】素数环
【题目链接】
ybt 2110:【例5.1】素数环
【题目考点】
1. 深搜回溯
2. 质数
【解题思路】
1~n的数字构成一个环,要求相邻数字加和必须是质数。
该题最终输出的是一个序列,只不过逻辑上序列最后一个数字的下一个数字就是序列的第一个数字。数值1一定在这个序列中,因此我们让序列第1个数字就是数值1。
而后使用深搜算法依次确定第2个数字,第3个数字。。。
在确定第k个数字时,首先该数字只能是1~n中的数字,其次该数字必须没有使用过,而且该数字和前一个数字(第k-1个数字)的加和必须是质数。将可能的满足以上条件的数字作为序列的第k个数字。
当k为n+1,也就是满足k>n时,已经确定了序列中的n个数字,此时如果第1个数字和第n个数字的加和也是质数,那么就确定了一个满足条件的质数环,将序列中的数字输出。
可以使用标志位isOver记录是否已经找到解。如果已经找到解,那么递归调用可以直接返回,不用继续进行搜索。
【题解代码】
解法1:深搜回溯
#include <bits/stdc++.h>
using namespace std;
#define N 35
int n, a[N];
bool vis[N], isOver;
bool isPrime(int x)//判断x是否是质数
{if(x < 2)return false;for(int i = 2; i*i <= x; ++i) if(x%i == 0)return false;return true;
}
void dfs(int k)
{if(isOver)return;if(k > n){if(isPrime(a[n]+a[1])){isOver = true;for(int i = 1; i <= n; ++i)cout << a[i] << ' ';cout << endl;}return;}for(int i = 1; i <= n; ++i) if(!vis[i] && isPrime(a[k-1]+i)){vis[i] = true;a[k] = i;//选择数值i作为第k个数字dfs(k+1);vis[i] = false;}
}
int main()
{cin >> n;a[1] = 1;vis[1] = true;dfs(2);return 0;
}
相关文章:
信息学奥赛一本通 2110:【例5.1】素数环
【题目链接】 ybt 2110:【例5.1】素数环 【题目考点】 1. 深搜回溯 2. 质数 【解题思路】 1~n的数字构成一个环,要求相邻数字加和必须是质数。 该题最终输出的是一个序列,只不过逻辑上序列最后一个数字的下一个数字就是序列的第一个数字…...
Redis、MongoDB 和 MySQL评估
Redis、MongoDB 和 MySQL 是三种不同类型的数据库系统,各自有独特的特点和适用场景。MySQL 是一个关系型数据库管理系统(RDBMS),而 Redis 和 MongoDB 是非关系型数据库(NoSQL)。以下是对这三者的比较以及它…...
P1719 最大加权矩形
为了更好的备战 NOIP2013,电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为,我们不光需要机房,我们还需要运动,于是就决定找校长申请一块电脑组的课余运动场地,听说她们都是电脑组的高手,校长没有马上答应他们…...
在生产环境中部署和管理 Apache:运维从入门到精通
在生产环境中部署和管理 Apache:运维从入门到精通 引言 Apache HTTP Server(简称 Apache)作为世界上最受欢迎的 Web 服务器之一,因其稳定性、灵活性和丰富的模块支持而被广泛使用。从个人网站到企业级应用,Apache 都能游刃有余。然而,要想在生产环境中高效部署和管理 A…...
DeepSeek API 的获取与对话示例
代码文件下载:Code 在线链接:Kaggle | Colab 文章目录 注册并获取API环境依赖设置 API单轮对话多轮对话流式输出更换模型 注册并获取API 访问 https://platform.deepseek.com/sign_in 进行注册并登录: 新用户注册后将赠送 10 块钱余额&#…...
【愚公系列】《循序渐进Vue.js 3.x前端开发实践》027-组件的高级配置和嵌套
标题详情作者简介愚公搬代码头衔华为云特约编辑,华为云云享专家,华为开发者专家,华为产品云测专家,CSDN博客专家,CSDN商业化专家,阿里云专家博主,阿里云签约作者,腾讯云优秀博主,腾讯云内容共创官,掘金优秀博主,亚马逊技领云博主,51CTO博客专家等。近期荣誉2022年度…...
预测性维护系统:让设备“未卜先知”
预测性维护系统:让设备“未卜先知” 在工业4.0的浪潮中,设备管理正在向智能化转型。传统的设备维护方式,要么是定期维护(时间消耗大),要么是被动维修(问题发生后再处理)。这种方式效率低下且成本高昂。而预测性维护(Predictive Maintenance,简称PdM)则为设备管理提…...
Qt Ribbon使用实例
采用SARibbon创建简单的ribbon界面 实例代码如下所示: 1、头文件: #pragma once #include <SARibbonBar.h> #include "SARibbonMainWindow.h" class QTextEdit; class SAProjectDemo1 : public SARibbonMainWindow { Q_OBJECT pub…...
Midscene.js:重新定义UI自动化的新时代工具
前言 Midscene.js 是一个创新的、面向开发者的 UI 自动化解决方案,并通过人工智能技术简化自动化脚本的编写与维护。 它提供了三种核心方法——交互(.ai, .aiAction)、提取(.aiQuery)和断言(.aiAssert&am…...
【C语言基础】编译并运行第一个C程序
博主未授权任何人或组织机构转载博主任何原创文章,感谢各位对原创的支持! 博主链接 博客内容主要围绕: 5G/6G协议讲解 高级C语言讲解 Rust语言讲解 文章目录 编译并运行第一个C程序一、编译上面的程序二、运行上面的程序…...
处理 .gitignore 未忽略文件夹问题
本地删除缓存 例如 .idea 文件夹被其他同事误提交,那么他本地执行以下代码 git rm -r --cached .idea对应本地再提交即可...
php-phar打包避坑指南2025
有很多php脚本工具都是打包成phar形式,使用起来就很方便,那么如何自己做一个呢?也找了很多文档,也遇到很多坑,这里就来总结一下 phar安装 现在直接装yum php-cli包就有phar文件,很方便 可通过phar help查看…...
卡特兰数学习
1,概念 卡特兰数(英语:Catalan number),又称卡塔兰数,明安图数。是组合数学中一种常出现于各种计数问题中的数列。它在不同的计数问题中频繁出现。 2,公式 卡特兰数的递推公式为:f(…...
第05章 10 地形梯度场模拟显示
在 VTK(Visualization Toolkit)中,可以通过计算地形数据的梯度场,并用箭头或线条来表示梯度方向和大小,从而模拟显示地形梯度场。以下是一个示例代码,展示了如何使用 VTK 和 C 来计算和显示地形数据的梯度场…...
2023CISCN初赛unzip
2023CISCN初赛unzip 随便上传一个文件,会自动跳转到uplaod.php目录下,源码如下: <?php error_reporting(0); highlight_file(__FILE__);$finfo finfo_open(FILEINFO_MIME_TYPE); if (finfo_file($finfo, $_FILES["file"]["tmp_name…...
计算机网络 (55)流失存储音频/视频
一、定义与特点 定义:流式存储音频/视频是指经过压缩并存储在服务器上的多媒体文件,客户端可以通过互联网边下载边播放这些文件,也称为音频/视频点播。 特点: 边下载边播放:用户无需等待整个文件下载完成即可开始播放…...
Linux通过docker部署京东矩阵容器服务
获取激活码 将京东无线宝app升级到最新版,然后打开首页,点击号 选择添加容器矩阵,然后获取激活码 运行容器 read -p "请输入你的激活码: " ACTIVECODE;read -p "请输入宿主机的缓存路径: " src;docker rm -f cmatrix;docker run -d -it --name cmatrix …...
【MySQL】悲观锁和乐观锁的原理和应用场景
悲观锁和乐观锁,并不是 MySQL 或者数据库中独有的概念,而是并发编程的基本概念。 主要区别在于,操作共享数据时,“悲观锁”认为数据出现冲突的可能性更大,而“乐观锁”则是认为大部分情况不会出现冲突,进而…...
Java Web-Tomcat Servlet
Web服务器-Tomcat Web服务器简介 Web 服务器是一种软件程序,它主要用于在网络上接收和处理客户端(如浏览器)发送的 HTTP 请求,并返回相应的网页内容或数据。以下是关于 Web 服务器的详细介绍: 功能 接收请求&#…...
老牌工具被破!
屏幕录制技术因其高效的信息传递能力在多个行业中得到了广泛应用,在教育领域,教师利用屏幕录制制作在线课程。在企业培训中,它为新员工提供了灵活的学习方式。在直播、游戏时,录制分享精彩内容。在客户支持中,客服人员…...
Qwen3-VL-30B部署避坑指南:从下载到运行一气呵成
Qwen3-VL-30B部署避坑指南:从下载到运行一气呵成 1. 为什么选择Qwen3-VL-30B Qwen3-VL-30B是目前通义千问系列中最强大的视觉-语言模型,它在多个方面实现了显著提升: 更优秀的文本理解和生成:能够处理复杂语义和长文本更深入的…...
VMware 16 安装win,Win11推荐下载链接(不要选arm)
目录Win11下载链接待续、更新中......Win11下载链接 ed2k://|file|zh-cn_windows_11_consumer_editions_version_22h2_updated_sep_2022_x64_dvd_23d39103.iso|5579771904|33C7EC6485AD8C55ADFB550FA1A0F270|/ 待续、更新中… 1 顿号、: 先使用ctrl. ,再使用一遍切…...
别再只盯着数据了!用Arduino+GP2Y1014AU传感器,手把手教你做个能“看见”空气的PM2.5监测仪
用Arduino打造智能PM2.5监测仪:从硬件连接到可视化交互 在空气质量日益受到关注的今天,拥有一个实时监测PM2.5浓度的设备不仅能提升生活品质,还能为健康保驾护航。不同于市面上千篇一律的商用监测仪,自己动手打造一个兼具实用性和…...
嵌入式系统中的累加和校验算法原理与实现
1. 累加和校验算法概述在嵌入式系统开发中,数据通信的可靠性至关重要。想象一下,当你通过无线模块控制一台工业机器人时,如果传输的运动指令数据出现错误,可能导致机械臂做出完全不可预测的动作,轻则损坏产品ÿ…...
告别重复造轮子:用快马AI一键生成可配置的魔鬼面具UI组件库
作为一个经常需要处理各种UI组件的前端开发者,最近在做一个万圣节主题项目时,遇到了一个有趣的挑战:需要快速开发一套可配置的魔鬼面具组件库。传统手动编码方式不仅耗时,而且难以应对多风格需求。幸运的是,我发现了In…...
w3x2lni:魔兽地图跨版本兼容解决方案技术指南
w3x2lni:魔兽地图跨版本兼容解决方案技术指南 【免费下载链接】w3x2lni 魔兽地图格式转换工具 项目地址: https://gitcode.com/gh_mirrors/w3/w3x2lni 价值定位:破解魔兽地图版本壁垒 当你尝试在1.32.8版本魔兽争霸III中运行经典的1.24.4地图时&…...
AI报告文档审核赋能人才培养:IACheck打造环境检测人机协同审核虚拟仿真新体系
在环境检测行业持续走向精细化与规范化的过程中,报告审核能力逐渐成为影响整体质量的重要因素。然而,与检测设备和分析技术不断升级相比,审核人员的培养却长期依赖经验积累与“师带徒”模式,这种方式虽然能够传递实践经验…...
终极空洞骑士模组管理器:用Scarab实现10倍效率提升的完整指南
终极空洞骑士模组管理器:用Scarab实现10倍效率提升的完整指南 【免费下载链接】Scarab An installer for Hollow Knight mods written in Avalonia. 项目地址: https://gitcode.com/gh_mirrors/sc/Scarab 你是否曾经为《空洞骑士》安装模组时感到头疼&#x…...
Wireshark抓包实战:用一道CTF题彻底搞懂IP分片与UDP重组
Wireshark抓包实战:用一道CTF题彻底搞懂IP分片与UDP重组 在网络安全竞赛中,一个看似简单的UDP传输任务可能隐藏着协议层面的精妙设计。去年CyBRICS赛事中的lx100题目就完美诠释了这一点——参赛者需要从相机传输的UDP流量中提取图片,而真正的…...
从GC停顿2.3s到零暂停:Java函数GraalVM Native Image迁移全周期复盘(含12个兼容性雷区)
第一章:从GC停顿2.3s到零暂停:Java函数GraalVM Native Image迁移全周期复盘(含12个兼容性雷区)在高吞吐、低延迟的Serverless函数场景中,一个Spring Boot微服务因频繁Full GC导致单次停顿高达2.3秒,严重违反…...
