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;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/82785.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

CSS:盒子模型 与 多种横向布局方法

目录 盒子模型块级盒子内联级盒子内联块级盒子弹性盒子display 改变模型区域划分text 内容区padding 填充区border 边框区margin 外边距直接设置盒子大小 布局横向布局方法一 float 浮起来方法二 内联块级元素实现方法三 弹性盒子模型 盒子模型 块级盒子 独占一行&#xff0c…

layui的基本使用-日期控件的业务场景使用入门实战案例一

效果镇楼; 1 前端UI层面; <!DOCTYPE html> <html lang="en"> <head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" conten…

【前端】html

HTML标签&#xff08;上&#xff09; 目标&#xff1a; -能够说出标签的书写注意规范 -能够写出HTML骨架标签 -能够写出超链接标签 -能够写出图片标签并说出alt和title的区别 -能够说出相对路径的三种形式 目录&#xff1a; HTML语法规范HTML基本结构标签开发工具HTML常用标…

Android SystemServer中Service的创建和启动方式(基于Android13)

Android SystemServer创建和启动方式(基于Android13) SystemServer 简介 Android System Server是Android框架的核心组件&#xff0c;运行在system_server进程中&#xff0c;拥有system权限。它在Android系统中扮演重要角色&#xff0c;提供服务管理和通信。 system …

浅析 C 语言的共用体、枚举和位域

前言 最近在尝试阅读一些系统库的源码&#xff0c;但是其中存在很多让我感到既熟悉又陌生的语法。经过资料查阅&#xff0c;发现是 C 语言中的共用体和位域。于是&#xff0c;趁着课本还没有扔掉&#xff0c;将一些相关的知识点记录在本文。 文章目录 前言共用体 (union)枚举…

zookeeper常用命令

zookeeper常用命令 1. 下载安装2. 配置说明2.1 配置 3. zookeeper的常见命令3.1 server端启动停止等命令3.2 客户端连接等命令3.3 客户端简单常用命令3.3.1 查看目录&#xff08;查看数据结构&#xff09;3.3.2 删除目录3.3.3 创建目录3.3.4 创建目录并写入值 查看节点值3.3.5…

原型链污染,nodejs逃逸例子

文章目录 原型链污染原型链污染原理原型链污染小例子 原型链污染题目解析第一题第二题 Nodejs沙箱逃逸方法一方法二 原型链污染 原型链污染原理 原型链 function test(){this.a test; } b new test;可以看到b在实例化为test对象以后&#xff0c;就可以输出test类中的属性a…

【腾讯云 Cloud Studio 实战训练营】使用Cloud Studio构建SpringSecurity权限框架

1.Cloud Studio&#xff08;云端 IDE&#xff09;简介 Cloud Studio 是基于浏览器的集成式开发环境&#xff08;IDE&#xff09;&#xff0c;为开发者提供了一个永不间断的云端工作站。用户在使用 Cloud Studio 时无需安装&#xff0c;随时随地打开浏览器就能在线编程。 Clou…

XSS漏洞原理及利用跨站请求伪造CSRF

XSS漏洞原理及利用&跨站请求伪造CSRF XSS一、案例二、什么是XSS三、XSS危害四、XSS的分类4.1、反射型XSS4.1.1、介绍4.1.2、利用过程 4.2、存储型XSS4.2.1、介绍4.2.2、利用过程4.2.3、案例 4.3、DOM型XSS4.3.1、介绍4.3.2、常用的DOM方法4.3.3、案例4.3.3.1、代码分析4.3.…

如何快速完成MySQL数据的差异对比|NineData

在现代商业环境中&#xff0c;数据库是企业存储核心数据的重要工具&#xff0c;而 MySQL 作为最受欢迎的关系型数据库管理系统&#xff0c;广泛应用于各行各业。在容灾、数据迁移、备份恢复等场景下&#xff0c;为了确保两端或多端之间数据的一致性&#xff0c;通常需要对数据进…

