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

【学习笔记】[COCI2018-2019#1] Teoretičar

首先,可以发现 C C C等于所有点度数的最大值,我们能用到的颜色数目为 2 x ≥ C 2^x\ge C 2xC

考虑分治,将边集划分为 E = E 1 + E 2 E=E_1+E_2 E=E1+E2,使得 E 1 , E 2 E_1,E_2 E1,E2中点度数的最大值都不超过 2 x − 1 2^{x-1} 2x1。这样,我们将 [ 1 , 2 x − 1 ] [1,2^{x-1}] [1,2x1]中的颜色分配给 E 1 E_1 E1 [ 2 x − 1 + 1 , 2 x ] [2^{x-1}+1,2^x] [2x1+1,2x]中的颜色分配给 E 2 E_2 E2,就可以递归到子问题。显然当 C = 1 C=1 C=1时,可以将所有边染成同一个颜色。

显然,我们可以用欧拉回路解决这个问题。但是这个做法常数比较大。考虑 CF1499G Graph Coloring 的做法,维护若干个环和若干条端点互不相同的链(因为是二分图,所以环的长度一定是偶数),这可以用带权并查集维护。注意并查集的维护对象是每条边,合并两条边的时候限制等价于这两条边所属集合不同。

复杂度 O ( m log ⁡ m ) O(m\log m) O(mlogm)

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e5+5;
const int M=5e5+5;
int L,R,m,U[M],V[M],du[N],st[N];
int fa[M],val[M],tag[M],res[M];
vector<int>v;
int find(int x){if(fa[x]==x)return x;int tmp=fa[x];fa[x]=find(fa[x]);val[x]^=val[tmp];return fa[x];
}
void upd(int x){find(x);if(!(val[x]^tag[fa[x]])){tag[fa[x]]^=1;}
}
void unionset(int x,int y){int u=find(x),v=find(y);if(u!=v){val[u]=val[x]^val[y]^1,fa[u]=v;}
}
void solve(vector<int>&v,int cur){if(v.size()==0)return;for(auto e:v){fa[e]=e,val[e]=0,tag[e]=0,st[U[e]]=st[V[e]]=0;}int f=0;for(auto e:v){int x=U[e],y=V[e];if(st[x]||st[y])f=1;if(!st[x]&&!st[y]){st[x]=st[y]=e;}else if(!st[x]){upd(st[y]);unionset(e,st[y]);st[x]=e,st[y]=0;}else if(!st[y]){upd(st[x]);unionset(e,st[x]);st[y]=e,st[x]=0;}else{upd(st[x]),upd(st[y]);unionset(e,st[x]),unionset(e,st[y]);st[x]=st[y]=0;}}if(f==0){for(auto e:v)res[e]=1;}else{vector<int>vl,vr;for(auto e:v){find(e);if(val[e]^tag[fa[e]]){vr.pb(e);}else{vl.pb(e);}}solve(vl,cur>>1),solve(vr,cur>>1);for(auto e:vr)res[e]+=cur>>1;}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>L>>R>>m;for(int i=1;i<=m;i++){cin>>U[i]>>V[i],V[i]+=L;du[U[i]]++,du[V[i]]++,v.pb(i);}int dmax=0;for(int i=1;i<=L+R;i++)dmax=max(dmax,du[i]);int x=2;while(x<dmax)x<<=1;solve(v,x);cout<<x<<"\n";for(int i=1;i<=m;i++)cout<<res[i]<<"\n";
}

相关文章:

【学习笔记】[COCI2018-2019#1] Teoretičar

首先&#xff0c;可以发现 C C C等于所有点度数的最大值&#xff0c;我们能用到的颜色数目为 2 x ≥ C 2^x\ge C 2x≥C。 考虑分治&#xff0c;将边集划分为 E E 1 E 2 EE_1E_2 EE1​E2​&#xff0c;使得 E 1 , E 2 E_1,E_2 E1​,E2​中点度数的最大值都不超过 2 x − 1 2^…...

64位Office API声明语句第112讲

跟我学VBA&#xff0c;我这里专注VBA, 授人以渔。我98年开始&#xff0c;从源码接触VBA已经20余年了&#xff0c;随着年龄的增长&#xff0c;越来越觉得有必要把这项技能传递给需要这项技术的职场人员。希望职场和数据打交道的朋友&#xff0c;都来学习VBA,利用VBA,起码可以提高…...

C++ day3作业

1> 思维导图 2> 自己封装一个矩形类(Rect)&#xff0c;拥有私有属性:宽度(width)、高度(height)&#xff0c; 定义公有成员函数: 初始化函数:void init(int w, int h) 更改宽度的函数:set_w(int w) 更改高度的函数:set_h(int h) 输出该矩形的周长和面积函数:void s…...

蓝桥杯官网填空题(方格计数)

题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 如下图所示&#xff0c;在二维平面上有无数个 11 的小方格。 我们以某个小方格的一个顶点为圆心画一个半径为 50000 的圆。 你能计算出这个圆里有多少个完整的小方…...

【系统架构设计】计算机公共基础知识: 6 知识产权与标准化

一 知识产权 1 保护对象和范围 法律法规名称保护对象及范围注意事项著作权法著作权 文学、绘画、摄影等作品 不需要申请,作品完成就开始保护。 绘画或摄影作品原件出售(赠予)著作权归还原作者,原件拥有者有所有权和展览权。 软件著作权法 计算机软件保护条例 软件著作权 软…...

【新】致远OA从前台XXE到RCE漏洞分析

0x01 前言 致远OA是目前国内最流行的OA系统之一&#xff0c;前几年也曾爆出过多个安全漏洞。致远官方一直对修复漏洞的态度十分积极&#xff0c;目前能有效利用的致远漏洞已经很少了。 和我们之前分享过的通达OA的漏洞类似&#xff0c;这类主流OA系统现在想要直接一步达到RCE的…...

宠物领养系统jsp+servlet+mysql

设计不同用户的操作权限、注册和登录方法。 管理员可以在管理员管理、用户管理、宠物管理、评论管理、团队活动管理、志愿者的申请等等模块中进行查询、添加、删除、修改。 管理员可以在领养管理中通过领养时间查询所有宠物被领养的信息&#xff0c;修改是否同意领养宠物&#…...

MySQL 数据库安全性练习题

数据库安全性 一、实验目的 &#xff08;1&#xff09;熟悉通过MySQL对数据进行安全性控制 二、实验环境 Windows 11 MySQL Navicat 三、实验内容 今有以下两个关系模式&#xff1a; 职工&#xff08;职工号&#xff0c;姓名&#xff0c;年龄&#xff0c;职务&#xff0c;工…...

如何使用Node.js快速创建HTTP服务器并实现公网访问本地Server

文章目录 前言1.安装Node.js环境2.创建node.js服务3. 访问node.js 服务4.内网穿透4.1 安装配置cpolar内网穿透4.2 创建隧道映射本地端口 5.固定公网地址 前言 Node.js 是能够在服务器端运行 JavaScript 的开放源代码、跨平台运行环境。Node.js 由 OpenJS Foundation&#xff0…...

zigbee路灯无线通讯机制

zigbee路灯无线通讯机制 wang20160630 前言 目前路灯上通讯主要有电力载波和无线通讯&#xff1b;各有利弊&#xff0c;众说纷纭&#xff1b;本文不对两种技术进行比较&#xff0c;也不讨论哪种好&#xff0c;毕竟同种通讯模块&#xff0c;有的开发出来稳定&#xff0c;有的…...

asp.net docker-compose添加kafka和redis和zookeeper

docker-compose.yml添加 redis:image: redis:alpinekafka:image: "bitnami/kafka:3.1.1"depends_on:- zookeeperzookeeper:image: "bitnami/zookeeper:3.5.10" docker-compose.override.yml添加 redis:ports:- "6379"kafka:links: - zookeepere…...

2024上海国际人工智能展(CSITF)“创新驱动发展·科技引领未来”

人工智能&#xff08;Artificial Intelligence&#xff0c;AI&#xff09;作为当今世界科技发展的关键领域之一&#xff0c;正不断推动着各行各业的创新和变革。作为世界上最大的消费市场之一&#xff0c;中国正在积极努力将AI技术与产业融合并加速推广应用。在这个背景下&…...

汽车标定技术(三)--XCP协议如何支持测量功能

目录 1. 概述 2. 测量方式 -- Poll 3. 测量方式 -- DAQ 3.1 ODT概念模型 3.2 DAQ List概念 3.3 ODT 绝对编号和相对编号 3.4 静态DAQ和动态DAQ模式 &#xff08;1&#xff09;静态DAQ &#xff08;2&#xff09;动态DAQ 4.小结 1. 概述 在该系列的首篇文章汽车标定技…...

[c++]你最喜爱的stringstream和snprintf性能深入剖析

最近写一个程序中两个差不多的模块&#xff0c;一个使用了snprintf输出中间数据&#xff0c;另一个偷懒使用stringstream。结果你猜怎么着&#xff1f;居然压帧了&#xff01;&#xff01;到底是谁拖了性能的后退&#xff1f; 来自阿里云的性能分析实验 我上网一搜&#xff0…...

windows 用vs创建cmake工程并编译opencv应用项目生成exe流程简述

目录 前言一、安装opencv&#xff08;1&#xff09;下载&#xff08;2&#xff09;双击安装&#xff08;3&#xff09;环境变量和system文件夹设置 二、打开vs创建项目三、编辑cpp&#xff0c;.h&#xff0c;cmakelist.txt文件&#xff08;1&#xff09;h文件&#xff08;2&…...

QML 仪表盘小示例

本次项目已发布在CSDN->GitCode,下载方便,安全,可在我主页进行下载即可,后面的项目和素材都会发布这个平台。 个人主页:https://gitcode.com/user/m0_45463480怎么下载:在项目中点击克隆,windows:zip linux:tar.gz tar # .pro TEMPLATE = appTARGET = dialcontrol​#…...

力扣206. 反转链表

题目: 给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。 示例1&#xff1a; 输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[5,4,3,2,1] 示例 2&#xff1a; 输入&#xff1a;head [1,2] 输出&#xff1a;[2,1] 示例 3&#xff1a;…...

深度学习之基于Tensorflow卷积神经网络花卉识别系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 深度学习是一种机器学习方法&#xff0c;它通过模拟人脑神经网络的结构和功能来实现对数据的自动分析和学习。卷积神…...

leetcode链表

这几天手的骨裂稍微好一点了&#xff0c;但是还是很疼&#xff0c;最近学校的课是真多&#xff0c;我都没时间做自己的事&#xff0c;但是好在今天下午是没有课的&#xff0c;我也终于可以做自己的事情了。 今天分享几道题目 移除链表元素 这道题我们将以两种方法开解决&…...

Kali Linux渗透测试的艺术

Kali Linux&#xff08;Kali&#xff09;是专门用于渗透测试的Linux操作系统&#xff0c;它由BackTrack 发展而来。在整合了IWHAX、WHOPPIX 和Auditor 这3 种渗透测试专用Live Linux 之后&#xff0c;BackTrack正式改名为Kali Linux。 BackTrack是相当著名的Linux发行版本。在…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...