【学习笔记】[COCI2018-2019#1] Teoretičar
首先,可以发现 C C C等于所有点度数的最大值,我们能用到的颜色数目为 2 x ≥ C 2^x\ge C 2x≥C。
考虑分治,将边集划分为 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} 2x−1。这样,我们将 [ 1 , 2 x − 1 ] [1,2^{x-1}] [1,2x−1]中的颜色分配给 E 1 E_1 E1, [ 2 x − 1 + 1 , 2 x ] [2^{x-1}+1,2^x] [2x−1+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
首先,可以发现 C C C等于所有点度数的最大值,我们能用到的颜色数目为 2 x ≥ C 2^x\ge C 2x≥C。 考虑分治,将边集划分为 E E 1 E 2 EE_1E_2 EE1E2,使得 E 1 , E 2 E_1,E_2 E1,E2中点度数的最大值都不超过 2 x − 1 2^…...
64位Office API声明语句第112讲
跟我学VBA,我这里专注VBA, 授人以渔。我98年开始,从源码接触VBA已经20余年了,随着年龄的增长,越来越觉得有必要把这项技能传递给需要这项技术的职场人员。希望职场和数据打交道的朋友,都来学习VBA,利用VBA,起码可以提高…...
C++ day3作业
1> 思维导图 2> 自己封装一个矩形类(Rect),拥有私有属性:宽度(width)、高度(height), 定义公有成员函数: 初始化函数:void init(int w, int h) 更改宽度的函数:set_w(int w) 更改高度的函数:set_h(int h) 输出该矩形的周长和面积函数:void s…...
蓝桥杯官网填空题(方格计数)
题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 如下图所示,在二维平面上有无数个 11 的小方格。 我们以某个小方格的一个顶点为圆心画一个半径为 50000 的圆。 你能计算出这个圆里有多少个完整的小方…...
【系统架构设计】计算机公共基础知识: 6 知识产权与标准化
一 知识产权 1 保护对象和范围 法律法规名称保护对象及范围注意事项著作权法著作权 文学、绘画、摄影等作品 不需要申请,作品完成就开始保护。 绘画或摄影作品原件出售(赠予)著作权归还原作者,原件拥有者有所有权和展览权。 软件著作权法 计算机软件保护条例 软件著作权 软…...
【新】致远OA从前台XXE到RCE漏洞分析
0x01 前言 致远OA是目前国内最流行的OA系统之一,前几年也曾爆出过多个安全漏洞。致远官方一直对修复漏洞的态度十分积极,目前能有效利用的致远漏洞已经很少了。 和我们之前分享过的通达OA的漏洞类似,这类主流OA系统现在想要直接一步达到RCE的…...
宠物领养系统jsp+servlet+mysql
设计不同用户的操作权限、注册和登录方法。 管理员可以在管理员管理、用户管理、宠物管理、评论管理、团队活动管理、志愿者的申请等等模块中进行查询、添加、删除、修改。 管理员可以在领养管理中通过领养时间查询所有宠物被领养的信息,修改是否同意领养宠物&#…...
MySQL 数据库安全性练习题
数据库安全性 一、实验目的 (1)熟悉通过MySQL对数据进行安全性控制 二、实验环境 Windows 11 MySQL Navicat 三、实验内容 今有以下两个关系模式: 职工(职工号,姓名,年龄,职务,工…...
如何使用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࿰…...
zigbee路灯无线通讯机制
zigbee路灯无线通讯机制 wang20160630 前言 目前路灯上通讯主要有电力载波和无线通讯;各有利弊,众说纷纭;本文不对两种技术进行比较,也不讨论哪种好,毕竟同种通讯模块,有的开发出来稳定,有的…...
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)“创新驱动发展·科技引领未来”
人工智能(Artificial Intelligence,AI)作为当今世界科技发展的关键领域之一,正不断推动着各行各业的创新和变革。作为世界上最大的消费市场之一,中国正在积极努力将AI技术与产业融合并加速推广应用。在这个背景下&…...
汽车标定技术(三)--XCP协议如何支持测量功能
目录 1. 概述 2. 测量方式 -- Poll 3. 测量方式 -- DAQ 3.1 ODT概念模型 3.2 DAQ List概念 3.3 ODT 绝对编号和相对编号 3.4 静态DAQ和动态DAQ模式 (1)静态DAQ (2)动态DAQ 4.小结 1. 概述 在该系列的首篇文章汽车标定技…...
[c++]你最喜爱的stringstream和snprintf性能深入剖析
最近写一个程序中两个差不多的模块,一个使用了snprintf输出中间数据,另一个偷懒使用stringstream。结果你猜怎么着?居然压帧了!!到底是谁拖了性能的后退? 来自阿里云的性能分析实验 我上网一搜࿰…...
windows 用vs创建cmake工程并编译opencv应用项目生成exe流程简述
目录 前言一、安装opencv(1)下载(2)双击安装(3)环境变量和system文件夹设置 二、打开vs创建项目三、编辑cpp,.h,cmakelist.txt文件(1)h文件(2&…...
QML 仪表盘小示例
本次项目已发布在CSDN->GitCode,下载方便,安全,可在我主页进行下载即可,后面的项目和素材都会发布这个平台。 个人主页:https://gitcode.com/user/m0_45463480怎么下载:在项目中点击克隆,windows:zip linux:tar.gz tar # .pro TEMPLATE = appTARGET = dialcontrol#…...
力扣206. 反转链表
题目: 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 示例1: 输入:head [1,2,3,4,5] 输出:[5,4,3,2,1] 示例 2: 输入:head [1,2] 输出:[2,1] 示例 3:…...
深度学习之基于Tensorflow卷积神经网络花卉识别系统
欢迎大家点赞、收藏、关注、评论啦 ,由于篇幅有限,只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 深度学习是一种机器学习方法,它通过模拟人脑神经网络的结构和功能来实现对数据的自动分析和学习。卷积神…...
leetcode链表
这几天手的骨裂稍微好一点了,但是还是很疼,最近学校的课是真多,我都没时间做自己的事,但是好在今天下午是没有课的,我也终于可以做自己的事情了。 今天分享几道题目 移除链表元素 这道题我们将以两种方法开解决&…...
Kali Linux渗透测试的艺术
Kali Linux(Kali)是专门用于渗透测试的Linux操作系统,它由BackTrack 发展而来。在整合了IWHAX、WHOPPIX 和Auditor 这3 种渗透测试专用Live Linux 之后,BackTrack正式改名为Kali Linux。 BackTrack是相当著名的Linux发行版本。在…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)
题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...
webpack面试题
面试题:webpack介绍和简单使用 一、webpack(模块化打包工具)1. webpack是把项目当作一个整体,通过给定的一个主文件,webpack将从这个主文件开始找到你项目当中的所有依赖文件,使用loaders来处理它们&#x…...
关于 ffmpeg设置摄像头报错“Could not set video options” 的解决方法
若该文为原创文章,转载请注明原文出处 本文章博客地址:https://hpzwl.blog.csdn.net/article/details/148515355 长沙红胖子Qt(长沙创微智科)博文大全:开发技术集合(包含Qt实用技术、树莓派、三维、OpenCV…...
项目研究:使用 LangGraph 构建智能客服代理
概述 本教程展示了如何使用 LangGraph 构建一个智能客服代理。LangGraph 是一个强大的工具,可用于构建复杂的语言模型工作流。该代理可以自动分类用户问题、分析情绪,并根据需要生成回应或升级处理。 背景动机 在当今节奏飞快的商业环境中,…...
