信息学奥赛一本通 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 服务器的详细介绍: 功能 接收请求&#…...
老牌工具被破!
屏幕录制技术因其高效的信息传递能力在多个行业中得到了广泛应用,在教育领域,教师利用屏幕录制制作在线课程。在企业培训中,它为新员工提供了灵活的学习方式。在直播、游戏时,录制分享精彩内容。在客户支持中,客服人员…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统
Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...
一些实用的chrome扩展0x01
简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序,无论是测试应用程序、搜寻漏洞还是收集情报,它们都能提升工作流程。 FoxyProxy 代理管理工具,此扩展简化了使用代理(如 Burp…...
