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

2023河南萌新联赛第(五)场:郑州轻工业大学 --Kruskal

题目描述

给定一张nnn个点的无向完全图,其中两点之间的路径边权为两点编号的按位与(编号为 (1,2,...,n)(1,2,...,n)(1,2,...,n)),即w(u,v)=u&v(1≤u,v≤n)w\left(u, v \right )=u\&v \left( 1 \le u, v \le n \right)w(u,v)=u&v(1≤u,v≤n),求该图最小生成树的边权和。

输入描述:

本题包含多组数据
第一行包含一个正整数T(1≤T≤2×105)T \left( 1 \le T \le 2 \times 10^5 \right)T(1≤T≤2×105),代表测试用例的组数。
对于每组数据:
第一行输入一个正整数n(2≤n<109)n \left( 2 \le n < 10^{9} \right)n(2≤n<109),代表该完全图的节点个数。

输出描述:

对于每组数据:
输出一行一个整数,代表该完全图最小生成树的边权和。

示例1

输入

1
3

输出

1

说明

对于n=3n=3n=3的完全图,生成树的方式有如下三种:

*  \leftrightarrow 2, 1 \leftrightarrow 3,生成树的权值之和为0+1=1

*  1\leftrightarrow 3, 2 \leftrightarrow 3,生成树的权值之和为1+2=3

* 1 \leftrightarrow 2, 2 \leftrightarrow 3,生成树的权值之和为0+2=2

选择第一种连接方式最优,因此最小生成树的权值之和为1。

思路:

做这个题首先要先了解二进制的一些小特征

第一个,我们要知道所有的偶数二进制的最后以为一定是0,所以我可以用 1 去连接所有的偶数,总权值和为0

第二个,我们要知道一个特点,就是二进制的中,高位的一个1,即使后面全是0,他也比高位为0后面全是1的数大,所以我们的奇数就可以分为两类了,一类是二进制全部为1的,一类是二进制中有0存在的。

二进制中全部为1的数,我们要想让他贡献最小,可以考虑他的下一个数存不存在。比如  7=(111)_2  就可以用8=(1000)_2 来连接,他的贡献也是 0.

二进制中有 0 存在的,我们就可以找小于他的一个数来跟他连接,找的这个数的二进制各位数字恰好与其相反,所以这一类的贡献也都是0

综上,我们就可以看出答案只有两种情况,一个是1,一个是0。总结起来,其实就是看最后一个数属于哪一类,如果属于二进制中全1的一类的话,他的下一个就不存在了,所以我们只能考虑让他跟1连,与运算之后是1.(与其他数运算结果为什么大,就是第二条)

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
int a[N];
void solve(){int n;cin >> n;if(n % 2 == 0){cout << "0\n";}else{bool flag = 0;while(n){if(n % 2 == 0){flag = 1;break;}n /= 2;}if(flag)cout << "0\n";else cout << "1\n";}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while(T--){solve();}return 0;
}

相关文章:

2023河南萌新联赛第(五)场:郑州轻工业大学 --Kruskal

题目描述 给定一张nnn个点的无向完全图&#xff0c;其中两点之间的路径边权为两点编号的按位与&#xff08;编号为 (1,2,...,n)(1,2,...,n)(1,2,...,n)&#xff09;&#xff0c;即w(u,v)u&v(1≤u,v≤n)w\left(u, v \right )u\&v \left( 1 \le u, v \le n \right)w(u,v…...

Maven引入本地jar包

maven做为一种强大的依赖管理工具&#xff0c;可以帮助我们更方便的管理项目中的依赖&#xff1b;而在使用过程中我们难免会有需要引入本地jar包的需求&#xff0c;这里踩过坑之后我分享俩种引入方式&#xff1b; 1.上传jar到本地maven仓库&#xff0c;再引入 使用此方法后可…...

Java并发编程实战——结构化并发应用程序

文章目录 6 任务执行6.1 在线程中执行任务6.1.1 串行地执行任务6.1.2 显式地为任务创建线程6.1.3 无限制创建线程的不足 6.2 Executor框架6.2.1 示例&#xff1a;基于Executor的Web服务器6.2.2 执行策略6.2.3 线程池6.2.4 Executor的生命周期6.2.5 延迟任务与周期任务 6.3 找出…...

uniapp echarts 点击失效

这个问题网上搜了一堆&#xff0c;有的让你降版本&#xff0c;有的让你改源码。。。都不太符合预期&#xff0c;目前我的方法可以用最新的echarts。 这个方法就是由npm安装转为CDN&#xff0c;当然你可能会质疑用CDN这样会不稳定&#xff0c;那如果CDN的地址是本地呢&#xff1…...

手机开启应急预警通知 / 地震预警

前言 安卓手机在检测到地震时&#xff0c;将发送地震预警通知&#xff0c;但此设置是默认关闭的&#xff0c;原因是以防引发用户恐慌从而引发安全问题&#xff0c;且开启此设置需要完成指引教程&#xff0c;因此默认关闭此设置。下文介绍如何开启此设置。 开启方法 华为手机开…...

2020年12月 Python(一级)真题解析#中国电子学会#全国青少年软件编程等级考试

一、单选题(共25题,每题2分,共50分) 第1题 执行语句print(10==10.0)的结果为? A:10 B:10.0 C:True D:False 正确的答案是 C:True。 解析:在Python中,比较运算符 “==” 用于比较两个值是否相等。在这个特定的比较中,整数10和浮点数10.0在数值上是相等的。…...

遇到无法复现的 Bug

