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

程序自动分析——并查集+离散化

在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本:假设 x1,x2,x3,… 代表程序中出现的变量,给定 n 个形如 xi=xj 或 xi≠xj 的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。
例如,一个问题中的约束条件为:x1=x2,x2=x3,x3=x4,x1≠x4,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。
现在给出一些约束满足问题,请分别对它们进行判定。

输入格式
输入文件的第 1 行包含 1 个正整数 t,表示需要判定的问题个数,注意这些问题之间是相互独立的。
对于每个问题,包含若干行:第 1 行包含 1 个正整数 n,表示该问题中需要被满足的约束条件个数。
接下来 n 行,每行包括 3 个整数 i,j,e,描述 1 个相等/不等的约束条件,相邻整数之间用单个空格隔开。若 e=1,则该约束条件为 xi=xj;若 e=0,则该约束条件为 xi≠xj。

输出格式
输出文件包括 t 行。
输出文件的第 k 行输出一个字符串 YES 或者 NO,YES 表示输入中的第 k 个问题判定为可以被满足,NO 表示不可被满足。

数据范围
1≤n≤105, 1≤i,j≤109

输入样例:
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

输出样例:
NO
YES

解析:

每个问题给的条件是相互独立的,也就是和顺序无关,可先进行“e=1” ,再进行“e=2”。

当进行“e=1”时,是并查集的合并;

当进行“e=2”时,也就是相当于变相的并查集查询。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+10;
int p[N];
map <int,int> k;
int cnt;
int get(int x)
{if (k.count(x)==0) k[x]=++cnt;        //离散化return k[x];
}
int find(int x)
{if (x!=p[x]) p[x]=find(p[x]);return p[x];
}
struct node
{int a,b,e;
}s[N];
bool cmp(node x,node y)
{return x.e>y.e;
}
signed main()
{int t;scanf("%lld",&t);                          //读入的数据较多,用scanf读入while (t--){int n;scanf("%lld",&n);for (int i=1;i<=2e6;i++) p[i]=i;k.clear();                            //记得要清空哦!cnt=0;for (int i=0;i<n;i++) {int x,y;scanf("%lld%lld%lld",&x,&y,&s[i].e);    s[i].a=get(x);                            //离散化,map即可s[i].b=get(y); }bool falg=0;for (int i=0;i<n;i++)if (s[i].e==1){if (find(s[i].a)!=find(s[i].b)) p[find(s[i].a)]=find(s[i].b);}for (int i=0;i<n;i++)if (s[i].e==0){if (find(s[i].a)==find(s[i].b)) {falg=1;break;}}if (!falg) puts("YES");else puts("NO");}return 0;
}

相关文章:

程序自动分析——并查集+离散化

在实现程序自动分析的过程中&#xff0c;常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本&#xff1a;假设 x1,x2,x3,… 代表程序中出现的变量&#xff0c;给定 n 个形如 xixj 或 xi≠xj 的变量相等/不等的约束条件&#xff0c;请判定是否可以分别为…...

Qt 获取文件图标、类型 QFileIconProvider

Qt中获取系统图标、类型是通过QFileIconProvider来实现的&#xff0c;具体如下&#xff1a; 一、Qt获取系统文件图标1、获取文件夹图标QFileIconProvider icon_provider;QIcon icon icon_provider.icon(QFileIconProvider::Folder);2、获取指定文件图标QFileInfo file_info(n…...

TopicExchange主题交换机

目录 一、简介 二、代码展示 父pom文件 pom文件 配置文件 config 生产者 消费者 测试 结果 一、简介 主题交换机&#xff0c;这个交换机其实跟直连交换机流程差不多&#xff0c;但是它的特点就是在它的路由键和绑定键之间是有规则的。 简单地介绍下规则&#xff1…...

A Survey on Large Language Models for Recommendation

本文是LLM系列的文章&#xff0c;针对《A Survey on Large Language Models for Recommendation》的翻译。 大模型用于推荐的综述 摘要1 引言2 建模范式和分类3 判别式LLM用于推荐4 生成式LLM用于推荐5 发现6 结论 摘要 大型语言模型&#xff08;LLM&#xff09;作为自然语言…...

Springboot 入门指南:控制反转和依赖注入的含义和实现方式

目录 一、什么是控制反转&#xff08;IoC&#xff09;&#xff1f; 二、什么是依赖注入&#xff08;DI&#xff09;&#xff1f; 三、如何在 springboot 中使用 IoC 和 DI&#xff1f; 总结 一、什么是控制反转&#xff08;IoC&#xff09;&#xff1f; 控制反转&#xff…...

使用Tampermonkey(篡改猴)向页面注入js脚本

一、Tampermonkey 简单介绍 Tampermonkey是一款浏览器插件&#xff0c;适用于Chrome、Microsoft Edge、Safari、Opera Next 和 Firefox。他允许我们自定义javascript给指定网页添加功能&#xff0c;或修改现有功能。也可以用来辅助调试&#xff0c;或去除网页广告等。 官网地…...