Android 实现 RecyclerView下拉刷新,SwipeRefreshLayout上拉加载

上拉、下拉的效果图如下&#xff1a; 使用步骤 1、在清单文件中添加依赖 implementation ‘com.android.support:recyclerview-v7:27.1.1’ implementation “androidx.swiperefreshlayout:swiperefreshlayout:1.0.0” 2、main布局 <LinearLayout xmlns:android"http…

渐进式云渲染和模块式云渲染:二者的区别与选择

云渲染是一种利用云计算技术&#xff0c;将本地的渲染任务分配到远程的服务器上进行高效、快速、低成本的渲染的服务。云渲染可以帮助用户节省时间、资金和硬件资源&#xff0c;提高工作效率和质量。但是&#xff0c;在使用云渲染时&#xff0c;用户需要面对一个重要的选择&…

SpringBoot 底层机制分析[上]

文章目录 分析SpringBoot 底层机制【Tomcat 启动分析Spring 容器初始化Tomcat 如何关联Spring 容器】[上]搭建SpringBoot 底层机制开发环境Configuration Bean 会发生什么&#xff0c;并分析机制提出问题&#xff1a;SpringBoot 是怎么启动Tomcat &#xff0c;并可以支持访问C…

【iOS】autoreleasepool

来说一下最近在了解的autoreleasepool吧&#xff0c;我们可能平时书写过许多脑残代码&#xff0c;其有很多的缺陷但是我们可能当时学的比较浅就也不太了解&#xff0c;就像下面这样的&#xff1a; for (int i 0; i < 1000000; i) {NSNumber *num [NSNumber numberWithInt…

matlab使用教程(10)—脚本和函数

1.概述 MATLAB 提供了一个强大的编程语言和交互式计算环境。您可以使用此语言在 MATLAB 命令行中一次输入一个命令&#xff0c;也可以向某个文件写入一系列命令&#xff0c;按照执行任何 MATLAB 函数的相同方式来执行这些命令。使用 MATLAB 编辑器或任何其他文件编辑器可以创建…

HCIP实验

实验题目如下&#xff1a; 实验拓扑如下&#xff1a; 实验要求如下&#xff1a; 【1】两个协议间进行多点双向重发布 【2】R7的环回没有宣告在OSPF协议中&#xff0c;而是后期重发布进入的 【3】解决环路&#xff0c;所有路径选择最优&#xff0c;且存在备份 实验思路如下&…

九、Spring 声明式事务学习总结

文章目录 一、声明式事务1.1 什么是事务1.2 事务的应用场景1.3 事务的特性&#xff08;ACID&#xff09;1.4 未使用事务的代码示例1.5 配置 Spring 声明式事务学习总结 一、声明式事务 1.1 什么是事务 把一组业务当成一个业务来做&#xff1b;要么都成功&#xff0c;要么都失败…

网络安全的相关知识点

网络安全威胁类型&#xff1a; 1.窃听&#xff1a;广播式网络系统。 2.假冒 3.重放&#xff1a;重复一份报文或者报文的一部分&#xff0c;以便产生一个被授权的效果。 4.流量分析 5.数据完整性破坏 6.拒绝服务 7.资源的非授权使用 8.陷门和特洛伊木马&#xff1a;木马病毒有客…

解数独(Java)

题目链接&#xff1a; 力扣 题目详情&#xff1a; 37. 解数独t编写一个程序&#xff0c;通过填充空格来解决数独问题。 数独的解法需 遵循如下规则&#xff1a; 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只…

jmeter测试rpc接口-使用dubbo框架调用【杭州多测师_王sir】

1.基于SOAP架构。基于XML规范。基于WebService协议。特点:接口地址?wsdl结尾2.基于RPC架构&#xff0c;基于dubbo协议&#xff0c;thrift协议。SpringCloud微服务。3.基于RestFul架构&#xff0c;基于json规范。基于http协议(我们常用的都是这种&#xff0c;cms平台也是) Rest…