当我们在软件开发过程中遇到无法复现的 Bug 时&#xff0c;这可能会让我们感到头疼和困惑。处理这种 Bug 需要一些技巧和方法来帮助我们更好地解决问题。本篇博客将为大家总结一些常用的技术手段和策略&#xff0c;希望能对开发者们在日常工作中遇到类似问题时提供一些帮助。 …...

虚拟列表的实现(简单易懂)

起因&#xff1a; app开发过程中遇到需要渲染3000行的列表&#xff0c;页面直接卡顿&#xff0c;所以开始研究起虚拟列表 实现前提条件&#xff1a; item项等高列表 实现思路&#xff1a; 首先是dom结构&#xff1a; 定义一个容器&#xff08;固定高度&#xff09;&#…...

【WordPress】如何在WordPress中实现真·页面路由

这篇文章也可以在我的博客中查看 页面路由 是什么 页面路由是指从url顺着网线砍到网站内容的途径&#xff0c;说人话就是地址与页面的映射。 就像真实世界的地址一样&#xff0c;我要找你&#xff0c;必须知道你的地址。 在网站中&#xff0c;通过地址找内容的机制&#xf…...

Android界面设计与用户体验

Android界面设计与用户体验 1. 引言 在如今竞争激烈的移动应用市场&#xff0c;提供优秀的用户体验成为了应用开发的关键要素。无论应用功能多么强大&#xff0c;如果用户界面设计不合理&#xff0c;用户体验不佳&#xff0c;很可能会导致用户流失。因此&#xff0c;在Androi…...

基于 FFmpeg 的跨平台视频播放器简明教程(八):音画同步

系列文章目录 基于 FFmpeg 的跨平台视频播放器简明教程&#xff08;一&#xff09;&#xff1a;FFMPEG Conan 环境集成基于 FFmpeg 的跨平台视频播放器简明教程&#xff08;二&#xff09;&#xff1a;基础知识和解封装&#xff08;demux&#xff09;基于 FFmpeg 的跨平台视频…...

【NLP pytorch】基于BiLSTM-CRF模型医疗数据实体识别实战(项目详解)

基于BiLSTM-CRF模型医疗数据实体识别实战 1数据来源与加载1.1 数据来源1.2 数据类别名称和定义1.3 数据介绍2 模型介绍2 数据预处理2.1 数据读取2.2 数据标注2.3 数据集划分2.4 词表和标签的生成3 Dataset和DataLoader3.1 Dataset3.2 DataLoader4 BiLSTM模型定义5 CRF模型6 模型…...

人工智能原理(1)

*请注意&#xff0c;本文仅供学习使用* 目录 一、人工智能发展 1、孕育期 2、摇篮期 3、形成期 4、发展期&#xff08;1970-1979&#xff09; 5、实用期 6、稳步发展期 二、何为人工智能 1、智能的主要观点 2、智能定义 3、人工智能定义 三、人工智能研究方法 1、…...

预测成真,国内传来三个消息,中国年轻人变了,创新力产品崛起

中国的年轻人真的变了&#xff01; 最近&#xff0c;国内传来三个消息&#xff0c;让外媒的预测成真。 第一&#xff0c;奥迪要开始用国产车的平台了。这里需要说明的是新能源汽车&#xff0c;奥迪也曾多次公开表示&#xff0c;承认了当前中国新能源汽车核心技术上的领先。 第…...

维深(Wellsenn):2023中国消费端VR内容开发商调研报告(附下载

关于报告的所有内容&#xff0c;公众【营销人星球】获取下载查看 核心观点 国内互联网大厂商入局VR&#xff0c;字节跳动、网易表态明确。字节跳动2021年收购国内头部VR硬件厂商PICO后&#xff0c;加速构建VR内容生态&#xff0c;2021年 成立海南创见未来当前已推出VR视频应用…...

redis事务管理详解

事务管理 事务管理乐观锁与悲观锁watch命令实现乐观锁watch命令示例 事务管理 Redis 提供了事务管理功能&#xff0c;可以通过 Redis 的 MULTI、EXEC、WATCH 和 DISCARD 命令来实现。 开启事务&#xff1a; 使用 MULTI 命令开始一个事务&#xff0c;表示接下来执行的命令都属于…...

国产低功耗蓝牙HS6621CxC/6621Px系列支持Find My网络功能方案芯片

目录 什么是“Find My“&#xff1f;HS6621系列简介 什么是“Find My“&#xff1f; “Find My”是苹果公司于19年前推出的针对失物追踪&#xff0c;Find My iPhone&#xff08;查找我的iPhone&#xff09;和Find My Friends&#xff08;查找朋友&#xff09;的结合体应用。为…...

【openGauss】分区表的介绍与使用

一、openGauss分区表介绍 在openGauss中&#xff0c;数据分区是在一个节点内部对数据按照用户指定的策略做进一步的水平分表&#xff0c;将表中的数据按照指定方式划分为多个互不重叠的部分。 对于大多数用户使用场景&#xff0c;分区表和普通表相比具有以下优点&#xff1a; …...

代码随想录算法训练营day57

文章目录 Day57回文子串题目思路代码 最长回文子序列题目思路代码 Day57 回文子串 647. 回文子串 - 力扣&#xff08;LeetCode&#xff09; 题目 给你一个字符串 s &#xff0c;请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。…...

【基础类】—前后端通信类系统性学习

一、什么是同源策略及限制 同源策略限制从一个源加载的文档或脚本如何与来自另一个源的资源进行交互。这是一个用于隔离潜在恶意文件的关键的安全机制。源&#xff1a;协议、域名和端口&#xff0c; 默认端口是80 三者有一个不同&#xff0c;即源不同&#xff0c;就是跨域 ht…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...