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

【学习笔记】CF1305 Kuroni and Antihype

想了一下,觉得还是发单篇的题解比较合理

怎么感觉这题之前做过

先抛开建边方式不管 这一步其实挺重要的,但是可能大多数人独立做这道题的时候都在想用位运算的性质,而没有想到分开考虑吧?,考虑新建000号节点,问题转化为如果aiand aj=0a_i\ \text{and}\ a_j=0ai and aj=0,那么存在i→ji\to jij的长度为aja_jaj的边,以及j→ij\to iji的长度为aia_iai的边,求以000为根节点的最大树形图。

观察发现边权和等于将每条边看成ai+aja_i+a_jai+aj求和后再减去∑ai\sum a_iai,因此无向图的生成树也对应一个树形图。

因此可以直接跑kruskal\text{kruskal}kruskal算法。从大到小枚举边权,然后枚举子集,注意一下细节应该可以通过。复杂度O(318)O(3^{18})O(318)时限开3s还是比较稳的

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int cnt[1<<18],vs[1<<18];
int n,m,fa[1<<18],a[1<<18];
ll res;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unionset(int x,int y){int u=find(x),v=find(y);if(u!=v){m-=cnt[u]+cnt[v]-1;res+=(ll)(cnt[u]+cnt[v]-1)*(x|y);fa[u]=v,cnt[v]=1;}
}
int main(){cin>>n;cnt[0]++;for(int i=0;i<1<<18;i++)fa[i]=i,vs[i]=0;for(int i=1;i<=n;i++){cin>>a[i],cnt[a[i]]++;}for(int i=(1<<18)-1;i>=0;i--){for(int j=i;j;j=(j-1)&i){if(cnt[j]&&cnt[i-j]){unionset(j,i-j);}}}for(int i=1;i<=n;i++)res-=a[i];cout<<res;
}

相关文章:

【学习笔记】CF1305 Kuroni and Antihype

想了一下&#xff0c;觉得还是发单篇的题解比较合理 怎么感觉这题之前做过 先抛开建边方式不管 这一步其实挺重要的&#xff0c;但是可能大多数人独立做这道题的时候都在想用位运算的性质&#xff0c;而没有想到分开考虑吧&#xff1f;&#xff0c;考虑新建000号节点&#xf…...

json-server单独使用或者在react中进行使用

json-serverjson-server使用教程修改json-server端口号启动1、全局安装json-server2、在根目录生成一个db.json3、启动 访问react中进行使用react中修改json-server启动端口号1、 第一步也是安装&#xff0c;和第一种一样2、在根路径下定义一个__json_server_mock__文件夹3、在…...

【6G 新技术】6G数据面介绍

博主未授权任何人或组织机构转载博主任何原创文章&#xff0c;感谢各位对原创的支持&#xff01; 博主链接 本人就职于国际知名终端厂商&#xff0c;负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作&#xff0c;目前牵头6G算力网络技术标准研究。 博客…...

【AI绘图学习笔记】深度前馈网络(一)

有关深度前馈网络的部分知识&#xff0c;我们已经在吴恩达的机器学习课程中有过了解了&#xff0c;本章主要是对《深度学习》花书中第六章&#xff1a;深度前馈网络的总结笔记。我希望你在看到这一章的时候&#xff0c;能回忆起机器学习课程中的一些环节或者细节&#xff0c;这…...

目标检测笔记合集

目标检测笔记合集1. 必看的两篇目标检测论文2. 必速看的深度学习目标检测的论文集及概述2.1 一份Slide&#xff08;PPT)两张表格带你快速了解目标检测2.2 最新目标检测算法回顾2022笔记合集3.目标检测的应用与需求4.目标检测的定义与挑战5.目标检测损失函数的进展6.目标检测IOU…...

《计算机网络》期末复习笔记

文章目录一、一些英文名词的标签&#xff08;方便记忆&#xff09;二、OSI七层协议三、综合题3.0 知识点储备3.1 在Internet 网中&#xff0c;某计算机的IP 地址是11001010.01100000.00101100.01011000 &#xff0c;请回答下列问题3.2 假定发送方要发送的数据为10000101。采用C…...

linux下安装SonarQube

目录1. 准备安装环境2. 安装postgres数据库3. 安装SonarQube4. 使用SonarQube1. 准备安装环境 这里安装SonarQube的系统环境是Red Hat Enterprise Linux release 8.7 &#xff0c;然后将jdk的压缩包&#xff08;jdk-17.0.2_linux-x64_bin.tar.gz&#xff09;和sonarQube的压缩…...

MyBatis-Plus(狂神)

一.特点 无侵入&#xff1a;只做增强不做改变&#xff0c;引入它不会对现有工程产生影响&#xff0c;如丝般顺滑损耗小&#xff1a;启动即会自动注入基本 CURD&#xff0c;性能基本无损耗&#xff0c;直接面向对象操作强大的 CRUD 操作&#xff1a;内置通用 Mapper、通用 Serv…...

Python3实现写作

