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

《算法笔记》8.1小节——搜索专题->深度优先搜索(DFS)问题 C: 【递归入门】组合+判断素数

题目描述

已知 n 个整数b1,b2,…,bn

以及一个整数 k(k<n)。

从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。

例如当 n=4,k=3,4 个整数分别为 3,7,12,19 时,可得全部的组合与它们的和为:
    3+7+12=22  3+7+19=29  7+12+19=38  3+12+19=34。
  现在,要求你计算出和为素数共有多少种。

例如上例,只有一种的和为素数:3+7+19=29。

输入

第一行两个整数:n , k (1<=n<=20,k<n) 
第二行n个整数:x1,x2,…,xn (1<=xi<=5000000) 

输出

一个整数(满足条件的方案数)。 

样例输入
4 3
3 7 12 19
样例输出
1

分析:本质上是B题的强化版本,在B题基础上增加了求和和素数判断。基本上把B的代码拿过来改动一下就可以了。不过下面的代码是递归写的。

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include   <string>
#include   <vector>
#include   <cstdio>
#include    <queue>
#include    <stack>
#include    <ctime>
#include    <cmath>
#include      <map>
#include      <set>
#define ll long long
#define INF 0x3f3f3f3f
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,a) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#a<<"="<<(a)<<endl
using namespace std;void getprime(int *flag,vector<int>&prime)
{flag[0]=flag[1]=1;for(int i=2;i<=10000;++i)if(!flag[i])for(int j=i*i;j<=10000;j=j+i)flag[j]=1;for(int i=2;i<=10000;++i)if(!flag[i])prime.push_back(i);return;
}void getans(int n,int k,int index,int *num,int *flag,int *temp,vector<int>prime,vector<int>&ans,int pos)
{if(index==k){int sum=0,cnt=prime.size();for(int i=0;i<k;++i)sum+=temp[i];int f=0;for(int i=0;i<cnt;++i){if(sum%prime[i]==0&&sum!=prime[i]){f=1;break;}}if(!f)ans.push_back(sum);return;}for(int i=pos;i<n;++i){if(flag[i]==0){temp[index]=num[i],flag[i]=1;getans(n,k,index+1,num,flag,temp,prime,ans,i+1);flag[i]=0;}}return;
}int main(void)
{#ifdef testfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);clock_t start=clock();#endif //testint n,k;scanf("%d%d",&n,&k);int num[n+5]={0},flag[20000]={0},temp[k+5]={0};vector<int>prime,ans;for(int i=0;i<n;++i)scanf("%d",&num[i]);getprime(flag,prime);memset(flag,0,sizeof(int)*(n+5));getans(n,k,0,num,flag,temp,prime,ans,0);printf("%d\n",ans.size());#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位#endif //testreturn 0;
}