软考高级系统架构设计师系列之:论文典型试题写作要点和写作素材总结系列文章二

软考高级系统架构设计师系列之:论文典型试题写作要点和写作素材总结系列文章二 一、论基于DSSA的软件架构设计与应用1.论文题目2.写作要点和写作素材二、论信息系统建模方法1.论文题目2.写作要点和写作素材三、论高可靠性系统中软件容错技术的应用1.论文题目2.写作要点和写作素…...

【Linux】如何在linux系统重启或启动时执行命令或脚本(也支持docker容器内部)

如何在linux系统重启或启动时执行命令或脚本&#xff08;也支持docker容器内部&#xff09; 第一种&#xff1a;使用 systemd 服务单元在重启或启动时运行命令或脚本第二种&#xff1a;使用 /etc/rc.d/rc.local 文件在重启或启动时运行脚本或命令第三种&#xff1a;使用 cronta…...

医疗中心管理环境温湿度,这样操作就对了!

随着医疗技术的不断发展&#xff0c;越来越多的医疗设备对于稳定的工作环境要求越来越高&#xff0c;而环境温湿度是影响这些设备性能和可靠性的关键因素之一。 为了确保医疗设备的正常运行和患者的安全&#xff0c;医疗机构越来越倾向于采用精密空调监控系统来维护设备的稳定性…...

嵌入式系统存储体系

一、存储系统概述 主要分为三种&#xff1a;高速缓存&#xff08;cache&#xff09;、主存和外存。 二、高速缓存Cache 高速缓冲存储器中存放的是当前使用得最多得程序代码和数据&#xff0c;即主存中部分内容的副本&#xff0c;其本身无自己的地址空间。在嵌入式系统中Cac…...

【Java架构-版本控制】-Gitlab安装

本文摘要 Git作为版本控制工具&#xff0c;使用非常广泛&#xff0c;在此咱们由浅入深&#xff0c;分三篇文章&#xff08;Git基础、Git进阶、Gitlab搭那家&#xff09;来深入学习Git 文章目录 本文摘要1. docker接取镜像2. docker启动镜像3. 配置启动端口和ssh端口4. 获取初始…...

关于disriminative 和 generative这两种模型

但是&#xff0c;其实&#xff0c;根据李宏毅老师讲到的&#xff0c;generative model是做了一些假设的&#xff0c;比如&#xff0c;如果使用Naive Bayes的话&#xff0c;不同特征x1,x2...之间相互独立的话&#xff0c;其实是很容易出现较大的偏差的&#xff0c;因为不同特征变…...

关于Java中@Transient主键的作用的一些介绍

Transient主下面是关于Transient主键的使用方法、代码案例以及与transient关键字的区别&#xff0c;以及一些实用场景的详细介绍。 1. Transient主键的作用 在实体类中&#xff0c;通常需要将某些字段标记为主键&#xff0c;并将其映射到数据库中的主键字段。但是&#xff0c…...

死信队列理解与使用

一、简介 在rabbitMQ中常用的交换机有三种&#xff0c;直连交换机、广播交换机、主题交换机&#xff1b; 直连交换机中队列与交换机需要约定好routingKey去进行绑定&#xff1b; 广播交换机并不需要routingKey绑定,只需队列与交换机绑定即可&#xff1b; 主题交换机最大的特…...

tomcat 启动 java war 包

要启动一个Java WAR包的Tomcat服务器&#xff0c;您可以按照以下步骤操作&#xff1a; 确保您已经安装了Java Development Kit (JDK)。您可以在Oracle官方网站上下载并安装适合您操作系统的JDK版本。 下载和安装Tomcat服务器。您可以访问Apache Tomcat官方网站&#xff08;htt…...

leetcode分类刷题:滑动窗口(三、两个序列+窗口定长类型)

1、通过对滑动窗口前两个题型的总结&#xff0c;我们几乎已经习惯在给定的一个序列里使用滑动窗口的模板解题了&#xff0c;本次对应的“三、两个序列窗口定长类型”&#xff0c;也是考察连续子数组、连续子串问题&#xff0c;只不过这次会给定两个序列&#xff0c;判断短序列在…...

一个简单的web应用程序的创建

一个简单的web应用程序的创建 1、数据库设计与创建1.1、数据库系统1.2、Navicat Premium1.3、Power Designer2、使用maven创建SpringBoot项目2.1、配置maven2.2、安装idea2.3、使用idea创建maven项目2.4、根据需要配置pom.xml文件、配置项目启动相关的文件2.5、写SpringBoot项目…...

分类行为的排斥作用

( A, B )---3*30*2---( 1, 0 )( 0, 1 ) 让网络的输入只有3个节点&#xff0c;AB训练集各由5张二值化的图片组成&#xff0c;让A中有2个1&#xff0c;B中有1个1&#xff0c;且不重合&#xff0c;排列组合&#xff0c;统计迭代次数并排序。 其中有6组数据 构造平均列A 构造平均…...

表现层消息一致性处理

