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

1384:珍珠(bead)

1384:珍珠(bead)
时间限制: 1000 ms         内存限制: 65536 KB
【题目描述】
有n颗形状和大小都一致的珍珠,它们的重量都不相同。n为整数,所有的珍珠从1到n编号。你的任务是发现哪颗珍珠的重量刚好处于正中间,即在所有珍珠的重量中,该珍珠的重量列(n+1)/2位。下面给出将一对珍珠进行比较的办法:
给你一架天平用来比较珍珠的重量,我们可以比出两个珍珠哪个更重一些,在作出一系列的比较后,我们可以将某些肯定不具备中间重量的珍珠拿走。
例如,下列给出对5颗珍珠进行四次比较的情况:
1、珍珠2比珍珠1重
2、珍珠4比珍珠3重
3、珍珠5比珍珠1重
4、珍珠4比珍珠2重
根据以上结果,虽然我们不能精确地找出哪个珍珠具有中间重量,但我们可以肯定珍珠1和珍珠4不可能具有中间重量,因为珍珠2、4、5比珍珠1重,而珍珠1、2、3比珍珠4轻,所以我们可以移走这两颗珍珠。
写一个程序统计出共有多少颗珍珠肯定不会是中间重量。
【输入】
第一行包含两个用空格隔开的整数N和M,其中1≤N≤99,且N为奇数,M表示对珍珠进行的比较次数,接下来的M行每行包含两个用空格隔开的整数x和y,表示珍珠x比珍珠y重。
【输出】
一行包含一个整数,表示不可能是中间重量的珍珠的总数。
【输入样例】
5 4
2 1
4 3
5 1
4 2
【输出样例】
2

