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

蓝桥杯 18.分考场

news 来源：原创 2025/7/22 11:49:18

分考场

原题目链接

题目描述

有 n 个人参加某项特殊考试。

为了公平，要求任何两个认识的人不能分在同一个考场。

你的任务是求出最少需要分几个考场才能满足这个条件。

输入描述

  • 第一行：一个整数 n，表示参加考试的人数（1 ≤ n ≤ 100）。
  • 第二行：一个整数 m，表示接下来有 m 行数据。
  • 接下来 m 行：每行两个整数 a, b，表示第 a 个人与第 b 个人认识（1 ≤ a, b ≤ n）。

输出描述

输出一个整数，表示最少需要的考场数。

输入样例

5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

输出样例

4

c++代码

#include<bits/stdc++.h>using namespace std;vector<unordered_set<int>> st;
vector<vector<int>> arr;int n, m, a, b, ans = INT_MAX, myclass = 0;void dfs(int index) {if (myclass >= ans) return;if (index == n + 1) {ans = min(ans, myclass);return;}for (int i = 1; i <= myclass; i++) {bool key = true;for (int x : arr[index]) {if (st[i].find(x) != st[i].end()) {key = false;break;}}if (key) {st[i].insert(index);dfs(index + 1);st[i].erase(index);}}myclass++;st[myclass].insert(index);dfs(index + 1);st[myclass].erase(index);myclass--;
}int main() {cin >> n >> m;arr = vector<vector<int>>(n + 1);st = vector<unordered_set<int>>(101);while(m--) {cin >> a >> b;arr[a].push_back(b), arr[b].push_back(a);}dfs(1);cout << ans;return 0;
}//by wqs

题目解析

这个题目就是个暴力题，会用题目的认识关系剪枝就行。

对于第index个人，假设当前有myclass(初始化为0)个教室，枚举1 - myclass个教室，让index加入，取最终需要教室最小的就行，当然如果这间教室有index认识的人，就枚举下一个教室，也就是剪枝。

for (int i = 1; i <= myclass; i++) {bool key = true;for (int x : arr[index]) {if (st[i].find(x) != st[i].end()) {key = false;break;}}if (key) {st[i].insert(index);dfs(index + 1);st[i].erase(index);}
}

当然还有一种情况，对于第index个人，可以去一个全新的教室

myclass++;
st[myclass].insert(index);
dfs(index + 1);
st[myclass].erase(index);
myclass--;

相关文章：

蓝桥杯 18.分考场

分考场 原题目链接 题目描述 有 n 个人参加某项特殊考试。 为了公平&#xff0c;要求任何两个认识的人不能分在同一个考场。 你的任务是求出最少需要分几个考场才能满足这个条件。 输入描述 第一行&#xff1a;一个整数 n&#xff0c;表示参加考试的人数&#xff08;1 ≤…...

编程日记 2025/7/22 11:49:18

大文件分片上传进阶版（新增md5校验、上传进度展示、并行控制，智能分片、加密上传、断点续传、自动重试），实现四位一体的网络感知型大文件传输系统‌

上篇文章我们总结了大文件分片上传的主要核心&#xff0c;但是我对md5校验和上传进度展示这块也比较感兴趣&#xff0c;所以在deepseek的帮助下&#xff0c;扩展了一下我们的代码&#xff0c;如果有任何问题和想法&#xff0c;非常欢迎大家在评论区与我交流&#xff0c;我需要学…...

编程日记 2025/7/22 11:45:08

【项目管理】成本类计算 笔记

项目管理-相关文档&#xff0c;希望互相学习&#xff0c;共同进步 风123456789&#xff5e;-CSDN博客 &#xff08;一&#xff09;知识总览 项目管理知识域 知识点&#xff1a; &#xff08;项目管理概论、立项管理、十大知识域、配置与变更管理、绩效域&#xff09; 对应&…...

编程日记 2025/7/22 11:35:14

Redis 事务

事务介绍 Redis 事务和 MySQL 事务在概念上类似的 把一些列的操作绑定成一组&#xff0c;让这一组能够批量执行 MySQL 事务 原子性&#xff1a;把多个操作打包成一个整体 一致性&#xff1a;事务执行前后数据合理 持久性&#xff1a;事务做出的操作都会修改硬盘 隔离性&#…...

