当前位置: 首页 > news >正文

信息学奥赛一本通 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&#xff1a;【例5.1】素数环 【题目考点】 1. 深搜回溯 2. 质数 【解题思路】 1~n的数字构成一个环&#xff0c;要求相邻数字加和必须是质数。 该题最终输出的是一个序列&#xff0c;只不过逻辑上序列最后一个数字的下一个数字就是序列的第一个数字…...

Redis、MongoDB 和 MySQL评估

Redis、MongoDB 和 MySQL 是三种不同类型的数据库系统&#xff0c;各自有独特的特点和适用场景。MySQL 是一个关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;而 Redis 和 MongoDB 是非关系型数据库&#xff08;NoSQL&#xff09;。以下是对这三者的比较以及它…...

P1719 最大加权矩形

为了更好的备战 NOIP2013&#xff0c;电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为&#xff0c;我们不光需要机房&#xff0c;我们还需要运动&#xff0c;于是就决定找校长申请一块电脑组的课余运动场地&#xff0c;听说她们都是电脑组的高手&#xff0c;校长没有马上答应他们&#xf…...

在生产环境中部署和管理 Apache:运维从入门到精通

在生产环境中部署和管理 Apache:运维从入门到精通 引言 Apache HTTP Server(简称 Apache)作为世界上最受欢迎的 Web 服务器之一,因其稳定性、灵活性和丰富的模块支持而被广泛使用。从个人网站到企业级应用,Apache 都能游刃有余。然而,要想在生产环境中高效部署和管理 A…...

DeepSeek API 的获取与对话示例

代码文件下载&#xff1a;Code 在线链接&#xff1a;Kaggle | Colab 文章目录 注册并获取API环境依赖设置 API单轮对话多轮对话流式输出更换模型 注册并获取API 访问 https://platform.deepseek.com/sign_in 进行注册并登录&#xff1a; 新用户注册后将赠送 10 块钱余额&#…...

【愚公系列】《循序渐进Vue.js 3.x前端开发实践》027-组件的高级配置和嵌套

标题详情作者简介愚公搬代码头衔华为云特约编辑,华为云云享专家,华为开发者专家,华为产品云测专家,CSDN博客专家,CSDN商业化专家,阿里云专家博主,阿里云签约作者,腾讯云优秀博主,腾讯云内容共创官,掘金优秀博主,亚马逊技领云博主,51CTO博客专家等。近期荣誉2022年度…...

预测性维护系统:让设备“未卜先知”

预测性维护系统:让设备“未卜先知” 在工业4.0的浪潮中,设备管理正在向智能化转型。传统的设备维护方式,要么是定期维护(时间消耗大),要么是被动维修(问题发生后再处理)。这种方式效率低下且成本高昂。而预测性维护(Predictive Maintenance,简称PdM)则为设备管理提…...

Qt Ribbon使用实例

采用SARibbon创建简单的ribbon界面 实例代码如下所示&#xff1a; 1、头文件&#xff1a; #pragma once #include <SARibbonBar.h> #include "SARibbonMainWindow.h" class QTextEdit; class SAProjectDemo1 : public SARibbonMainWindow { Q_OBJECT pub…...

Midscene.js:重新定义UI自动化的新时代工具

前言 Midscene.js 是一个创新的、面向开发者的 UI 自动化解决方案&#xff0c;并通过人工智能技术简化自动化脚本的编写与维护。 它提供了三种核心方法——交互&#xff08;.ai, .aiAction&#xff09;、提取&#xff08;.aiQuery&#xff09;和断言&#xff08;.aiAssert&am…...

【C语言基础】编译并运行第一个C程序

博主未授权任何人或组织机构转载博主任何原创文章&#xff0c;感谢各位对原创的支持&#xff01; 博主链接 博客内容主要围绕&#xff1a; 5G/6G协议讲解 高级C语言讲解 Rust语言讲解 文章目录 编译并运行第一个C程序一、编译上面的程序二、运行上面的程序…...

处理 .gitignore 未忽略文件夹问题

