AtCoder ABC周赛2023 11/4 (Sat) D题题解

目录

原题截图:

题目大意:

主要思路:

注意事项(很多人再这个地方掉坑):

代码:


原题截图:

 

题目大意:

给你两个数组(A和B)长度都为n,然你求出一个01元组(设为x,长度为m) 使得 x_{a_i} != x_{b_i}(i<=n)

主要思路:

如果你细细想一想,这题就很简单,我们可以发现,可以用图论的方式解决,将a[i]和b[i]之间连一条无向边,然后染色法(用0和1,边的两边染的颜色要不同),如果有两个颜色再同一点,就有问题,输出No,否则输出Yes。

注意事项(很多人再这个地方掉坑):

  1. 图不一定是连通的(也就是初始化成-1,遍历一下所有点,如果这个点是-1,就以这个点为开头,染色,然后继续遍历点)

代码:

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[200010],b[200010];
vector<int> g[200010];
int color[200010];
int flag;
void dfs(int c, int u)
{
	color[c]=u;
	for(int i=0;i<g[c].size();i++)
	{
		if(color[g[c][i]] == -1)
		{
			dfs(g[c][i],1-u);
		}
		else if(color[g[c][i]] == color[c])
		{
			flag=1;
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>a[i];
		a[i]--;
	}
	for(int i=0;i<m;i++)
	{
		cin>>b[i];
		b[i]--;
	}
	for(int i=0;i<m;i++)
	{
		g[a[i]].push_back(b[i]);
		g[b[i]].push_back(a[i]);
	}
	for(int i=0;i<n;i++)
	{
		color[i]=-1;
	}
	for(int i=0;i<n;i++)
	{
		if(color[i] == -1)
		{
			dfs(i,0);	
		}
	}
	cout<<(flag?"No":"Yes");
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/226965.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

从零开发短视频电商 在AWS SageMaker已创建的模型列表中进行部署

1.导航到 SageMaker 控制台。 2.在 SageMaker 控制台的左侧导航栏中&#xff0c;选择 “模型” 选项。 3.在模型列表中&#xff0c;找到您要部署的模型。选择该模型。 4.点击 “创建端点” 选项或者点击 “创建端点配置” 选项都可以进行部署。 选择创建端点进去后还是会进行…

Axure原型组件库,数据可视化动态元件库(超详细Axure9可视化素材)

专门针对Axure制作的动态图表元件库&#xff0c;帮助产品经理更高效地制作高保真图表原型&#xff0c;是产品经理必备元件工具。现分享完整的组件库&#xff0c;大家一起学习。 每一个动态组件在原型文件中都配有详细介绍&#xff0c;文末可下载完整原型组件包~ 1. 本组件库的…

Appium获取toast方法封装

一、前置说明 toast消失的很快&#xff0c;并且通过uiautomatorviewer也不能获取到它的定位信息&#xff0c;如下图&#xff1a; 二、操作步骤 toast的class name值为android.widget.Toast&#xff0c;虽然toast消失的很快&#xff0c;但是它终究是在Dom结构中出现过&…

如何在Spring Boot中集成RabbitMQ

如何在Spring Boot中集成RabbitMQ 在现代微服务架构中&#xff0c;消息队列&#xff08;如RabbitMQ&#xff09;扮演了关键的角色&#xff0c;它不仅能够提供高效的消息传递机制&#xff0c;还能解耦服务间的通信。本文将介绍如何在Spring Boot项目中集成RabbitMQ&#xff0c;…

华为配置Smart Link负载分担示例

Smart Link基本概念 Smart Link通过两个端口相互配合工作来实现功能。这样的一对端口组成了一个Smart Link组。为了区别一个Smart Link组中的两个端口&#xff0c;我们将其中的一个叫做主端口&#xff0c;另一个叫做从端口。同时我们利用Flush报文、Smart Link实例和控制VLAN等…

Windows故障排除 – 连接WiFi却无法上网

Windows故障排除 – 连接WiFi却无法上网 Windows Troubleshooting - Connecting WiFi but PC Cannot Browse Internet By JacksonML 有个同学买了一台崭新的D品牌游戏本&#xff0c;i7处理器&#xff0c;英伟达RTX系列独立显卡及15寸液晶显示器&#xff0c;可谓功能强大。但是…

0011Java程序设计-ssm药店管理系统微信小程序

文章目录 摘 要目 录系统实现5.2服务端开发环境 编程技术交流、源码分享、模板分享、网课分享 企鹅&#x1f427;裙&#xff1a;776871563 摘 要 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机…

设备状态监测好帮手:无线温振传感器的应用

在现代工业生产中&#xff0c;设备状态监测对于确保设备的正常运行和预防故障至关重要。而无线温振传感器的出现为设备状态监测带来了全新的解决方案。本文将介绍无线温振传感器的工作原理和优势&#xff0c;并探讨其在设备状态监测中的广泛应用。 无线温振传感器是一种能够实时…

电脑系统重装Win10专业版操作教程

用户想给自己的电脑重新安装上Win10专业版系统&#xff0c;但不知道具体的重装步骤。接下来小编将详细介绍Win10系统重新安装的步骤方法&#xff0c;帮助更多的用户完成Win10专业版的重装&#xff0c;重装后用户即可体验到Win10专业版系统带来的丰富功能。 准备工作 1. 一台正常…

论文阅读:LSeg: LANGUAGE-DRIVEN SEMANTIC SEGMENTATION

可以直接bryanyzhu的讲解&#xff1a;CLIP 改进工作串讲&#xff08;上&#xff09;【论文精读42】_哔哩哔哩_bilibili 这里是详细的翻译工作 原文链接 https://arxiv.org/pdf/2201.03546.pdf ICLR 2022 0、ABSTRACT 我们提出了一种新的语言驱动的语义图像分割模型LSeg。…

dockerfile简单实践部署(jenkins,wordpress)

实现部署jenkins的流程 配置java环境&#xff0c;导入jenkins包&#xff0c;运行命令 java -jar jenkins包&#xff0c;这里为了减少进入jenkins的web端安装插件&#xff0c;将插件提前部署到容器内。 制作dockerfile 创建镜像所在的文件夹和Dockerfile文件 mkdir /test cd …

【Flink系列六】Flink里面的状态一致性

状态一致性 有状态的流处理&#xff0c;内部每个算子任务都可以有自己的状态&#xff0c;对于流处理器内部来说&#xff0c;所谓的状态一致性&#xff0c;其实就是我们所说的计算结果要保证准确。一条数据不应该丢失&#xff0c;也不应该重复计算。再遇到有故障时可以恢复状态…

P30 C++智能指针

前言 &#x1f3ac; 个人主页&#xff1a;ChenPi &#x1f43b;推荐专栏1: 《C_ChenPi的博客-CSDN博客》✨✨✨ &#x1f525; 推荐专栏2: 《Linux C应用编程&#xff08;概念类&#xff09;_ChenPi的博客-CSDN博客》✨✨✨ &#x1f6f8;推荐专栏3: ​​​​​​《 链表_Chen…

在Spring Cloud使用Hystrix核心组件,并注册到Eureka注册中心去

其实吧&#xff0c;写Spring Cloud系列&#xff0c;我有时候觉得也挺难受的&#xff0c;因为Spring Cloud的微服务启动都需要一个一个来&#xff0c;并且在IDea中也需要占用比较大的内存&#xff0c;并且我本来可以一篇写完5大核心组件的&#xff0c;但是我却分了三篇&#xff…

QT 重定向qdebug输出到自绘界面

因为在嵌入式中调试qt需要查看输出信息,特意写了一个类用户便捷查看qdebug信息 界面如下: 提供了开始,停止,保存,清空,退出功能,具体代码下文给出 文件如下 #ifndef QDEBUGREDIRECT_H #define QDEBUGREDIRECT_H /**qdebug 重定向类 定向到界面控件*李吉磊 2023.12.7* */#in…

【dig命令查询方法】

dig&#xff08;Domain Information Groper&#xff09;是一个用于查询DNS&#xff08;域名系统&#xff09;的命令行工具&#xff0c;它可以帮助您获取关于域名的各种信息&#xff0c;如IP地址、MX记录、NS记录等。下面是dig的详细使用教程。 基本语法&#xff1a; dig [ser…

【数据库】树形数据组织架构下的封锁并发控制,B树索引并发访问控制,树协议原理及案例分析

数据库并发访问树协议 ​专栏内容&#xff1a; 手写数据库toadb 本专栏主要介绍如何从零开发&#xff0c;开发的步骤&#xff0c;以及开发过程中的涉及的原理&#xff0c;遇到的问题等&#xff0c;让大家能跟上并且可以一起开发&#xff0c;让每个需要的人成为参与者。 本专栏会…

docker基本管理和概念

1、定义&#xff1a;一个开源的应用容器引擎&#xff0c;基于go语言开发&#xff0c;运行在liunx系统中的开源的、轻量级的“虚拟机” docker的容器技术可以在一台主机上轻松的为任何应用创建一个轻量级的、可移植的、自给自足的容器 docker的宿主机是liunx系统&#xff0c;集…

深度学习与逻辑回归模型的融合--TensorFlow多元分类的高级应用

手写数字识别 文章目录 手写数字识别1、线性回归VS逻辑回归Sigmoid函数 2、逻辑回归的基本模型-神经网络模型3、多元分类基本模型4、TensorFlow实战解决手写数字识别问题准备数据集数据集划分 特征数据归一化归一化方法归一化场景 标签数据独热编码One-Hot编码构建模型损失函数…

NLP自然语言处理学习笔记

参考&#xff1a;NLP&#xff08;自然语言处理&#xff09;介绍 - 知乎 (zhihu.com) 一、NLP是什么 自然语言处理( Natural Language Processing, NLP)是计算机科学领域与人工智能领域中的一个重要方向。它研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法。自…