上面的代码比较繁琐,下面给出AI优化过的代码。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;#define ll long long// 判断某个数是否是素数(试除法)
bool is_prime(int num) {if (num < 2) return false;for (int i = 2; i * i <= num; ++i) {if (num % i == 0) return false;}return true;
}// 递归搜索所有 k 组合,并判断是否为素数
void dfs(int index, int sum, int count, int n, int k, vector<int>& num, int& result) {if (count == k) { // 选满 k 个数if (is_prime(sum)) result++;return;}for (int i = index; i < n; ++i) {dfs(i + 1, sum + num[i], count + 1, n, k, num, result);}
}int main() {int n, k;cin >> n >> k;vector<int> num(n);for (int i = 0; i < n; ++i) {cin >> num[i];}int result = 0;dfs(0, 0, 0, n, k, num, result);cout << result << endl;return 0;
}

 

相关文章:

《算法笔记》8.1小节——搜索专题->深度优先搜索(DFS)问题 C: 【递归入门】组合+判断素数

题目描述 已知 n 个整数b1,b2,…,bn 以及一个整数 k&#xff08;k&#xff1c;n&#xff09;。 从 n 个整数中任选 k 个整数相加&#xff0c;可分别得到一系列的和。 例如当 n4&#xff0c;k&#xff1d;3&#xff0c;4 个整数分别为 3&#xff0c;7&#xff0c;12&#xf…...

重生之我在学Vue--第8天 Vue 3 UI 框架(Element Plus)

重生之我在学Vue–第8天 Vue 3 UI 框架&#xff08;Element Plus&#xff09; 文章目录 重生之我在学Vue--第8天 Vue 3 UI 框架&#xff08;Element Plus&#xff09;前言一、Element Plus 基础&#xff1a;从安装到组件革命1.1 安装与两种引入模式全量引入&#xff08;适合快速…...

从前端视角理解消息队列:核心问题与实战指南

消息队列&#xff08;Message Queue&#xff09;是现代分布式系统的核心组件之一&#xff0c;它在前后端协作、系统解耦、流量削峰等场景中发挥着重要作用。本文从前端开发者视角出发&#xff0c;解析消息队列的关键问题&#xff0c;并结合实际场景给出解决方案。 一、为什么要…...

Mysql配置文件My.cnf(my.ini)配置参数说明

一、my.cnf 配置文件路径&#xff1a;/etc/my.cnf&#xff0c;在调整了该文件内容后&#xff0c;需要重启mysql才可生效。 1、主要参数 basedir path # 使用给定目录作为根目录(安装目录)。 datadir path # 从给定目录读取数据库文件。 pid-file filename # 为mysq…...

Docker 安装成功后,安装 Dify 中文版本的步骤

Docker 安装成功后&#xff0c;安装 Dify 中文版本的步骤如下1&#xff1a; 克隆 Dify 代码仓库&#xff1a;在终端中执行以下命令&#xff0c;将 Dify 源代码克隆至本地环境。 bash git clone https://github.com/langgenius/dify.git进入 Dify 的 docker 目录&#xff1a; b…...

Spring(4)——响应相关

一、返回静态页面 1.1**RestController和Controller** 想返回如下页面&#xff1a; 如果我们依旧使用原来的**RestController** 可以看到的是仅仅返回了字符串。 此时将**RestController改为Controller** 可以看到这次返回的是html页面。 那么**RestController和Controller…...

LPDDR5x电源使用Si电容对PI和PSIJ影响分析

SoC可能包含许多高速接口&#xff0c;其中LPDDR5X目前因为高带宽、低功耗、大容量等性能优势开始逐渐在AI计算、5G通信、视频处理等领域开始使用。LPDDR5X目前的速率高达8.533 GT/s&#xff0c;以及多个为这些接口供电的IO电压轨&#xff0c;而这些IO轨的PDN需要提供低阻抗&…...

[网络爬虫] 动态网页抓取 — Selenium 介绍 环境配置

&#x1f31f;想系统化学习爬虫技术&#xff1f;看看这个&#xff1a;[数据抓取] Python 网络爬虫 - 学习手册-CSDN博客 0x01&#xff1a;Selenium 工具介绍 Selenium 是一个开源的便携式自动化测试工具。它最初是为网站自动化测试而开发的&#xff0c;类似于我们玩游戏用的按…...

MySQL数据库操作

目录 SQL语句 1、SQL的背景 2、SQL的概念 SQL的分类 SQL的书写规范 MySQL数据库 1、MySQL数据库的编码 &#xff08;1&#xff09;utf8和utf8mb4的区别 &#xff08;2&#xff09;MySQL的字符集 &#xff08;3&#xff09;MySQL默认编码为 latin1 &#xff0c;如何更改…...

java之uniapp实现门店地图

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、后台实现1. 获取门店的经纬度2.api查询对应的sql 二 、小程序实现 前言 实现查询门店地址的功能&#xff0c;可以按照距离排序。使用技术&#xff1a;java…...

Git基本概念及使用

目录 一、git安装 二、git仓库基本概念 1. 远程仓库&#xff08;Remote&#xff09;&#xff1a; 2. 本地库&#xff08;Repository&#xff09;&#xff1a; 3. 分支&#xff08;Branch&#xff09;&#xff1a; 4.本地库和远程库的关系 三、git仓库的工作流程 四、gi…...

游戏引擎学习第147天

仓库:https://gitee.com/mrxiao_com/2d_game_3 上一集回顾 具体来说&#xff0c;我们通过隐式计算来解决问题&#xff0c;而不是像数字微分分析器那样逐步增加数据。我们已经涵盖了这个部分&#xff0c;并计划继续处理音量问题。不过&#xff0c;实际上我们现在不需要继续处理…...

docker私有仓库配置

基于 harbor 构建docker私有仓库 1、机器准备 os&#xff1a;openEuler 、rockylinux mem&#xff1a;4G disk&#xff1a;100G 2、关闭防火墙、禁用SELinux 3、安装docker和docker-compose yum install docker-ce -y配置加速 vim /etc/docker/d…...

PostgreSQL 18新特性之虚拟生成列

PostgreSQL 12 提供了生成列&#xff08;GENERATED ALWAYS AS STORED&#xff09;功能&#xff0c;但是只能支持存储型的生成列&#xff0c;需要占用存储空间&#xff0c;更新成本高。 为此&#xff0c;PostgreSQL 18 即将引入一个新的增强&#xff1a;虚拟生成列。这种类型的…...

燃气对我们生活的重要性体现在哪里?

燃气在我们的生活中有 多方面的重要性 &#xff0c;以下是燃气对我们生活的重要性的详细说明&#xff1a; 烹饪和热水供应 &#xff1a; 燃气是家庭烹饪的主要能源&#xff0c;能够快速、高效地加热食物&#xff0c;使家庭聚餐更加便捷和愉快。 燃气热水器能够在短时间内提供…...

简易分析 uni.chooseImage 拍照上传的基本知识点(附Demo)

目录 前言1. 基本知识2. Demo 前言 &#x1f91f; 找工作&#xff0c;来万码优才&#xff1a;&#x1f449; #小程序://万码优才/r6rqmzDaXpYkJZF 基本的介绍也可看官网&#xff1a;uni.chooseImage(options) 以下知识点主要用于学习了解&#xff0c;从实战中出发 1. 基本知识…...

私域流量时代的创新实践:以定制开发开源AI智能名片与S2B2C商城小程序源码为例的深度研究

摘要&#xff1a;在数字化转型的浪潮中&#xff0c;私域流量已成为企业获取用户、增强品牌影响力及实现销售转化的关键路径。本文首先概述了私域流量的概念及其重要性&#xff0c;随后通过分析故宫文创、B站跨年晚会及美妆品牌“完美日记”的成功案例&#xff0c;深入探讨了私域…...

preloaded-classes裁剪

系统预加载了哪些class类&#xff1f;system/etc/preloaded-classes 修改源代码&#xff1f; frameworks\base\config\preloaded-classes 默认位置&#xff0c;如果改了不生效&#xff0c;可能有其它模块的mk文件指定了preloaded-classes覆盖了framework模块&#xff0c;例如…...

JavaScript性能优化实战

在 JavaScript 开发中&#xff0c;性能优化是一个至关重要的方面&#xff0c;它可以提升应用的响应速度、减少资源消耗&#xff0c;从而提供更好的用户体验。以下是从多个方面进行 JavaScript 性能优化的详细实战内容&#xff1a; 1. 代码加载优化 1.1 异步加载脚本 使用 as…...

文件和异常

从文件中读取数据 读取整个文件 读取整个文件 要读取文件&#xff0c;需要一个包含几行文本的文件。下面首先创建一个文件&#xff0c;它包含精确 到小数点后30位的圆周率值&#xff0c;且在小数点后每10位处换行&#xff1a; pi_digits.txt 3.14159265358979323846264338…...

【AI大模型】LLM训练deepseek如何识别视频

要让像DeepSeek这样的大语言模型&#xff08;LLM&#xff09;具备视频识别能力&#xff0c;需要结合多模态学习技术&#xff0c;将视觉信息与文本语义进行融合。以下是实现这一目标的关键步骤和技术要点&#xff1a; --- 一、视频识别的核心挑战 1. 多模态数据&#xff1a;视频…...

【机械视觉】C#+VisionPro联合编程———【五、硬币检测小项目实现(C#+VisionPro联合编程和csv文件格式操作)】

【机械视觉】C#VisionPro联合编程———【五、硬币检测小项目实现(C#VisionPro联合编程和csv文件格式操作)】 项目介绍 总共有十二张检测的图片&#xff0c;当点击检测按钮时检测当前展示的图片并且将检测效果展示在表格中&#xff0c;当点击上一页或下一页时换检测图片&…...

空间域与频域图像处理

第一部分&#xff1a;空间域图像处理&#xff08;Part 1&#xff09; 1. 点操作&#xff08;Pixel-wise Operations&#xff09; 定义&#xff1a;仅基于单个像素的灰度值进行变换&#xff0c;不依赖邻域信息。 常见操作&#xff1a; 2. 邻域操作&#xff08;Neighborhood O…...

使用DeepSeek+蓝耘快速设计网页简易版《我的世界》小游戏

前言&#xff1a;如今&#xff0c;借助先进的人工智能模型与便捷的云平台&#xff0c;即便是新手开发者&#xff0c;也能开启创意游戏的设计之旅。DeepSeek 作为前沿的人工智能模型&#xff0c;具备强大的功能与潜力&#xff0c;而蓝耘智算云平台则为其提供了稳定高效的运行环境…...

使用 React 和 Ant Design 处理 Excel 和 CSV 文件

在现代 Web 开发中&#xff0c;文件上传和解析是常见的需求。本文将介绍如何使用 React 和 Ant Design 库来处理 Excel 和 CSV 文件的上传&#xff0c;并将提取的表头信息展示在表格中。 1. 项目基础 确保你已经创建了一个 React 项目&#xff0c;并安装了必要的依赖。可以使…...

js 使用 Web Workers 来实现一个精确的倒计时,即使ios手机锁屏或页面进入后台,倒计时也不会暂停。

## 效果如上 <!-- 将 main.js 和 worker.js 放在同一个目录下&#xff0c;然后在 HTML 文件中引入 main.js --><!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content&q…...

Java中的常用关键字

目录 static关键字 &#xff08;1&#xff09;static修饰成员变量 &#xff08;2&#xff09;static修饰成员方法 super和this关键字 super关键字 示例1&#xff1a;使用super调用父类的构造器 示例2&#xff1a;使用super访问父类的方法 示例3&#xff1a;使用super访问…...

pytest数据库测试文章推荐

参考链接&#xff1a; 第一部分&#xff1a;http://alextechrants.blogspot.fi/2013/08/unit-testing-sqlalchemy-apps.html第二部分&#xff1a;http://alextechrants.blogspot.fi/2014/01/unit-testing-sqlalchemy-apps-part-2.html...

ubuntu20.04 使用linuxdeployqt打包一个QT程序

问题描述:ubuntu 打包一个QT程序 解决方法&#xff1a; 1.安装linuxdeployqt linuxdeployqt的github网址&#xff1a;linuxdeplyoqt 我下载好了&#xff0c;适合大家的直接拿&#xff0c;已经改好名字为linuxdeployqt 链接: https://pan.baidu.com/s/1r25aVwRAh-sx4ksadj6…...

⭐算法OJ⭐经典题目分类索引(持续更新)

在编程竞赛和算法学习中&#xff0c;Online Judge&#xff08;OJ&#xff09;平台是程序员们磨练技能的重要工具。OJ平台上的题目种类繁多&#xff0c;涵盖了从基础数据结构到复杂算法的各个方面。为了更好地理解和掌握这些题目&#xff0c;对其进行分类是非常有必要的。这篇索…...

Redis-缓存穿透击穿雪崩

1. 穿透问题 缓存穿透问题就是查询不存在的数据。在缓存穿透中&#xff0c;先查缓存&#xff0c;缓存没有数据&#xff0c;就会请求到数据库上&#xff0c;导致数据库压力剧增。 解决方法&#xff1a; 给不存在的key加上空值&#xff0c;防止每次都会请求到数据库。布隆过滤器…...

mac使用Homebrew安装miniconda(mac搭建python环境),并在IDEA中集成miniconda环境

一、安装Homebrew mac安装brew 二、使用Homebrew安装miniconda brew search condabrew install miniconda安装完成后的截图&#xff1a; # 查看是否安装成功 brew list环境变量&#xff08;无需手动配置&#xff09; 先执行命令看能不能正常返回&#xff0c;如果不能正常…...

tomcat应用的作用以及安装,以及tomcat软件的开机自启动。

一.tomcat介绍 1.作用 tomcat是一款用来部署网站服务器的一款软件。 动态网站主流语言&#xff1a; PHP, lamp/lnmp平台 Java语言&#xff0c;运行在tomcat平台。【只要这个网站或者软件是Java语言写的&#xff0c;我们都可以在tomcat平台上去运行这个java程序。】 网站是…...

Javascript基础语法详解

面向对象的语言.脚本语言,不需要编译,浏览器解释即可运行 .用于控制网页的行为.浏览器的source可以打断点调试, console输入代码可以执行 use strict指令: 在“严格模式”下运行js代码, 防止意外创建全局变量等, 提高代码安全性和执行效率. 使用: 全局严格模式&#xff1a;…...

网络编程(师从韩顺平)

文章目录 续写前面没有提到的内容自定义线程JVM,JDK,JREJava 核心机制-Java 虚拟机 [JVM java virtual machine]JDKJREJDK、JRE 和 JVM 的包含关系 Java 技术体系平台 网络的相关概念网络通信网络Ip 地址ipv4 地址分类域名网络通信协议TCP 和 UDP InetAddress 类相关方法应用案…...

HTML嵌入CSS样式超详解(尊享)

一、行内样式&#xff08;Inline CSS&#xff09; 1. 定义与语法 行内样式是直接在HTML标签中使用style属性来定义样式。这种方式只对当前标签生效。 <tagname style"css 样式">2. 示例 <p style"color: red; font-size: 14px;">这是一个红…...

AI开源竞赛与硬件革命:2025年3月科技热点全景解读——阿里、腾讯领跑开源,英特尔、台积电重塑算力格局

目录 开源生态&#xff1a;阿里与腾讯的“技术对决” 1. 阿里云QwQ-32B&#xff1a;小参数撬动大性能的技术革命 2. 腾讯混元&#xff1a;视频创作的普惠化尝试 AI硬件与算力&#xff1a;全球供应链的“新战场” 1. 英特尔商用AI PC&#xff1a;端侧算力突围 2. 台积电千…...

无头浏览器与请求签名技术-Cloudflare防护

在实际数据采集实践中&#xff0c;许多目标网站&#xff08;例如 Amazon&#xff09;都会采用 Cloudflare 等防护措施&#xff0c;防止机器人和非正常流量。本文将分享一个故障场景下的排查与改进方案&#xff0c;讲述如何利用无头浏览器、请求签名技术以及爬虫代理 IP来实现数…...

6.聊天室环境安装 - Ubuntu22.04 - elasticsearch(es)的安装和使用

目录 介绍安装安装kibana安装ES客户端使用 介绍 Elasticsearch&#xff0c; 简称 ES&#xff0c;它是个开源分布式搜索引擎&#xff0c;它的特点有&#xff1a;分布式&#xff0c;零配置&#xff0c;自动发现&#xff0c;索引自动分片&#xff0c;索引副本机制&#xff0c;res…...

【NexLM 开源系列】让 AI 聊天更丝滑:SSE 实现流式对话!

&#x1f31f; 在这系列文章中&#xff0c;我们将一起探索如何搭建一个支持大模型集成项目 NexLM 的开发过程&#xff0c;从 架构设计 到 代码实战&#xff0c;逐步搭建一个支持 多种大模型&#xff08;GPT-4、DeepSeek 等&#xff09; 的 一站式大模型集成与管理平台&#xff…...

具备多种功能的PDF文件处理工具

软件介绍 在日常办公和学习场景中&#xff0c;PDF文件使用极为频繁&#xff0c;而一款功能强大的PDF编辑软件能大幅提升处理效率。 今天要介绍的Adobe Acrobat Pro DC 2024.005.20414&#xff0c;就具备像编辑Word文档一样便捷编辑PDF的能力。 PDF文档在学习和工作中广泛应用…...

electron+vue+webview内嵌网页并注入js

vue内嵌网页可以使用iframe实现内嵌网页&#xff0c;但是只能通过postMessage间接通信&#xff0c;在electron环境下&#xff0c;vue可以直接使用webview来内嵌网页&#xff0c;支持 executeJavaScript、postMessage、send 等丰富的通信机制。 使用 webview的优势 性能更佳&…...

机器学习常见面试题

常见基模型 1. 线性模型&#xff08;Linear Models&#xff09; 特点&#xff1a;通过线性组合特征进行预测&#xff0c;适合处理线性关系。常见类型&#xff1a; 线性回归&#xff08;Linear Regression&#xff09;逻辑回归&#xff08;Logistic Regression&#xff09;岭回…...

单片机OTA升级中Bootloader怎么判断APP有没有问题?

没开发过OTA的工程师&#xff0c;职业生涯是不完整的。因为它能让设备远程更新功能&#xff0c;太方便了&#xff0c;产品有了这个功能&#xff0c;再也不会跟硬件工程师一起背锅了。 不过&#xff0c;新手玩OTA&#xff0c;搞不好&#xff0c;也会翻车&#xff0c;比如下载过程…...

《OpenCV》—— dlib(换脸操作)

文章目录 dlib换脸介绍仿射变换在 dlib 换脸中的应用 换脸操作 dlib换脸介绍 dlib 换脸是基于 dlib 库实现的一种人脸替换技术&#xff0c;以下是关于它的详细介绍&#xff1a; 原理 人脸检测&#xff1a;dlib 库中包含先进的人脸检测器&#xff0c;如基于 HOG&#xff08;方向…...

从零开始实现大语言模型(十三):预训练大语言模型GPTModel

1. 前言 使用梯度下降算法通过下一个token预测任务预训练大语言模型GPTModel&#xff0c;前向传播流程每次会输入一个batch的长度均为context_len的训练样本&#xff0c;执行 batch_size context_len \text{batch\_size}\times\text{context\_len} batch_sizecontext_len次下…...

[C++面试] 对通透比较器了解多少?(较少涉及,可跳过)

一、入门 1、什么是比较器 在 C 中&#xff0c;比较器是一个可调用对象&#xff08;函数、函数对象或 Lambda 表达式&#xff09;&#xff0c;用于定义元素之间的比较规则。 用途&#xff1a;通常作为参数传递给标准库中的排序函数或关联容器&#xff0c;以指定元素的顺序。…...

【高分论文密码】AI大模型和R语言的全类型科研图形绘制,从画图、标注、改图、美化、组合、排序分解科研绘图每个步骤

在科研成果竞争日益激烈的当下&#xff0c;「一图胜千言」已成为高水平SCI期刊的硬性门槛——数据显示很多情况的拒稿与图表质量直接相关。科研人员普遍面临的工具效率低、设计规范缺失、多维数据呈现难等痛点&#xff0c;因此科研绘图已成为成果撰写中的至关重要的一个环节&am…...

el-input-number添加自定义内容class-unit

在el-input,el-input-number中有需要在输入框后面添加单位的需求&#xff0c;这时候就需要用到class-unit <el-input-number size"small" class-unit"%" class"inputNumberClass"></el-input-number>// css .inputNumberClass[clas…...

MYSQL学习笔记(十一):MYSQL数据类型讲解

前言&#xff1a; 学习和使用数据库可以说是程序员必须具备能力&#xff0c;这里将更新关于MYSQL的使用讲解&#xff0c;大概应该会更新30篇&#xff0c;涵盖入门、进阶、高级(一些原理分析);这一篇数据类型&#xff0c;比较多&#xff0c;但是我感觉了解即可&#xff0c;ai时…...