设计表现层返回结果的模型类&#xff0c; 用于后端与前端进行数据格式统一&#xff0c;也称为前后端数据协议 Data public class R {private Boolean flag;private Object data;private String msg;public R(){}public R(Boolean flag){this.flag flag;}public R(Boolean fla…...

【C语言进阶(8)】自定义数据类型1:结构体

文章目录 前言Ⅰ 结构体的声明和定义⒈结构体声明⒉结构体定义⒊特殊的声明 Ⅱ 结构体的自引用Ⅲ 结构体初始化Ⅳ 访问结构体成员Ⅴ 结构体内存对齐⒈结构体内存对齐规则⒉分析结构体大小⒊嵌套结构体内存大小⒋内存对齐存在的原因 Ⅵ 修改默认对齐数Ⅶ 结构体传参 前言 C 语言…...

如何在2024年继续运行Flash游戏?终极CefFlashBrowser解决方案指南

如何在2024年继续运行Flash游戏&#xff1f;终极CefFlashBrowser解决方案指南 【免费下载链接】CefFlashBrowser Flash浏览器 / Flash Browser 项目地址: https://gitcode.com/gh_mirrors/ce/CefFlashBrowser 随着现代浏览器全面停止对Flash的支持&#xff0c;无数经典F…...

遥感数据处理避坑指南:实测光谱如何用Matlab匹配卫星波段(以GF-6为例)

遥感数据处理避坑指南&#xff1a;实测光谱如何用Matlab匹配卫星波段&#xff08;以GF-6为例&#xff09; 当你在野外辛苦采集的ASD高光谱数据与卫星影像比对时&#xff0c;是否遇到过这样的困惑&#xff1a;明明地面测量值看起来合理&#xff0c;但和卫星数据对比时却总存在难…...

探索时序并行门控网络TPGN:RNN的崭新继任者

一种RNN的新继任者—时序并行门控网络TPGN&#xff0c;用于时间序列预测。 作为RNN的新继任者。 PGN通过设计的历史信息提取&#xff08;HIE&#xff09;层直接从以前的时间步捕获信息&#xff0c;并利用门通机制选择并将其与当前时间步信息融合。 这将信息传播路径减少到0(1)&…...

动态规划 -- 最长公共子序列

最长公共子序列的结构设序列 X{x1,x2,…,x m} 和 Y{y1,y2,…,y n} 的最长公共子序列为 Z{z1,z2,…,z k}&#xff0c;则有以下结论&#xff1a;若 x my n&#xff0c;则 z kx my n&#xff0c;且 Z k−1&#xff08;即 Z 去掉最后一个元素 z k 后的子序列&#xff09;是 X m−1&…...

OpCore Simplify:自动化OpenCore EFI配置的革命性工具

OpCore Simplify&#xff1a;自动化OpenCore EFI配置的革命性工具 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify OpCore Simplify是一款专为Hackinto…...

Qwen3-VL-WEBUI效果实测:对比其他模型,看看优势在哪里

Qwen3-VL-WEBUI效果实测&#xff1a;对比其他模型&#xff0c;看看优势在哪里 1. 引言&#xff1a;当AI不仅能“看”&#xff0c;还能“做” 想象一下&#xff0c;你给AI看一张软件界面的截图&#xff0c;它不仅能告诉你界面上有什么&#xff0c;还能一步步指导你如何操作&am…...

【自然语言处理】BERTopic:解决文本主题分析的5个创新方案

#【自然语言处理】BERTopic&#xff1a;解决文本主题分析的5个创新方案 【免费下载链接】BERTopic Leveraging BERT and c-TF-IDF to create easily interpretable topics. 项目地址: https://gitcode.com/gh_mirrors/be/BERTopic 在信息爆炸的时代&#xff0c;如何从海…...

企业级图片批量处理方案:InstructPix2Pix在电商修图中的落地实践

企业级图片批量处理方案&#xff1a;InstructPix2Pix在电商修图中的落地实践 1. 引言&#xff1a;电商修图的效率困局 想象一下&#xff0c;一家中型电商公司&#xff0c;每天要上新几百个商品。每个商品都需要一组高质量的主图、细节图、场景图。设计师团队忙得焦头烂额&…...

大学物理(上)-期末实战解析(5)——刚体力学核心:从转动惯量到角动量守恒的解题秘籍

1. 刚体力学入门&#xff1a;为什么转动惯量是解题钥匙 刚体力学是大学物理中最让人头疼的章节之一&#xff0c;尤其是当题目里出现"转动惯量"这个名词时&#xff0c;很多同学就开始手心冒汗。记得我第一次做这类题目时&#xff0c;盯着那个积分符号看了半小时愣是没…...

避坑指南:ThingsBoard部件开发中5个常见错误与优化方案(附跑马灯Demo代码)

ThingsBoard部件开发实战&#xff1a;5个高频踩坑点与性能优化技巧&#xff08;含跑马灯完整实现&#xff09; 最近在技术社区看到不少开发者讨论ThingsBoard部件开发中的"玄学问题"——明明按照文档操作却出现各种诡异现象。作为经历过完整产品开发周期的技术负责人…...