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:珍珠(bead) 时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 有n颗形状和大小都一致的珍珠,它们的重量都不相同。n为整数,所有的珍珠从1到n编号。你的任务是发现哪颗珍珠的重量刚好处于正中间,即在所有珍珠的重量…...
34岁本科男,做了5年功能测试想转行,除了进厂还能干什么?
我的建议是不要给自己设限。任何一个行业只要做到顶尖都是很有作为的,何况是IT行业,本身就比别的行业有优势,如果你现在是功能测试,应该想的是进阶自动化测试或者测试开发 如何在半年时间由功能测试成长为年薪30W的测试开发&#…...
一文理解Transformer整套流程
【备注】部分图片引至他人博客,详情关注参考链接 【PS】query 、 key & value 的概念其实来源于推荐系统。基本原理是:给定一个 query,计算query 与 key 的相关性,然后根据query 与 key 的相关性去找到最合适的 value。举个例…...
04、SpringBoot运维实用篇
一、配置文件1、临时属性设置目前我们的程序包打好了,可以发布了。但是程序包打好以后,里面的配置都已经是固定的了,比如配置了服务器的端口是8080。如果我要启动项目,发现当前我的服务器上已经有应用启动起来并且占用了8080端口&…...
3.Java运算符
Java运算符 运算符基本分为六类:算数运算符、赋值运算符、关系运算符、逻辑运算符、位运算符、三元(条件)运算符。 一、算术运算符 算数运算符,是指在Java运算中,计算数值类型的计算符号,既然是操作数值…...
《RockectMQ实战与原理解析》Chapter4-分布式消息队列的协调者
4.1 NameServer 的功能 NameServer 是整个消息队列中的状态服务器,集群的各个组件通过它来了解全局的信息 。 同时,各个角色的机器都要定期向 NameServer 上报自己的状态,超时不上报的话, NameServer 会认为某个机器出故障不可用了…...
Spring Boot 最适配的 UI 是什么
与Spring Boot一起使用的最佳 UI 是什么? 我经常碰到的一个常见问题是“与 Spring Boot 一起使用的最佳 UI 是什么?” UI,也称为“用户界面”,有许多不同的风格。 UI 应用程序可能是用 Java Swing、FX 或其他一些技术编写的桌面应…...
TensorFlow 1.x 深度学习秘籍:6~10
原文:TensorFlow 1.x Deep Learning Cookbook 协议:CC BY-NC-SA 4.0 译者:飞龙 本文来自【ApacheCN 深度学习 译文集】,采用译后编辑(MTPE)流程来尽可能提升效率。 不要担心自己的形象,只关心如…...
分布式场景下,Apache YARN、Google Kubernetes 如何解决资源管理问题?
所有的资源管理系统都需要解决资源的有效利用、任务的有效响应、调度策略的灵活配置这三个最基本问题。那么在分布式的场景下,YARN和Kubernetes是怎么解决的呢?本篇进行介绍。 — Apache YARN — YARN全称为(Yet Another Resource Negotiato…...
RK3399平台开发系列讲解(基础篇)POSIX 定时器
🚀返回专栏总目录 文章目录 一、clockid二、sigevent三、timerid四、flags五、 value & old_value六、POSIX 定时器的优势沉淀、分享、成长,让自己和他人都能有所收获!😄 📢为了克服传统定时器的局限性,POSIX 标准组织设计了新的计时器接口和规范,使它们能提供更…...
web小游戏开发:扫雷(三)(完成度90%)
web小游戏开发:扫雷(三) 实现布雷鼠标事件处理左键和右键单独实现实现递归展开追加地雷计数和时间计时小结书接前文啊,如果没看过前两篇的话,不好理解这里的定义了哦。 实现布雷 在之前两篇文章,我们已经把雷区布置好了,全部盖上了格子,现在我们需要把雷布出来,这就需…...
创建菜单栏、菜单、菜单项
1、QMainWindow窗口 1.1、创建菜单栏 this 代表的是 当前窗口(主窗口),也就是 当前窗口中添加/设置 菜单栏 this->resize(800,600); //创建 菜单栏 QMenuBar *menuBar new QMenuBar(this); //将菜单栏 添加到主窗口的特殊位置 this-&g…...
专访丨AWS量子网络中心科学家Antía Lamas谈量子计算
 Anta Lamas Linares(图片来源:网络) 47岁的Anta Lamas Linares出生于西班牙西北部的圣地亚哥德孔波斯特拉。她在当地学习物理学,然后在牛津大学和加利福尼亚继续深造。后来,她在新加坡领导了亚马逊网络服务…...
[ 云计算 | Azure ] Chapter 04 | 核心体系结构之数据中心、区域与区域对、可用区和地理区域
本章节主要内容进行讲解:Azure云计算的核心体系结构组件中的:Azure物理基础设施(Physical infrastructure),区域(Regions)和区域对(Region Pairs)、地理数据中心…...
升级长江存储最新闪存,忆恒创源发布新一代企业级NVMe SSD
2023年4月11日 —— 北京忆恒创源科技股份有限公司(Memblaze)正式发布搭载高品质国产闪存的PBlaze6 6541 系列企业级PCIe 4.0 NVMe SSD。作为 MUFP 平台化开发的最新作品,PBlaze6 6541 采用长江存储最新一代晶栈 Xtacking 3D NAND,…...
Xcode14:”Failed to prepare the device for development“解决
当前Xcode版本14.2,测试机iOS版本16.4, 结果出现提示:Failed to prepare the device for development,经过Clean,重装都无效,最后发现其他人也有类似的问题 https://developer.apple.com/forums/thread/714388 PS:首先…...
程序员的“灵魂笔记本“:五款高效笔记软件推荐
大家好,我是 jonssonyan。作为一名程序员,我们经常需要记录和整理大量的代码、知识和项目信息,以便在日后能够高效地进行查阅和复用。而好用的笔记软件则成为了我们的"灵魂笔记本",帮助我们提高工作效率。在这篇文章中&…...
Linux基础命令-scp远程复制文件
Linux基础命令-seq打印数字序列 前言 有时候不可避免的需要将文件复制到另外一台服务器上,那么这时就可以使用scp命令远程拷贝文件,scp命令是基于SSH协议,在复制的过程中数据都是加密过的,会比明文传输更为安全。 一.命令介绍 …...
【python学习】基础篇-列表元素排序操作 sort()、min()、max()函数
列表对象中提供了 sort0 方法,该方法用于对原列表中的元素进行排序,排序后原列表中的元素顺序将发生改变。 其语法格式如下: listname.sort(keyNone, reverseFalse) key:用于比较的键 reverse:可选参数,Fal…...
机器视觉检测系统的基本流程你知道吗
工业制造业种,首先我们便需要了解其基本流程,作为工厂信息科人员,我们不能只依靠视觉服务商的巡检驻检来解决问题,为了产线的效率提升,我们更多的应该培养产线技术人员,出现问题便可以最快速度解决问题&…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
【Linux】自动化构建-Make/Makefile
前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具:make/makfile 1.背景 在一个工程中源文件不计其数,其按类型、功能、模块分别放在若干个目录中,mak…...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...
