信息学奥赛一本通 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 服务器的详细介绍: 功能 接收请求&#…...
老牌工具被破!
屏幕录制技术因其高效的信息传递能力在多个行业中得到了广泛应用,在教育领域,教师利用屏幕录制制作在线课程。在企业培训中,它为新员工提供了灵活的学习方式。在直播、游戏时,录制分享精彩内容。在客户支持中,客服人员…...
OpenJSCAD.org与3D打印完美结合:从代码到实物的完整工作流程
OpenJSCAD.org与3D打印完美结合:从代码到实物的完整工作流程 【免费下载链接】OpenJSCAD.org JSCAD is an open source set of modular, browser and command line tools for creating parametric 2D and 3D designs with JavaScript code. It provides a quick, pr…...
从用户视角优化:让QGC地面站的盘旋半径显示更直观的3个实用技巧
从用户视角优化:让QGC地面站的盘旋半径显示更直观的3个实用技巧 在无人机飞行任务规划中,盘旋半径的准确显示直接关系到飞行安全和任务执行效率。QGroundControl(QGC)作为业界领先的开源地面站软件,其功能强大但某些细…...
FreeSWITCH 1.10.10 图形化部署实战 - 麒麟V10 SP3 X86/ARM双架构服务器安装与配置指南
1. FreeSWITCH与麒麟V10 SP3的完美组合 FreeSWITCH作为一款开源的软交换平台,在企业通信、呼叫中心、即时通讯等领域有着广泛应用。而麒麟V10 SP3作为国产操作系统的代表,在信创领域扮演着重要角色。将这两者结合起来,既能满足国产化需求&am…...
终极空洞骑士模组管理器:用Scarab实现10倍效率提升的完整指南
终极空洞骑士模组管理器:用Scarab实现10倍效率提升的完整指南 【免费下载链接】Scarab An installer for Hollow Knight mods written in Avalonia. 项目地址: https://gitcode.com/gh_mirrors/sc/Scarab 你是否曾经为《空洞骑士》安装模组时感到头疼&#x…...
终极指南:如何使用Harepacker-resurrected打造个性化MapleStory游戏体验
终极指南:如何使用Harepacker-resurrected打造个性化MapleStory游戏体验 【免费下载链接】Harepacker-resurrected All in one .wz file/map editor for MapleStory game files 项目地址: https://gitcode.com/gh_mirrors/ha/Harepacker-resurrected 你是否曾…...
Java应用内存泄漏排查实战:MAT工具从入门到精通(附常见问题解析)
Java应用内存泄漏排查实战:MAT工具从入门到精通 引言:为什么我们需要关注内存泄漏? 记得去年我们团队接手的一个电商项目吗?上线三个月后,系统开始频繁出现OOM(OutOfMemoryError)错误。每次重启…...
Nomic-Embed-Text-V2-MoE实战:基于卷积神经网络(CNN)的图文多模态检索
Nomic-Embed-Text-V2-MoE实战:基于卷积神经网络(CNN)的图文多模态检索 你有没有想过,让电脑像人一样,既能看懂图片,又能理解文字,还能把两者联系起来?比如,你拍一张商品…...
让AI成为开发伙伴:调用快马模型为养龙虾系统添加智能预测与问答功能
最近在开发一个养龙虾的智能决策系统,发现很多功能模块如果纯手写会非常耗时。尝试用AI辅助开发后,效率提升了不少,这里分享下具体实现思路和踩坑经验。 生长预测模块的实现 这个模块需要根据历史水温、投喂量等数据预测龙虾未来一周的生长情…...
002
...
解锁PlotJuggler数据可视化:工业时序数据处理与分析指南
解锁PlotJuggler数据可视化:工业时序数据处理与分析指南 【免费下载链接】PlotJuggler The Time Series Visualization Tool that you deserve. 项目地址: https://gitcode.com/gh_mirrors/pl/PlotJuggler PlotJuggler是一款专业的时序数据可视化工具&#x…...
