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

蓝桥OJ 2942数字王国之军训排队 DFS剪枝

 蓝桥OJ 2942数字王国之军训排队

#include<bits/stdc++.h>
using namespace std;const int N = 15;//最多10队
int a[N], n;
vector<int>v[N];//二维数组 v[i]记录队伍i中所有人的编号bool dfs(int cnt, int dep)
{if (dep == n+1){//判断合法性for (int i = 1; i <= n; i++){for (int j = 0; j < v[i].size(); j++){for (int k = j + 1; k < v[i].size(); k++){if (v[i][k] % v[i][j] == 0) return false;}}}return true;}//枚举每个人所属的队伍for (int i = 1; i <= cnt; i++){v[i].push_back(a[dep]);if (dfs(cnt,dep+1))return true;v[i].pop_back();}return false;
}
int main()
{cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);//因为n的范围比较小,所以可以从小到大遍历出最少可以分成的队伍for (int i = 1; i <= n; i++){if (dfs(i, 1)){cout << i << '\n';break;}}return 0;
}

上面的方法有一个测试点出现了超时,所以下面用剪枝修改  

#include<bits/stdc++.h>
using namespace std;const int N = 15;//最多10队
int a[N], n;
vector<int>v[N];//二维数组 v[i]记录队伍i中所有人的编号bool dfs(int cnt, int dep)
{if (dep == n+1) return true;//枚举每个人所属的队伍for (int i = 1; i <= cnt; i++){bool tag = true;for (const auto& j : v[i]){if (a[dep] % j == 0){tag = false;break;}}if (!tag)continue;v[i].push_back(a[dep]);if (dfs(cnt,dep+1))return true;v[i].pop_back();}return false;
}
int main()
{cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);//因为n的范围比较小,所以可以从小到大遍历出最少可以分成的队伍for (int i = 1; i <= n; i++){if (dfs(i, 1)){cout << i << '\n';break;}}return 0;
}

相关文章:

蓝桥OJ 2942数字王国之军训排队 DFS剪枝

蓝桥OJ 2942数字王国之军训排队 #include<bits/stdc.h> using namespace std;const int N 15;//最多10队 int a[N], n; vector<int>v[N];//二维数组 v[i]记录队伍i中所有人的编号bool dfs(int cnt, int dep) {if (dep n1){//判断合法性for (int i 1; i < n; …...

SSL证书

SSL证书&#xff08;Secure Sockets Layer证书&#xff09;是一种网络安全协议&#xff0c;用于在互联网上建立加密链接&#xff0c;确保数据在从用户浏览器到服务器之间传输的过程中保持私密性和完整性。尽管现在实际上已经被TLS&#xff08;Transport Layer Security&#xf…...

【C++】string 类 ( 上)

标准库中的string类 注意&#xff1a; 1. string是表示字符串的字符串类 2. 该类的接口与常规容器的接口基本相同&#xff0c;再添加了一些专门用来操作string的常规操作。 比特就业课 3. string在底层实际是&#xff1a;basic_string模板类的别名&#xff0c;typedef basi…...

《中华人民共和国消防法》(2021年修订版)解读

单选题&#xff08;共7题&#xff0c;每题5分&#xff09; 1、举办大型群众性活动&#xff0c;承办人应当依法向&#xff08;&#xff09;申请安全许可。 正确答案&#xff1a;B、公安机关 2、违反消防安全规定进入生产、储存易燃易爆危险品场所的&#xff0c;情节严重的要处…...

vue+element模仿实现云码自动验证码识别平台官网

一、项目介绍 项目使用传统vue项目结构实现&#xff0c;前端采用element实现。 element官网&#xff1a;Element - The worlds most popular Vue UI framework 云码官网地址&#xff1a;云码-自动验证码识别平台_验证码识别API接口_免费验证码软件 项目截图&#xff0c;支持…...

蓝桥杯练习系统(算法训练)ALGO-992 士兵杀敌(二)

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 问题描述 南将军手下有N个士兵&#xff0c;分别编号1到N&#xff0c;这些士兵的杀敌数都是已知的。   小工是南将军手下的军师&…...

Pycharm下如何生成exe软件

第一步 下载pyinstaller pip install pyinstaller 对pyinstaller第二步 使用pyinstaller cmd切换到项目目录执行命令:pyinstaller --add-data “./templates;templates” 入口文件名.py...

KubeSphere平台安装系列之三【Linux多节点部署KubeSphere】(3/3)

**《KubeSphere平台安装系列》** 【Kubernetes上安装KubeSphere&#xff08;亲测–实操完整版&#xff09;】&#xff08;1/3&#xff09; 【Linux单节点部署KubeSphere】&#xff08;2/3&#xff09; 【Linux多节点部署KubeSphere】&#xff08;3/3&#xff09; **《KubeS…...

YOLOv9独家改进|动态蛇形卷积Dynamic Snake Convolution与空间和通道重建卷积SCConv与RepNCSPELAN4融合

专栏介绍&#xff1a;YOLOv9改进系列 | 包含深度学习最新创新&#xff0c;主力高效涨点&#xff01;&#xff01;&#xff01; 一、改进点介绍 Dynamic Snake Convolution是一种针对细长微弱的局部结构特征与复杂多变的全局形态特征设计的卷积模块。 SCConv是一种即插即用的空间…...

XSS初级漏洞靶场

一、环境的搭建 可以在githb上找靶机包&#xff0c;使用小皮面板搭建在自己本机 与此文章类似&#xff08;放在www目录下&#xff09; 二、XSS漏洞简介 1、什么是xss漏洞 当用户访问被xss注入的网页&#xff0c;xss代码就会被提取出来。用户浏览器就会解析这段xss代码&…...

