牛客练习赛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
场景:一个宽敞明亮的办公室,一位公司高管坐在办公桌前。 高管(自言自语):淘宝,这个平台上商品真是琳琅满目,应该有不少销售数据吧。我该怎么利用这些数据呢? 突然,房间…...
开源剧本AI落地实操:像素剧本圣殿+Dual-GPU并行推理完整教程
开源剧本AI落地实操:像素剧本圣殿Dual-GPU并行推理完整教程 1. 项目概览 像素剧本圣殿(Pixel Script Temple)是一款基于Qwen2.5-14B-Instruct深度微调的专业剧本创作工具。这个开源项目将先进的AI推理能力与独特的8-Bit复古美学相结合&…...
舰艇推进电机供电流程优化方案
舰艇推进电机供电流程优化方案 第一章 绪论 1.1 背景与意义 现代舰艇(如驱逐舰、潜艇、全电推进船舶)广泛采用综合电力系统。传统的供电流程中,推进电机作为最大的非线性负载,其负载突变(如急加速、倒车、波浪冲击导致的螺旋桨甩尾)会通过直流母线回馈至发电机组,导致…...
hadoop+spark+hive基于大数据的食谱分析与个性化推荐系统 美食推荐系统 美食可视化 大数据毕业设计
前言随着互联网技术的快速发展,人们获取信息的方式发生了巨大变化。特别是在食品领域,用户渴望获得更加个性化的推荐服务。大数据分析技术的出现为满足这一需求提供了可能。并据此提供精准的食谱推荐,从而提升用户体验。系统架构设计本项目 采…...
基于Spark+Hadoop+Hive 深度学习大数据的运河航运效率提升平台的设计与实现
前言随着全球贸易的不断发展,运河航运作为连接内陆与海洋的重要交通方式,其运输效率的提升对于促进经济发展、优化资源配置具有重要意义。基于大数据的运河航运效率提升平台的设计与实现,旨在通过收集、处理和分析大量的航运数据,…...
【Python MCP服务器安全开发黄金模板】:20年专家亲授7大零信任实践与3层防御体系
第一章:Python MCP服务器安全开发黄金模板概览Python MCP(Model-Controller-Protocol)服务器是一种面向协议驱动、可扩展性强的后端服务架构,广泛应用于物联网控制平台与微服务网关场景。本章所介绍的“黄金模板”并非通用框架&am…...
解锁智能OCR新范式:Pix2Text多模态内容识别技术全解析
解锁智能OCR新范式:Pix2Text多模态内容识别技术全解析 【免费下载链接】Pix2Text Pix In, Latex & Text Out. Recognize Chinese, English Texts, and Math Formulas from Images. 项目地址: https://gitcode.com/gh_mirrors/pi/Pix2Text Pix2Text是一款…...
3大创新让OpenRocket成为开源工程工具的典范:从问题到实践的完整指南
3大创新让OpenRocket成为开源工程工具的典范:从问题到实践的完整指南 【免费下载链接】openrocket Model-rocketry aerodynamics and trajectory simulation software 项目地址: https://gitcode.com/GitHub_Trending/op/openrocket OpenRocket是一款基于Jav…...
MULTISIM仿真揭秘:如何设计高可靠性的光耦隔离PMOS驱动电路
1. 光耦隔离PMOS驱动电路的设计挑战 在工业控制和高压隔离场景中,PMOS驱动电路的设计往往面临诸多挑战。我曾在多个项目中遇到过MOS管因静电击穿而损坏的情况,也经历过因开关频率不足导致系统性能下降的尴尬。这些问题归根结底都与MOS管的特性有关。 MOS…...
LFM2.5-1.2B-Thinking-GGUF开源生态初探:与Ollama等工具的对比与集成
LFM2.5-1.2B-Thinking-GGUF开源生态初探:与Ollama等工具的对比与集成 1. 开源大模型本地部署生态概览 近年来,开源大模型本地部署工具呈现百花齐放的局面。从早期的单一模型加载器,发展到如今功能丰富的模型管理生态系统,开发者…...
从ULN2803芯片内部拆解,聊聊三极管“黄金搭档”达林顿管到底强在哪?
ULN2803芯片拆解:达林顿管如何成为三极管的“黄金搭档”? 当我们需要用单片机的微弱IO口信号(通常只有几毫安)驱动继电器、电机这类“大胃王”负载时,就像试图用一根吸管给游泳池注水——理论可行,实际效率…...