导语T_T没有科研梦想的人半夜过来水篇文章~~~让Python学会写写歌&#xff0c;创创作~~~纯属娱乐~~~改编自PyTorch官网的一个教程&#xff0c;不过我用TF写的&#xff0c;然后生成英文变成了生成中文~~~Lets Go~~~相关文件百度网盘下载链接: https://pan.baidu.com/s/1VUEFR82Cq…...

UEFI实战--------HII之uni文件

uni文件 HII的实现涉及到多种不同类型的文件&#xff0c;uni文件是其中最简单的一种&#xff0c;它用来存放各种语言的字符串以实现本地化。本节主要参考自《edk-ii-uni-specification.pdf》&#xff0c;后面简称为参考文档。 关于uni文件的作用&#xff0c;在参考文档中做了如…...

基于Spring Boot集成MyBatis-3.5.9操作数据库

记录&#xff1a;382场景&#xff1a;在Spring Boot 2.6.3中集成MyBatis 3.5.9操作数据库。实现MyBatis的查、增、改、删操作数据库示例。MyBatis官网&#xff1a;http://www.mybatis.org/MyBatis源码&#xff1a;https://github.com/mybatis/1.初始化准备1.1创建Maven工程使用…...

了解国外SEO负面压制的现状与应对策略!

随着全球化的发展&#xff0c;越来越多的企业和品牌开始将目光转向海外市场&#xff0c;而谷歌作为全球最大的搜索引擎之一&#xff0c;也成为了外贸企业最主要的搜索引擎之一。 然而&#xff0c;随着谷歌的不断发展&#xff0c;国外SEO负面压制的现状也愈发严峻&#xff0c;外…...

Yolov5-交通标志检测与识别

项目介绍 上一篇文章介绍了基于卷积神经网络的交通标志分类识别Python交通标志识别基于卷积神经网络的保姆级教程&#xff08;Tensorflow&#xff09;&#xff0c;并且最后实现了一个pyqt5的GUI界面&#xff0c;并且还制作了一个简单的Falsk前端网页实现了前后端的一个简单交互…...

Linux内核Thermal框架详解五、Thermal Core(4)

本文部分内容参考Linux Thermal 学习笔记 - 爱码网。特此致谢&#xff01; 接前一篇文章Linux内核Thermal框架详解四、Thermal Core&#xff08;3&#xff09; 三、相关源码及分析 2. thermal_register_governors 上一回说到这一段代码&#xff1a; for (__governor __gove…...

gcc 编译的过程

#include <stdio.h> #define PI 3.14 int main(int argc, char const *argv[]) { //打印IP的值printf("PI %lf\n", PI);return 0; }编译的过程&#xff1a;预处理、编译、汇编、链接1.预处理&#xff1a;宏替换、删除注释、头文件包含、条件编译 -E &#xf…...

Hadoop入个门

文章目录1️⃣、Hadoop概述1.1、Hadoop是什么1.2、三大发行版本1.3、优势1.4、组成HDFSYARNMapReduceHDFS、YARN、MapReduce三者关系1.6、大数据技术生态体系image-202303111027195802️⃣、Hadoop运行环境搭建2.1、虚拟机环境准备2.2、克隆虚拟机2.3、在hadoop2上安装JDK2.4、…...

python 从0到批量下载某站视频

简介&#xff1a;真实从0到1&#xff0c;童叟无欺&#xff5e; 目标&#xff1a;用python批量下载某站搜索视频&#xff0c;以“CG 服装”为例 本章主要介绍如何用python把搜索到的视频直接下载到自己的本地文件夹中&#xff5e; 介绍一下工作流1. 下载并安装python2. 测试pyt…...

【深度学习】神经网络和深度学习--卷积和池化的作用

深度学习通常指训练大型深度的神经网络的过程。 与传统的神经网络模型相比&#xff0c;深度学习模型在结构上与之非常相似&#xff1b;不同的是&#xff0c;深度学习模型的“深度”更大&#xff0c;“深度”的体现就是神经网络层数多&#xff0c;神经网络每一层的结点数多。 本…...

锦正茂风冷系列电源JCP-10-80的技术参数

JCP-10-80为高稳定度的双极性恒流电源&#xff0c;广泛应用于电磁铁、亥姆霍兹线圈等感性负载的励磁。电源采用线性电源结构&#xff0c;输出电流稳定度高&#xff0c;纹波和噪声低。电源输出电流可在正负额定电流*值之间连续变化&#xff0c;电流平滑连续过零&#xff0c;可使…...

Idea+maven+spring-cloud项目搭建系列--11-1 dubbo(zookeeper,nacos)注册中心

前言&#xff1a;dubbo rpc 服务需要将服务提供者和消费者信息进行注册&#xff0c;以便于消费端可以完成远程接口调用&#xff1b;注册中心是 Dubbo 服务治理的核心组件&#xff0c;Dubbo 依赖注册中心的协调实现服务&#xff08;地址&#xff09;发现&#xff0c;自动化的服务…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...