本地删除缓存 例如 .idea 文件夹被其他同事误提交&#xff0c;那么他本地执行以下代码 git rm -r --cached .idea对应本地再提交即可...

php-phar打包避坑指南2025

有很多php脚本工具都是打包成phar形式&#xff0c;使用起来就很方便&#xff0c;那么如何自己做一个呢&#xff1f;也找了很多文档&#xff0c;也遇到很多坑&#xff0c;这里就来总结一下 phar安装 现在直接装yum php-cli包就有phar文件&#xff0c;很方便 可通过phar help查看…...

卡特兰数学习

1&#xff0c;概念 卡特兰数&#xff08;英语&#xff1a;Catalan number&#xff09;&#xff0c;又称卡塔兰数&#xff0c;明安图数。是组合数学中一种常出现于各种计数问题中的数列。它在不同的计数问题中频繁出现。 2&#xff0c;公式 卡特兰数的递推公式为&#xff1a;f(…...

第05章 10 地形梯度场模拟显示

在 VTK&#xff08;Visualization Toolkit&#xff09;中&#xff0c;可以通过计算地形数据的梯度场&#xff0c;并用箭头或线条来表示梯度方向和大小&#xff0c;从而模拟显示地形梯度场。以下是一个示例代码&#xff0c;展示了如何使用 VTK 和 C 来计算和显示地形数据的梯度场…...

2023CISCN初赛unzip

2023CISCN初赛unzip 随便上传一个文件&#xff0c;会自动跳转到uplaod.php目录下,源码如下&#xff1a; <?php error_reporting(0); highlight_file(__FILE__);$finfo finfo_open(FILEINFO_MIME_TYPE); if (finfo_file($finfo, $_FILES["file"]["tmp_name…...

计算机网络 (55)流失存储音频/视频

一、定义与特点 定义&#xff1a;流式存储音频/视频是指经过压缩并存储在服务器上的多媒体文件&#xff0c;客户端可以通过互联网边下载边播放这些文件&#xff0c;也称为音频/视频点播。 特点&#xff1a; 边下载边播放&#xff1a;用户无需等待整个文件下载完成即可开始播放…...

Linux通过docker部署京东矩阵容器服务

获取激活码 将京东无线宝app升级到最新版,然后打开首页,点击号 选择添加容器矩阵,然后获取激活码 运行容器 read -p "请输入你的激活码: " ACTIVECODE;read -p "请输入宿主机的缓存路径: " src;docker rm -f cmatrix;docker run -d -it --name cmatrix …...

【MySQL】悲观锁和乐观锁的原理和应用场景

悲观锁和乐观锁&#xff0c;并不是 MySQL 或者数据库中独有的概念&#xff0c;而是并发编程的基本概念。 主要区别在于&#xff0c;操作共享数据时&#xff0c;“悲观锁”认为数据出现冲突的可能性更大&#xff0c;而“乐观锁”则是认为大部分情况不会出现冲突&#xff0c;进而…...

Java Web-Tomcat Servlet

Web服务器-Tomcat Web服务器简介 Web 服务器是一种软件程序&#xff0c;它主要用于在网络上接收和处理客户端&#xff08;如浏览器&#xff09;发送的 HTTP 请求&#xff0c;并返回相应的网页内容或数据。以下是关于 Web 服务器的详细介绍&#xff1a; 功能 接收请求&#…...

老牌工具被破!

屏幕录制技术因其高效的信息传递能力在多个行业中得到了广泛应用&#xff0c;在教育领域&#xff0c;教师利用屏幕录制制作在线课程。在企业培训中&#xff0c;它为新员工提供了灵活的学习方式。在直播、游戏时&#xff0c;录制分享精彩内容。在客户支持中&#xff0c;客服人员…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...

前端调试HTTP状态码

1xx&#xff08;信息类状态码&#xff09; 这类状态码表示临时响应&#xff0c;需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分&#xff0c;客户端应继续发送剩余部分。 2xx&#xff08;成功类状态码&#xff09; 表示请求已成功被服务器接收、理解并处…...