//示例代码 Floyed 暴力求解
#include <bits/stdc++.h>
using namespace std;
int a[105][105];
int n,m,x,y,ans,t;
int main() {cin>>n>>m;for(int i=1;i<=m;i++){cin>>x>>y;a[x][y]=1;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(a[i][k]==1&&a[k][j]==1) a[i][j]=1;for(int i=1;i<=n;i++){t=0;//统计 i>j 的个数for(int j=1;j<=n;j++) if(a[i][j]==1) t++;if(t>=(n+1)/2) ans++; //i>j 的个数t=0;//统计 j>i 的个数for(int j=1;j<=n;j++) if(a[j][i]==1) t++;if(t>=(n+1)/2) ans++;}cout<<ans;return 0;
}
//示例代码 深搜求解
#include <bits/stdc++.h>
using namespace std;
bool a1[205][205],a2[205][205],b[205];
int n,m,x,y,ans,t;
void dfs(int p,bool a[205][205]){int i; b[p]=1;for(i=1;i<=n;i++){if(a[p][i] && !b[i]) dfs(i,a);}t++;
}
int main() {cin>>n>>m;for(int i=1;i<=m;i++){cin>>x>>y;a1[x][y]=1;//a1  x>ya2[y][x]=1;//a2  y>x}//统计多少个珍珠的重量比(n+1)/2以上个数的珍珠重for(int i=1;i<=n;i++){t=0;memset(b,0,sizeof(b));dfs(i,a1);if(t>(n+1)/2)ans++;}//统计多少个珍珠的重量比(n+1)/2以上个数的珍珠轻for(int i=1;i<=n;i++){t=0;memset(b,0,sizeof(b));dfs(i,a2);if(t>(n+1)/2)ans++;}cout<<ans;return 0;
}

相关文章:

1384:珍珠(bead)

1384&#xff1a;珍珠(bead) 时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 有n颗形状和大小都一致的珍珠&#xff0c;它们的重量都不相同。n为整数&#xff0c;所有的珍珠从1到n编号。你的任务是发现哪颗珍珠的重量刚好处于正中间&#xff0c;即在所有珍珠的重量…...

34岁本科男,做了5年功能测试想转行,除了进厂还能干什么?

我的建议是不要给自己设限。任何一个行业只要做到顶尖都是很有作为的&#xff0c;何况是IT行业&#xff0c;本身就比别的行业有优势&#xff0c;如果你现在是功能测试&#xff0c;应该想的是进阶自动化测试或者测试开发 如何在半年时间由功能测试成长为年薪30W的测试开发&#…...

一文理解Transformer整套流程

【备注】部分图片引至他人博客&#xff0c;详情关注参考链接 【PS】query 、 key & value 的概念其实来源于推荐系统。基本原理是&#xff1a;给定一个 query&#xff0c;计算query 与 key 的相关性&#xff0c;然后根据query 与 key 的相关性去找到最合适的 value。举个例…...

04、SpringBoot运维实用篇

一、配置文件1、临时属性设置目前我们的程序包打好了&#xff0c;可以发布了。但是程序包打好以后&#xff0c;里面的配置都已经是固定的了&#xff0c;比如配置了服务器的端口是8080。如果我要启动项目&#xff0c;发现当前我的服务器上已经有应用启动起来并且占用了8080端口&…...

3.Java运算符

Java运算符 运算符基本分为六类&#xff1a;算数运算符、赋值运算符、关系运算符、逻辑运算符、位运算符、三元&#xff08;条件&#xff09;运算符。 一、算术运算符 算数运算符&#xff0c;是指在Java运算中&#xff0c;计算数值类型的计算符号&#xff0c;既然是操作数值…...

《RockectMQ实战与原理解析》Chapter4-分布式消息队列的协调者

4.1 NameServer 的功能 NameServer 是整个消息队列中的状态服务器&#xff0c;集群的各个组件通过它来了解全局的信息 。 同时&#xff0c;各个角色的机器都要定期向 NameServer 上报自己的状态&#xff0c;超时不上报的话&#xff0c; NameServer 会认为某个机器出故障不可用了…...

Spring Boot 最适配的 UI 是什么

与Spring Boot一起使用的最佳 UI 是什么&#xff1f; 我经常碰到的一个常见问题是“与 Spring Boot 一起使用的最佳 UI 是什么&#xff1f;” UI&#xff0c;也称为“用户界面”&#xff0c;有许多不同的风格。 UI 应用程序可能是用 Java Swing、FX 或其他一些技术编写的桌面应…...

TensorFlow 1.x 深度学习秘籍:6~10

原文&#xff1a;TensorFlow 1.x Deep Learning Cookbook 协议&#xff1a;CC BY-NC-SA 4.0 译者&#xff1a;飞龙 本文来自【ApacheCN 深度学习 译文集】&#xff0c;采用译后编辑&#xff08;MTPE&#xff09;流程来尽可能提升效率。 不要担心自己的形象&#xff0c;只关心如…...

分布式场景下,Apache YARN、Google Kubernetes 如何解决资源管理问题?

所有的资源管理系统都需要解决资源的有效利用、任务的有效响应、调度策略的灵活配置这三个最基本问题。那么在分布式的场景下&#xff0c;YARN和Kubernetes是怎么解决的呢&#xff1f;本篇进行介绍。 — Apache YARN — YARN全称为&#xff08;Yet Another Resource Negotiato…...

RK3399平台开发系列讲解(基础篇)POSIX 定时器

🚀返回专栏总目录 文章目录 一、clockid二、sigevent三、timerid四、flags五、 value & old_value六、POSIX 定时器的优势沉淀、分享、成长,让自己和他人都能有所收获!😄 📢为了克服传统定时器的局限性,POSIX 标准组织设计了新的计时器接口和规范,使它们能提供更…...

web小游戏开发:扫雷(三)(完成度90%)

web小游戏开发:扫雷(三) 实现布雷鼠标事件处理左键和右键单独实现实现递归展开追加地雷计数和时间计时小结书接前文啊,如果没看过前两篇的话,不好理解这里的定义了哦。 实现布雷 在之前两篇文章,我们已经把雷区布置好了,全部盖上了格子,现在我们需要把雷布出来,这就需…...

创建菜单栏、菜单、菜单项

1、QMainWindow窗口 1.1、创建菜单栏 this 代表的是 当前窗口&#xff08;主窗口&#xff09;&#xff0c;也就是 当前窗口中添加/设置 菜单栏 this->resize(800,600); //创建 菜单栏 QMenuBar *menuBar new QMenuBar(this); //将菜单栏 添加到主窗口的特殊位置 this-&g…...

专访丨AWS量子网络中心科学家Antía Lamas谈量子计算

​ Anta Lamas Linares&#xff08;图片来源&#xff1a;网络&#xff09; 47岁的Anta Lamas Linares出生于西班牙西北部的圣地亚哥德孔波斯特拉。她在当地学习物理学&#xff0c;然后在牛津大学和加利福尼亚继续深造。后来&#xff0c;她在新加坡领导了亚马逊网络服务&#xf…...

[ 云计算 | Azure ] Chapter 04 | 核心体系结构之数据中心、区域与区域对、可用区和地理区域

本章节主要内容进行讲解&#xff1a;Azure云计算的核心体系结构组件中的&#xff1a;Azure物理基础设施&#xff08;Physical infrastructure&#xff09;&#xff0c;区域&#xff08;Regions&#xff09;和区域对&#xff08;Region Pairs&#xff09;、地理数据中心&#xf…...

升级长江存储最新闪存,忆恒创源发布新一代企业级NVMe SSD

2023年4月11日 —— 北京忆恒创源科技股份有限公司&#xff08;Memblaze&#xff09;正式发布搭载高品质国产闪存的PBlaze6 6541 系列企业级PCIe 4.0 NVMe SSD。作为 MUFP 平台化开发的最新作品&#xff0c;PBlaze6 6541 采用长江存储最新一代晶栈 Xtacking 3D NAND&#xff0c…...

Xcode14:”Failed to prepare the device for development“解决

当前Xcode版本14.2&#xff0c;测试机iOS版本16.4, 结果出现提示&#xff1a;Failed to prepare the device for development&#xff0c;经过Clean,重装都无效&#xff0c;最后发现其他人也有类似的问题 https://developer.apple.com/forums/thread/714388 PS&#xff1a;首先…...

程序员的“灵魂笔记本“:五款高效笔记软件推荐

大家好&#xff0c;我是 jonssonyan。作为一名程序员&#xff0c;我们经常需要记录和整理大量的代码、知识和项目信息&#xff0c;以便在日后能够高效地进行查阅和复用。而好用的笔记软件则成为了我们的"灵魂笔记本"&#xff0c;帮助我们提高工作效率。在这篇文章中&…...

Linux基础命令-scp远程复制文件

Linux基础命令-seq打印数字序列 前言 有时候不可避免的需要将文件复制到另外一台服务器上&#xff0c;那么这时就可以使用scp命令远程拷贝文件&#xff0c;scp命令是基于SSH协议&#xff0c;在复制的过程中数据都是加密过的&#xff0c;会比明文传输更为安全。 一.命令介绍 …...

【python学习】基础篇-列表元素排序操作 sort()、min()、max()函数

列表对象中提供了 sort0 方法&#xff0c;该方法用于对原列表中的元素进行排序&#xff0c;排序后原列表中的元素顺序将发生改变。 其语法格式如下: listname.sort(keyNone&#xff0c; reverseFalse) key&#xff1a;用于比较的键 reverse&#xff1a;可选参数&#xff0c;Fal…...

机器视觉检测系统的基本流程你知道吗

工业制造业种&#xff0c;首先我们便需要了解其基本流程&#xff0c;作为工厂信息科人员&#xff0c;我们不能只依靠视觉服务商的巡检驻检来解决问题&#xff0c;为了产线的效率提升&#xff0c;我们更多的应该培养产线技术人员&#xff0c;出现问题便可以最快速度解决问题&…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...