k8s pv与pvc理解与实践

参考文章&#xff1a; https://blog.csdn.net/qq_41337034/article/details/117220475 一、 pv/pvc简述 Pv是指PersistentVolume&#xff0c;中文含义是持久化存储卷是对底层的共享存储的一种抽象&#xff0c;Pv由管理员进行配置和创建&#xff0c;只要包含存储能力&#xff…...

Unity游戏输入系统(新版+旧版)

使用新版还是旧版 旧版 using System.Collections; using System.Collections.Generic; using UnityEngine;public class c5 : MonoBehaviour {void Start(){}void Update(){// 注意要在游戏中 点鼠标键盘进行测试// 鼠标// 0左键 1右键 2滚轮if (Input.GetMouseButtonDown(0)…...

区块链媒体:链游媒体宣发渠道9个方法分享-华媒舍

在当今的游戏市场中&#xff0c;要想让自己开发的游戏脱颖而出&#xff0c;宣传策略的选择也至关重要。链游媒体是一种有效的宣发渠道&#xff0c;通过它们可以向广大玩家推广游戏并提高知名度。下面介绍9个链游媒体宣发渠道&#xff0c;帮助你的游戏走向成功。 1. 游戏公众号 …...

LeetCode--42

42. 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [0,1,0,2,1,0,1,…...

【解决】虚幻导入FBX模型不是一个整体

问题&#xff1a; 现在有一个汽车的fbx模型&#xff0c;导入虚幻引擎&#xff0c;导入后变成了很多汽车零件模型。 解决&#xff1a; 把“合并网格体”勾选上&#xff0c;解决问题。...

第四十八回 解珍解宝双越狱 孙立孙新大劫牢-Python模块和包概念与使用

吴用对宋江说&#xff0c;有个人&#xff0c;他是石勇的关系&#xff0c;与祝家庄的峦廷玉关系好&#xff0c;还是杨林、邓飞的老相识&#xff0c;他有一计.... 原来在宋江攻打祝家庄的时间段&#xff0c;山东海边登州也发生了一件事。登州山下有一家猎户&#xff0c;弟兄两个…...

【Spring连载】使用Spring Data访问 MongoDB----对象映射之属性转换器

【Spring连载】使用Spring Data访问 MongoDB----对象映射之属性转换器 一、声明式值转换器二、编程式值转换器注册三、MongoCustomConversions配置 虽然基于类型的转换已经提供了影响目标存储中某些类型的转换和表示的方法&#xff0c;但当仅考虑特定类型的某些值或属性进行转换…...

【axiox】前后端接口通讯数据交互

重要全局配置&#xff1a; axios.create(); 设置axios请求的公共配置信息。 service.interceptors.request.use((config)>{}) 请求拦截器 service.interceptors.response.use((res)>{},(err)>{}) 响应拦截器 const source axios.CancelToken.source(); 用…...

《Linux C编程实战》笔记:共享内存

共享内存是分配一块能被其他进程访问的内存。每个共享内存段在内核中维护一个内部数据结构shmid_ds(和消息队列、信号量一样)&#xff0c;该结构定义在头文件linux/shm.h中,这是我从源码里抄的 #include<linux/shm.h> struct shmid_ds {struct ipc_perm shm_perm; /* 操…...

【GitHub】修改默认分支

GitHub的默认分支为main&#xff0c;但我们常常习惯使用master作为默认分支&#xff0c;那在GitHub上如何将master修改为默认分支呢&#xff1f; 全局修改 点击头像&#xff0c;选择菜单栏中的设置 输入master作为默认分支&#xff0c;然后执行updating即可&#xff01; 单项…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...

小智AI+MCP

什么是小智AI和MCP 如果还不清楚的先看往期文章 手搓小智AI聊天机器人 MCP 深度解析&#xff1a;AI 的USB接口 如何使用小智MCP 1.刷支持mcp的小智固件 2.下载官方MCP的示例代码 Github&#xff1a;https://github.com/78/mcp-calculator 安这个步骤执行 其中MCP_ENDPOI…...

LUA+Reids实现库存秒杀预扣减 记录流水 以及自己的思考

目录 lua脚本 记录流水 记录流水的作用 流水什么时候删除 我们在做库存扣减的时候&#xff0c;显示基于Lua脚本和Redis实现的预扣减 这样可以在秒杀扣减的时候保证操作的原子性和高效性 lua脚本 // ... 已有代码 ...Overridepublic InventoryResponse decrease(Inventor…...

Java中栈的多种实现类详解

Java中栈的多种实现类详解&#xff1a;Stack、LinkedList与ArrayDeque全方位对比 前言一、Stack类——Java最早的栈实现1.1 Stack类简介1.2 常用方法1.3 优缺点分析 二、LinkedList类——灵活的双端链表2.1 LinkedList类简介2.2 常用方法2.3 优缺点分析 三、ArrayDeque类——高…...

在Spring Boot中集成RabbitMQ的完整指南

前言 在现代微服务架构中&#xff0c;消息队列&#xff08;Message Queue&#xff09;是实现异步通信、解耦系统组件的重要工具。RabbitMQ 是一个流行的消息中间件&#xff0c;支持多种消息协议&#xff0c;具有高可靠性和可扩展性。 本博客将详细介绍如何在 Spring Boot 项目…...

Oracle实用参考(13)——Oracle for Linux物理DG环境搭建(2)

13.2. Oracle for Linux物理DG环境搭建 Oracle 数据库的DataGuard技术方案,业界也称为DG,其在数据库高可用、容灾及负载分离等方面,都有着非常广泛的应用,对此,前面相关章节已做过较为详尽的讲解,此处不再赘述。 需要说明的是, DG方案又分为物理DG和逻辑DG,两者的搭建…...