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

分考场

[蓝桥杯 2017 国 C] 分考场(假题:最小色数)

题目描述

nnn 个人参加某项特殊考试。

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

求最少需要分几个考场才能满足条件。

输入格式

第一行,一个整数 n(1<n<100)n(1<n<100)n(1<n<100),表示参加考试的人数。

第二行,一个整数 mmm,表示接下来有 mmm 行数据。

以下 mmm 行每行的格式为:两个整数 aaabbb,用空格分开 (1≤a,b≤n)(1 \le a,b \le n)(1a,bn) 表示第 aaa 个人与第 bbb 个人认识(编号从 111 开始)。

输出格式

一行一个整数,表示最少分几个考场。

样例 #1

样例输入 #1

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

样例输出 #1

4

样例 #2

样例输入 #2

5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

样例输出 #2

5

提示

时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200;
int st[N][N];
int mp[N][N];//第i个考场的第i位同学
int n,m;
int minkey;
void dfs(int k,int res)//第k个同学,存在res个考场
{if(res>=minkey)return;//目前的考场数大于了最优考场数,不再继续if(k>n)//目前遍历的是n+1位同学,没有,已经遍历完了{minkey=min(minkey,res);//更新考场数return ;}for(int i=1;i<=res;i++)//依次遍历每个考场,看有没有认识他的{int u=1;while(mp[i][u]&&!st[k][mp[i][u]])//如果第i个考场的第u名同学存在且不认识,继续往后遍历u++;//注意这个u如果每个人都不认识的话,这个u代表的是本考场人数加一//那么这个考场就没有第u个人,if(!mp[i][u])//没有第u个,让第k个同学成为第u个{mp[i][u]=k;dfs(k+1,res);mp[i][u]=0;//回溯}}//自己新加一个考场mp[res+1][1]=k;dfs(k+1,res+1);mp[res+1][1]=0;
}
int main()
{cin>>n>>m;minkey=n;while(m--){int a,b;cin>>a>>b;st[a][b]=1;//表示ab认识st[b][a]=1;}dfs(1,0);//第1个同学有0个考场cout<<minkey;return 0;
}

相关文章:

分考场

[蓝桥杯 2017 国 C] 分考场(假题&#xff1a;最小色数) 题目描述 nnn 个人参加某项特殊考试。 为了公平&#xff0c;要求任何两个认识的人不能分在同一个考场。 求最少需要分几个考场才能满足条件。 输入格式 第一行&#xff0c;一个整数 n(1<n<100)n(1<n<100…...

BI技巧丨DAX Studio

DAX Studio DAX Studio&#xff0c;作为PowerBI外部插件使用率排名第一的插件&#xff0c;相信各位小伙伴或多或少都听说过&#xff0c;那么DAX Studio具体有哪些功能呢&#xff1f; PS&#xff1a;DAX Studio的下载链接&#xff0c;小伙伴们可以自行搜索&#xff0c;这里就不…...

Java 8常用时间 API

Date: 你不爱我了吗? &#x1f6a1;本地时间时区相关格式化在Java 8中&#xff0c;Instant类用于表示时间戳&#xff0c;相当于旧的Date类&#xff1b;LocalDateTime类用于表示日期和时间&#xff0c;相当于旧的Calendar类&#xff1b;DateTimeFormatter类用于格式化日期和时间…...

C++运算符

C运算符 运算符是一种告诉编译器执行特定的数学或逻辑操作的符号。C 内置了丰富的运算符&#xff0c;并提供了以下类型的运算符&#xff1a; 算术运算符关系运算符逻辑运算符位运算符赋值运算符杂项运算符 1. 算术运算符 运算符描述实例把两个操作数相加A B 将得到 30-从第…...

低/无代码赋能企业,IT与业务的角色正在悄然改变

现在这个社会&#xff0c;年轻人的压力是真的大&#xff0c;需要会的技能多到数不清。想学习多点技能也不知道去哪学&#xff0c;主要是网络资源太丰富&#xff0c;很难找到一个适合自己的。那接下来推荐4个大神级别的资源网站你可一定得码住&#xff0c;都是年轻人特别 …...

SpringCloud学习2(Spring Cloud Netflix)负载均衡Ribbon、Feign负载均衡、Hystix服务熔断

文章目录负载均衡RibbonRibbon的作用代码实现生产者cloud1_provider实现配置文件在HiController中编写以下代码启动集群消费者cloud1_consumer实现引入依赖编写配置文件编写启动类&#xff0c;并给RestTemplate配置LoadBalanced注解编写RestController来测试Feign负载均衡简介F…...

Spring 源码解析 - @Async 注解下的循环依赖问题原理

一、Async 注解下的循环依赖问题 我们都知道 Spring IOC 单例模式下可以帮助我们解决循环依赖问题&#xff0c;比如下面自己依赖自己循环依赖的场景&#xff1a; Component public class TestAsync {ResourceTestAsync async;public void test() {System.out.println("t…...

8个全球性编程比赛,天才程序员的梦想舞台

很多编程爱好者在学习之初&#xff0c;都渴望与全球的程序员一较高下&#xff0c;以证明自己的实力。 一些全球性的编程竞赛为他们提供了这样的机会&#xff0c;不仅可以与全世界的顶尖程序员们交流&#xff0c;还有机会获得丰厚的奖金和进入顶级公司的机会&#xff0c;更重要…...

2023年中国海洋大学计算机及电子信息考研分析

考研时间跨度&#xff1a; 初试时间&#xff1a; 2022年8月23 海大推免及创新人才计划接收通知。 2022年9月13 海大专业目录及人数&#xff0c;包含推免。 2022年10月18 2022年硕士研究生计划 &#xff0c;不含推免。 海大2022年硕士研究生计划 网上第一次时间为2022年9月24日…...

【C++笔试强训】第六天

选择题 1. 解析&#xff1a;十进制转换为八进制就是不断的除8&#xff0c;取余数。十进制转换成其他进制的数就是除以进制&#xff0c;取余。 解析&#xff1a;注意printf的转换&#xff0c;%%只会打印一个%&#xff0c;所以选A。 解析&#xff1a;由于()的原因p先和*结合&…...

Redission 中的 RedLock 原理实现, springboot 你造吗?

分布锁之RedLock 锁住你的心我的爱 &#x1f682;为什么需要使用 RedLock锁被误释放时钟不一致问题锁的“延迟释放”而不是死锁Redlock是啥redlock 存在什么问题惊群效应时钟漂移Redisson 实现 RedLock在 Redisson 中, RedLock的实现类是哪一个类?这一招叫抛砖引玉springboot …...

【沐风老师】3dMax一键房屋创建者插件使用方法详解

3dmax一键房屋创建者&#xff0c;一键生成墙体、窗洞和门洞的插件&#xff01;这个脚本主要用于创建或捕获一些架构项目所代表的平面&#xff0c;这是通过导入它们并在每个所需的层添加值来实现的。传统方法&#xff0c;但是省事儿多了&#xff01; 【版本要求】 3dMax 2015及…...

C/C++ 变量详解

文章目录前言一、静态变量与动态变量1. 概念2. 区别3. 使用方法和注意事项3.1 静态变量3.2 动态变量4. 结论二、全局变量与局部变量1. 区别2. 全局变量的使用方法和注意事项3. 局部变量的使用方法和注意事项4. 总结前言 对C学习感兴趣的可以看看这篇文章哦&#xff1a;C/C教程…...

新SSD盘安装操作系统启动不了

今天打算给电脑升级下装备&#xff0c;加装一块固态硬盘。 电脑原本自带两块硬盘&#xff08;SSD128GSATA1T&#xff09;&#xff0c;SSD清理了许久还是没空间&#xff0c;于是就买了块1TSSD&#xff0c;打算扩容下。 打开电脑后盖傻眼了&#xff0c;没有备用插槽&#xff0c…...

基于Spring、SpringMVC、MyBatis的病历管理系统

文章目录 项目介绍主要功能截图:登录首页医院公告管理用户管理科室信息管理医生管理出诊信息管理预约时间段管理预约挂号管理门诊病历管理就诊评价管理轮播图管理功能架构图部分代码展示设计总结项目获取方式🍅 作者主页:Java韩立 🍅 简介:Java领域优质创作者🏆、 简历…...

QT编程从入门到精通之三十四:“第五章:Qt GUI应用程序设计”之“5.5 Qt Creator使用技巧”

目录 第五章:Qt GUI应用程序设计 5.5 Qt Creator使用技巧 第五章:Qt GUI应用程序设计 在“Qt 程序创建基础”上,本章将继续深入地介绍Qt Creator设计GUI应用程序的方法,包括Qt创建的应用程序项目的基本组织结构,可视化设计的UI界面文件的原理和运行机制,信号与槽的使用…...

网络工程方向有哪些SCI期刊推荐? - 易智编译EaseEditing

以下是网络工程领域的一些SCI期刊推荐&#xff1a; IEEE Transactions on Network and Service Management: 这是一个IEEE旗下的期刊&#xff0c;涵盖了网络与服务管理方面的研究。主要关注网络管理、服务管理和其它相关领域的创新和最新研究。 Computer Networks: 这是一本著…...

netty入门(二十六)任务加入异步线程池源码剖析

1.handler中加入线程池和Context添加线程池 1.1 源码剖析目的 &#xff08;1&#xff09;在 Netty 中做耗时的&#xff0c;不可预料的操作&#xff0c;比如&#xff1a;数据库、网络请求、会严重影响 Netty 对 Socket 的处理速度。 &#xff08;2&#xff09;而解决方法就是…...

神经网络算法入门和代码

文章内容 感知机&#xff08;Perceptron&#xff09;反向传播算法&#xff08;Back Propagation algorithm&#xff09;RBF(Radial Basis Function&#xff0c;径向基函数) 网络&#xff1a;单一层前馈网络&#xff0c;它使用径向基作为隐层神经元激活函数ART(Adaptive Resona…...

如何用一个端口同时暴露 HTTP1/2、gRPC、Dubbo 协议?

作者&#xff1a;华钟明 本文我们将介绍 Apache Dubbo 灵活的多协议设计原则&#xff0c;基于这一设计&#xff0c;在 Dubbo 框架底层可灵活的选用 HTTP/2、HTTP/REST、TCP、gRPC、JsonRPC、Hessian2 等任一 RPC 通信协议&#xff0c;同时享用统一的 API 与对等的服务治理能力。…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...