牛客练习赛114 G-图上异或难题(线性基)
题目要求把点涂成白和黑两种颜色,如果一条边左右两端是不同的颜色的话,结果就异或这跳边的权值,求结果最大是多少
把边的贡献转换成点的贡献
我们只考虑白色点的情况下,如果一个点A是白色,就把结果异或上这一个点A周围的所有边,
如果在该点周围还有一个白色点B的话,那么我们同样把结果异或上这个点B的所有边
因为我们知道两个点是有线段相连,而且两个点都异或上该点周围的所有边了
所以两个点相邻的线段就被去掉了
其他点同理
这时候我们就可以把这个问题转换成一个线性基的问题
已知所以点的贡献是该点异或上周围所有边
求从n个点中选出一部分点染成白色的最大异或和
const int inf = 0x3f3f3f3f3f3f3f3f, N = 2e5 + 5, mod = 1e9 + 7;
vector<int>q[N];
int a[N];
signed main()
{ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);int T;cin >> T;while (T--){int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {q[i].clear(); a[i] = 0;}while (m--){int u, v, w;cin >> u >> v >> w;q[u].push_back(w);q[v].push_back(w);}for (int i = 1; i <= n; i++) {for (auto w : q[i]){a[i] ^= w;}}int k = 1;for (int i = 32; i >= 0; i--){for (int j = k; j <= n; j++) {if (a[j] >> i & 1) {swap(a[j], a[k]);break;}}if (!(a[k] >> i & 1)) continue;for (int j = 1; j <= n; j++) {if (j != k && (a[j] >> i & 1))a[j] ^= a[k];}k++;if (k == n + 1) break;}int res = 0;for (int i = 1; i <= k; i++) {res ^= a[i];}cout << res << "\n";}
}
相关文章:
牛客练习赛114 G-图上异或难题(线性基)
题目要求把点涂成白和黑两种颜色,如果一条边左右两端是不同的颜色的话,结果就异或这跳边的权值,求结果最大是多少 把边的贡献转换成点的贡献 我们只考虑白色点的情况下,如果一个点A是白色,就把结果异或上这一个点A周…...
Neo4j之ORDER BY基础
ORDER BY 语句用于对查询结果进行排序。以下是一些常用的示例和解释: 按属性值排序: MATCH (p:Person) RETURN p.name, p.age ORDER BY p.age DESC这个示例返回所有人节点的姓名和年龄属性,并按年龄降序排序。 按多个属性排序:…...
【C++杂货铺】探索vector的底层实现
文章目录 一、STL1.1 什么是STL?1.2 STL的版本1.3 STL的六大组件 二、vector的介绍及使用2.1 vector的介绍2.2 vector的使用2.2.1 vector的定义2.2.2 vector iterator2.2.3 vector空间增长问题2.2.4 vector增删查改 2.3 vector\<char\> 可以替代 string 嘛? …...
MybatisPlus(1)
前言🍭 ❤️❤️❤️SSM专栏更新中,各位大佬觉得写得不错,支持一下,感谢了!❤️❤️❤️ Spring Spring MVC MyBatis_冷兮雪的博客-CSDN博客 MyBatis-Plus(简称MP)是一个 Mybatis 的增强工具&…...
探索未来世界,解密区块链奥秘!
你是否曾好奇,区块链是如何影响着我们的生活与未来?想要轻松了解这个引领着技术革命的概念吗?那么这本令人着迷的新书《区块链导论》绝对值得你拥有! 内容丰富多彩,让你轻松掌握: **1章:区块链…...
win10 下运行 npm run watch-poll问题
背景:在本地练习laravel项目,windows 宝塔环境(之前装过ubuntu子系统,很慢,就放弃了。有知道的兄弟说下,抱拳)。以下命令我是在本地项目中用git bash里运行的,最好用管理员权限打开你…...
Android平台RTMP|RTSP直播播放器功能进阶探讨
我们需要怎样的直播播放器? 很多开发者在跟我聊天的时候,经常问我,为什么一个RTMP或RTSP播放器,你们需要设计那么多的接口,真的有必要吗?带着这样的疑惑,我们今天聊聊Android平台RTMP、RTSP播放…...
Centos7安装Telnet服务
简述 Centos7安装Telnet服务 前情提示 Centos7安装Telnet服务 一说 ● 部分截图、链接等因过期、更换域名、MD语法等可能不显示,可联系反馈(备注好博文地址),谢谢❤ ● 带有#号、删除线、不操作、不执行字样的为提示或者备份bash&…...
【C++】GCC对应C++的版本支持
1、查看当前GCC的版本 pffNUC12WSKi7:~$ gcc -v Using built-in specs. COLLECT_GCCgcc COLLECT_LTO_WRAPPER/usr/lib/gcc/x86_64-linux-gnu/9/lto-wrapper OFFLOAD_TARGET_NAMESnvptx-none:hsa OFFLOAD_TARGET_DEFAULT1 Target: x86_64-linux-gnu Configured with: ../src/co…...
前端面试:【算法】排序、查找、递归、动态规划
算法是计算机科学的核心,是解决问题的方法和步骤。在编程和软件开发中,了解和掌握各种常见算法至关重要。本文将详细介绍四种重要的算法:排序、查找、递归和动态规划,并提供示例来帮助你理解它们的应用。 1. 排序算法:…...
RK3399 开机自启一个shell脚本,一直起不来BUG
开机自启shell脚本如下: diff --git a/device/rockchip/common/sepolicy/file_contexts b/device/rockchip/common/sepolicy/file_contexts index eb6b5e4bb4..0bbe781a7c 100755 --- a/device/rockchip/common/sepolicy/file_contextsb/device/rockchip/common/se…...
[MyBatis系列④]核心配置文件
目录 1、简介 2、DTD 3、typeHandlers 3.1、默认类型处理器 3.2、自定义类型处理器 4、plugins ⭐MyBatis系列①:增删改查 ⭐MyBatis系列②:两种Dao开发方式 ⭐MyBatis系列③:动态SQL 1、简介 MyBatis的核心配置文件(通常命…...
系统架构设计高级技能 · 层次式架构设计理论与实践
系列文章目录 系统架构设计高级技能 软件架构概念、架构风格、ABSD、架构复用、DSSA(一)【系统架构设计师】 系统架构设计高级技能 系统质量属性与架构评估(二)【系统架构设计师】 系统架构设计高级技能 软件可靠性分析与设计…...
Nuxt3打包部署到Linux(node+pm2安装和运行步骤+nginx代理)
最近,我们项目组的工作接近尾声,需要把项目部署上线。由于前端第一次使用Nuxt3框架,后端也是第一次部署Nuxt3项目,所以刚开始出现了很多问题。在我上网搜索很多教程后,得到了基本的流程。 1.服务器安装node.js环境 N…...
一维数组传参
在C语言中,可以通过指针来传递一维数组。一维数组实际上是指向数组首元素的指针,在函数中传递数组参数时,可以将数组名作为指针传递给函数。以下是一个示例: #include <stdio.h>void myFunction(int arr[], int size) {for…...
七层、四层和五层网络模型区别和联系
七层、四层和五层网络模型区别和联系 概述OSI网络7层模型(概念型框架)概述图片分析 四层模型概述常用协议OSI与TCP/IP四层的区别 五层模型概述三种网络模型对比 总结 概述 网络模型-七层模型(OSI模型)、五层协议体系结构和TCP/IP…...
RH1288V3 - 初识物理服务器
如果你拥有一台物理服务器(不是云服务器) 个人比较推荐你用物理服务器,虽然性能会比云要来的差,但是不用每月交钱上。云服务固然方便,但是几个核的性能和一点存储,想做一个动漫网站固然要很多mp4这种影视资源,云服务器…...
excel中如果A列中某项有多条记录,针对A列中相同的项,将B列值进行相加合并统计
excel中如果A列中某项有多条记录,针对A列中相同的项,将B列值进行相加合并统计。注意:B列的数据类型要为数字 如: 实现方法: C1、D1中分别输入公式,然后下拉 IF(COUNTIF($A$1:A1,A1)1, A1,"") …...
开发智能应用的新范式:大数据、AI和云原生如何构建智能软件
文章目录 1.利用大数据实现智能洞察2. 集成人工智能和机器学习3. 云原生架构的弹性和灵活性4. 实现实时处理和响应5. 数据安全和隐私保护6. 可解释性和透明性7. 持续创新和迭代8. 数据伦理和合规性 🎈个人主页:程序员 小侯 🎐CSDN新晋作者 &a…...
淘宝免费爬虫数据 商品详情数据 商品销售额销量API
场景:一个宽敞明亮的办公室,一位公司高管坐在办公桌前。 高管(自言自语):淘宝,这个平台上商品真是琳琅满目,应该有不少销售数据吧。我该怎么利用这些数据呢? 突然,房间…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !
我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...