编程日记 2025/7/22 11:44:02

JavaScript day5

立即执行函数 <script>(function(){ console.log//函数不需调用&#xff0c;立马执行 })() </script> //另外写法 <script> (function(){}()) </script> 常见的内置对象 Math console.dir()——打印对象的 使用Math中的属性——console.log(Math.…...

编程日记 2025/7/22 11:13:08

辛格迪客户案例 | 浙江高跖医药委托生产质量管理协同(OWL MAH)项目

一、案例概述 浙江高跖医药科技股份有限公司是一家集“研、产、销”为一体的专业化药品持证企业。高跖医药自成立之初就建立并运行着一套相对完善的质量管理体系&#xff0c;涵盖了药品的研发、生产监管及销售。高跖医药于2022年选择实施了辛格迪的“委托生产质量管理协同解决…...

编程日记 2025/7/22 11:20:46

科学养生指南：解锁健康生活新方式

在快节奏的现代生活中&#xff0c;健康养生已成为人们关注的焦点。科学合理的养生方式&#xff0c;能帮助我们增强体质、预防疾病&#xff0c;享受更优质的生活。​ 饮食是健康养生的基石。遵循 “均衡饮食” 原则&#xff0c;每日饮食需包含谷类、蔬菜水果、优质蛋白质和健康…...

编程日记 2025/7/22 11:24:24

FreeRTos学习记录--2.内存管理

后续的章节涉及这些内核对象&#xff1a;task、queue、semaphores和event group等。为了让FreeRTOS更容易使用&#xff0c;这些内核对象一般都是动态分配&#xff1a;用到时分配&#xff0c;不使用时释放。使用内存的动态管理功能&#xff0c;简化了程序设计&#xff1a;不再需…...

编程日记 2025/7/22 11:26:14

C++ 操作符重载Operator

C可以重载大多数操作符&#xff0c;如算术运算符号&#xff0c;-号。 位操作符<<,>> 下标符号[]等都可以重载。 重载的意思&#xff0c;是让这些符号&#xff0c;按你定义的行为来执行代码&#xff0c;但是这种自定义&#xff0c;是有限制的&#xff0c;必须有一…...

编程日记 2025/7/22 11:14:24

SBTI科学碳目标认证有什么要求？SBTI认证的好处？

SBTi&#xff08;科学碳目标倡议&#xff09;认证要求与好处 SBTi&#xff08;Science Based Targets initiative&#xff0c;科学碳目标倡议&#xff09;是由全球环境信息研究中心&#xff08;CDP&#xff09;、联合国全球契约&#xff08;UNGC&#xff09;、世界资源研究所&…...

编程日记 2025/7/22 11:20:46

RS232转Profibus DP网关：技术革新！

RS232转Profibus DP网关&#xff1a;技术革新&#xff01; 在工业自动化领域&#xff0c;通讯协议的多样性为系统设计提供了灵活性&#xff0c;但同时也带来了不同设备间通信的挑战。其中&#xff0c;RS232和Profibus DP是两种广泛应用的通讯协议。RS232&#xff0c;作为一种串…...

编程日记 2025/7/15 1:37:33

XAML基本语法与例子

XAML (eXtensible Application Markup Language) 是一种基于 XML 的声明性语言&#xff0c;主要用于 WPF、UWP、Xamarin.Forms 和 MAUI 等框架中构建用户界面。 基本语法结构 1. 根元素和命名空间声明 <Page x:Class"MyNamespace.MyPage"xmlns"http://sch…...

编程日记 2025/7/22 11:05:21

map和set封装

创作中心-CSDNhttps://mpbeta.csdn.net/mp_blog/creation/editor/147238663 目录 创作中心-CSDNhttps://mpbeta.csdn.net/mp_blog/creation/editor/147238663 一、封装原理 二、改造红黑树 三、实现迭代器 四、测试 五、小tip 一、封装原理 上一篇文章我们完成了红黑…...

编程日记 2025/7/21 19:17:11

Java第六节：创建线程的其它三种方式（附带源代码）

作者往期文章 Java第五节&#xff1a;继承thread类创建线程-CSDN博客 一、实现Runnable接口 创建一个Thread02类实现Runnable接口 二、使用匿名内部类 在Main函数中匿名内部类创建线程 三、使用Lambda表达式 在Main函数中利用Lambda表达式创建一个线程 四、源代码 此项目源代…...

编程日记 2025/7/22 11:15:35

041-代码味道-大泥团模块

代码味道-大泥团模块 代码味道-Blob Module深度解析与C重构实践 一、Blob Module定义与特征 Blob Module&#xff08;大泥团模块&#xff09;是代码坏味道中的一种典型表现&#xff0c;指某个类或模块承担了过多不相关的职责&#xff0c;导致代码结构臃肿、可维护性差。其核心…...

编程日记 2025/7/22 11:42:20

强化学习系统学习路径与实践方法

一、学习路径规划​​ ​​1. 基础巩固阶段&#xff08;1-2个月&#xff09;​​ ​​必读教材​​&#xff1a; 《Reinforcement Learning: An Introduction》(Sutton & Barto) ​​第1-6章​​重点掌握&#xff1a;马尔可夫决策过程&#xff08;MDP&#xff09;、贝尔曼…...

编程日记 2025/7/21 17:22:04

CSS字体

CSS字体 CSS 中的字体样式设置是网页设计的重要部分&#xff0c;以下是一些关键知识点和常见用法&#xff1a; 1.font-family &#xff1a; 用于设置元素的字体系列。可以指定一个或多个字体名称作为备选项&#xff0c;以确保如果某个字体不可用&#xff0c;可以使用下一个备选…...

编程日记 2025/7/22 11:09:02

JDBC:数据库访问的原始接口

目录 一、JDBC 基础入门&#xff1a;数据库访问的原始接口 JDBC 是什么&#xff1f;它在 Java 中扮演什么角色&#xff1f; JDBC 工作原理图解&#xff08;驱动 -> 连接 -> 执行 -> 关闭&#xff09; 常见 JDBC 驱动类型及差异 第一个 JDBC 示例程序&#xff1a;连…...

编程日记 2025/7/22 11:07:38

使用 Electron 打包可执行文件和资源：完整实战教程

一.项目结构 项目结构建议如下&#xff1a; my-electron-app/ ├── example.exe ← 需打包的外部程序 ├── config.json ← 配置文件 ├── native-lib/ ← 自定义库或 DLL │ └── yourlib.dll ├── main.js …...

编程日记 2025/7/17 11:44:17

【网络安全】CI/CD 流水线漏洞

【网络安全】CI/CD 流水线漏洞 1. 保护您的软件管道&#xff1a;CI/CD 安全2. 什么是 CI/CD 以及它为何重要&#xff1f;2.1 持续集成&#xff08;CI&#xff09;&#xff1a;构建坚实的基础2.2 持续交付&#xff08;CD&#xff09;&#xff1a;准备发布2.3 持续部署&#xff0…...

编程日记 2025/6/29 11:12:11

计算机是如何工作的（上）

对于学习JavaEE初阶为什么要知道计算机是如何工作的&#xff0c;是因为在未来我们写代码的时候&#xff0c;会出现一些bug&#xff0c;而在代码层面是看不出来的&#xff0c;所以我们需要了解一些关于计算机内部是如何工作的&#xff0c;从而提高代码的健壮度。 计算机的组成&…...

编程日记 2025/7/18 20:18:45

【SF顺丰】顺丰开放平台API对接（Java对接篇）

对接前置篇&#xff1a; 【SF顺丰】顺丰开放平台API对接&#xff08;注册、API测试篇&#xff09;_顺丰api接口对接指南-CSDN博客 1.实现效果展示 2.SF顺丰开放平台&#xff0c;JDK资源下载。 下载地址&#xff1a;顺丰开放平台 3.将下载的JDK放入项目中。 4.将JDK资源引入p…...

编程日记 2025/7/21 7:54:43

【KWDB创作者计划】_针对KWDB时序数据库（多副本集群环境）进行压力测试

【KWDB创作者计划】_针对KWDB时序数据库&#xff08;多副本集群环境&#xff09;进行压力测试 1. 概述2. 压测环境部署3. 生成测试数据4. 写入性能测试5. 查询性能测试7. 总结 1. 概述 KWDB是一款主要应用于工业物联网、数字能源、车联网、智慧产业等领域的时序数据库&#xff…...

编程日记 2025/7/16 16:33:00

24.中医知识问答删除历史对话功能前端代码实现

前端实现对话删除功能的完整指南 功能概述 前篇文章介绍了删除历史对话的后端开发&#xff0c;本篇将介绍如何在前端实现一个完整的对话删除功能&#xff0c;包括用户确认、API调用、状态管理和错误处理等关键环节。 功能拆解 1. 用户确认机制 javascript const confirmDe…...

编程日记 2025/6/29 11:34:07

在Cursor编辑器上部署MCP（Minecraft Coder Pack）完整指南

MCP&#xff08;Minecraft Coder Pack&#xff09;是用于反编译和修改Minecraft Java版代码的工具包。本教程将详细介绍如何在Cursor编辑器中配置和运行MCP&#xff0c;以便高效地进行Minecraft模组开发或代码研究。 1. 准备工作 1.1 所需工具 Cursor编辑器&#xff08;基于VS…...

编程日记 2025/7/7 22:59:53

STM32——相关软件安装

本文是根据江协科技提供的教学视频所写&#xff0c;旨在便于日后复习&#xff0c;同时供学习嵌入式的朋友们参考&#xff0c;文中涉及到的所有资料也均来源于江协科技&#xff08;资料下载&#xff09;。 Keil5 MDK安装 1.安装Keil5 MDK2.安装器件支持包方法一&#xff1a;离线…...

编程日记 2025/6/29 11:46:07

蓝牙WiFi模组rtl8821cs在Android14调

环境 SDK: AOSP14 主控&#xff1a;RK3576 蓝牙&#xff1a;RTL8821CS 先记一下官网文档关于蓝牙的资料 蓝牙 | Android Open Source Project 还在调&#xff0c;先看看啥情况&#xff0c;点赞多或者想起来记录再回来 TODO...

编程日记 2025/6/29 11:36:10

MCP实践第一步--磕磕碰碰搭环境

由于deepseek-r1不支持function calling&#xff0c;所以我们采用了deepseek-v3进行实践&#xff0c;模型名称为deepseek-chat&#xff0c;在deepseek官网获取api-key。 一、参照MCP官网设置环境 创建项目目录 uv init mcp-client # 若没有uv&#xff0c;则先通过pip instal…...

编程日记 2025/7/18 16:21:27

Java并发：线程池

目录 一、核心概念与设计原理 1、线程池的核心价值 2、核心接口和类 3、线程池的核心构造参数 4、线程池工作流程 二、参数选择 1、任务队列选择 2、拒绝策略选择 3、常见线程池选择 4、参数调优 三、 应用 1、创建建议 2、生命周期管理&#xff1a;优雅关闭 3、…...

编程日记 2025/7/4 8:35:49

Kubernetes集群超配节点容量

目录&#xff1a; 1、节点超配简介2、创建 PriorityClass3、运行请求节点容量的 Pod4、调整占位资源请求5、设置所需的副本数量6、自动扩缩容组件6.1、手动方式6.2、自动方式 1、节点超配简介 节点超配是一种主动预留部分集群计算资源的策略。这种预留有助于减少在扩缩容事件期…...

编程日记 2025/6/29 10:26:07

每日一题（小白）回溯篇7

首先我们可以判断出这是一个dfs的题目&#xff0c;因为简言之就是要求最短路径。其次这个题目与直接找最短路径有所不同&#xff0c;增加了条件必须依次穿过指定的符号。无论坦克走到任何一点都有四个方向可以走&#xff08;越界要判断&#xff09;&#xff0c;结束的条件是到达…...

编程日记 2025/6/29 12:03:46

rk3588上完成halcon的形状模型配准以及和opencv的图像转换

一、准备工作 1&#xff09;安装好halcon&#xff0c;确保halcon的c的调用是正常的 2&#xff09;编译好opencv 上面的两个步骤&#xff0c;均可以参考我的两个博文完成&#xff1a; Halcon在linux及ARM上的安装及c工程化_halcon linux-CSDN博客 RK3588上编译opencv 及基于…...

编程日记 2025/6/29 10:04:57

Spring Boot 断点续传实战：大文件上传不再怕网络中断

精心整理了最新的面试资料和简历模板&#xff0c;有需要的可以自行获取 点击前往百度网盘获取 点击前往夸克网盘获取 一、痛点与挑战 在网络传输大文件&#xff08;如视频、数据集、设计稿&#xff09;时&#xff0c;常面临&#xff1a; 上传中途网络中断需重新开始服务器内…...

编程日记 2025/7/22 10:53:59

Springboot集成websocket实现消息推送

假设有个需求需要多个用户同时在对应的消息面板实时查看相关接口的执行流程进度&#xff0c;此时可以可考虑使用websocket来实现结果进度推送 一、引入websocket依赖&#xff0c;并编写WebSocket配置类 <dependency><groupId>org.springframework.boot</group…...

编程日记 2025/7/10 12:15:27

PostgreSQL 用户资源管理

PostgreSQL 用户资源管理 PostgreSQL 提供了多种机制来管理和限制用户对数据库资源的使用&#xff0c;以下是全面的资源管理方法&#xff1a; 1 连接限制 1.1 限制最大连接数 -- 在 postgresql.conf 中设置 max_connections 100 -- 全局最大连接数-- 为特定用户设置连接限…...

编程日记 2025/7/9 15:34:06

Uniapp：pages.json页面路由

目录 一、pages二、style 一、pages uni-app 通过 pages 节点配置应用由哪些页面组成&#xff0c;pages 节点接收一个数组&#xff0c;数组每个项都是一个对象&#xff0c;其属性值如下&#xff1a; 属性类型默认值描述pathString配置页面路径styleObject配置页面窗口表现nee…...

编程日记 2025/7/3 14:38:32

使用open3d将pcd点云按照颜色等级分块显示并令其随颜色变化播放

👑主页：吾名招财 👓简介：工科学硕，研究方向机器视觉，爱好较广泛… ​💫签名：面朝大海，春暖花开！ 使用open3d将pcd点云按照颜色等级分块显示并令其随颜色变化播放 引言显示效果点云获取完整代码引言 有很多时候我们需要更改pcd点云某些区域的颜色，可能是颜色随着点…...

编程日记 2025/7/19 13:13:14

玩转Docker | 使用Docker部署nullboard任务管理工具

玩转Docker | 使用Docker部署nullboard任务管理工具 前言一、nullboard介绍简介主要特点二、系统要求环境要求环境检查Docker版本检查检查操作系统版本三、部署nullboard服务下载镜像创建容器创建容器检查容器状态检查服务端口安全设置四、访问nullboard服务访问nullboard首页五…...

编程日记 2025/7/4 19:24:45

如何避免流程形式化导致的效率低下？

要避免流程形式化导致的效率低下&#xff0c;核心在于&#xff1a;聚焦流程价值、保障执行灵活性、优化流程设计、建立反馈机制、提升执行感知。其中&#xff0c;聚焦流程价值 是解决流程“空转”的首要原则。流程不应只是文档或制度的堆叠&#xff0c;而要服务于业务目标&…...

编程日记 2025/6/29 12:08:14

Java学习手册：HTTP 协议基础知识

一、HTTP 协议概述 HTTP&#xff08;HyperText Transfer Protocol&#xff09;即超文本传输协议&#xff0c;是用于从万维网&#xff08;WWW&#xff1a;World Wide Web &#xff09;服务器传输超文本到本地浏览器的传输协议。它是一个应用层协议&#xff0c;基于请求-响应模型…...

编程日记 2025/6/29 10:44:10

基于多模态融合算法的航空武器毁伤评估技术方案

基于多模态融合算法的航空武器毁伤评估技术方案 1. 引言 航空武器毁伤评估（Damage Assessment, DA）是现代战争中的关键环节，直接影响后续作战决策。传统的人工评估方式效率低、主观性强，且在高强度战场环境下难以实时完成。因此，本研究提出一种基于多模态融合算法的自动…...

编程日记 2025/7/19 9:58:01

欧拉-国产操作系统替代产品如何

欧拉（openEuler）国产操作系统是由华为发起并联合开源社区共同开发的企业级操作系统，旨在构建自主可控的数字基础设施生态底座。以下从开发背景、技术特点、应用场景、生态建设及市场表现等方面进行全面介绍： 一、开发背景与战略定位 国家需求驱动 在中美技术竞争背景下，国…...

编程日记 2025/6/29 11:08:18

入门-C编程基础部分：16、 预处理器

飞书文档https://x509p6c8to.feishu.cn/wiki/DzSJwsGiTiXkeCkyEYUcuXbKnbf C 预处理是编译过程中一个单独的步骤&#xff0c;是一个文本替换工具而已。所有的预处理命令都是以井号&#xff08;#&#xff09;开头。 指令描述#define定义宏#ifdef如果宏已经定义&#xff0c;则返…...

编程日记 2025/7/22 11:39:49

Spark-SQL4

一 .Spark-SQL核心编程&#xff08;六&#xff09; Spark-SQL连接Hive Apache Hive 是 Hadoop 上的 SQL 引擎&#xff0c;Spark SQL 编译时可以包含 Hive 支持&#xff0c;也可以不包含。包含 Hive 支持的 Spark SQL 可以支持 Hive 表访问、UDF (用户自定义函数)、Hive 查询语…...

编程日记 2025/7/18 20:40:13

模数转换【1】AD7699

1.开发背景 一款可以模数转换芯片&#xff0c;兼容通用 SPI 接口&#xff0c;支持最多支持 8 个通道和 500KSPS 的采样率。支持单个通道采集和扫描采集模式。 同系列的芯片还有 AD7682 和 AD7689 等。 2.开发需求 配置内部参考电压4.096V&#xff0c;实现单个通道采集和扫描采集…...

编程日记 2025/7/19 10:28:49

P5670 秘籍-反复异或 Solution

Description 给定序列 a ( a 1 , a 2 , ⋯ , a n ) a(a_1,a_2,\cdots,a_n) a(a1​,a2​,⋯,an​) 和常数 m m m&#xff0c;有 q q q 个操作分两种&#xff1a; add ⁡ ( l , r , x ) \operatorname{add}(l,r,x) add(l,r,x)&#xff1a;对每个 i ∈ [ l , r ] i\in[l,r] …...

编程日记 2025/6/29 12:10:33

PID控制程序编写

目录 一、C语言PID控制器示例代码 二、代码解释 三、重要注意事项 一、C语言PID控制器示例代码 #include <stdio.h> #include <stdlib.h> #include <unistd.h> // For sleep function typedef struct { double Kp; // 比例增益 double…...

编程日记 2025/7/13 13:29:18

推荐系统/业务，相关知识/概念2

一、漫画库更新大量新作品&#xff0c;如何融入推荐系统&#xff1f; 参考答案&#xff1a; 快速提取新作品特征&#xff1a;除基础属性外&#xff0c;利用自然语言处理技术提取漫画简介关键词等丰富特征向量&#xff0c;分析情节、角色设定等深层次特征结合物品画像体系分类…...

编程日记 2025/6/29 12:12:44

基于Python的施工图与竣工图对比小工具开发方案

基于Python的施工图与竣工图对比小工具开发方案 一、引言 在工程建设领域&#xff0c;施工图与竣工图的对比是项目验收的关键环节。传统人工对比方式效率低、易出错&#xff0c;本文基于Python开发一款自动化对比工具&#xff0c;支持快速检测图纸差异并生成可视化报告&#x…...

编程日记 2025/7/9 15:22:12

2025年世界职业院校技能大赛实施方案（意见稿）

为贯彻落实《教育强国建设规划纲要&#xff08;2024—2035年&#xff09;》&#xff0c;进一步提升世界职业院校技能大赛&#xff08;以下简称“大赛”&#xff09;内涵质量&#xff0c;发挥大赛引领作用&#xff0c;提升高技能人才培养质量&#xff0c;服务现代职业教育体系建…...

编程日记 2025/6/29 12:00:56