当前位置: 首页 > 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 语言…...

Fastfetch:超越 Neofetch 的系统信息获取新利器

【导语&#xff1a;Fastfetch 作为一款类似 neofetch 的工具&#xff0c;以 C 语言编写&#xff0c;注重性能与可定制性&#xff0c;支持多平台。它在速度、功能、准确性等方面超越竞品&#xff0c;为用户带来全新系统信息获取体验。】多平台适配的系统信息工具Fastfetch 是一款…...

OpenClaw节日应用:GLM-4.7-Flash驱动春节祝福邮件批量定制与发送

OpenClaw节日应用&#xff1a;GLM-4.7-Flash驱动春节祝福邮件批量定制与发送 1. 为什么需要自动化节日邮件&#xff1f; 每年春节前&#xff0c;我都会陷入同样的困境——需要给200多位合作伙伴发送祝福邮件。手动操作意味着&#xff1a;反复复制粘贴内容、检查收件人姓名、调…...

低头编程:颈椎快要崩溃!

长期低头编写代码、调试程序、查看文档&#xff0c;是程序员、IT 从业者等人群颈椎损伤的高发原因。当你专注于电脑屏幕上的代码时&#xff0c;颈椎会不自觉地向前倾斜&#xff0c;颈部后侧肌肉为了支撑头部重量&#xff0c;会持续处于紧绷痉挛状态&#xff0c;时间一长&#x…...

AMP实战:对抗运动先验在物理驱动角色控制中的风格化应用

1. AMP框架如何革新角色动作控制 想象一下你在玩一款开放世界游戏&#xff0c;主角需要从悬崖边缘精准跳到对面平台。传统动画系统可能会直接播放预设的跳跃动画&#xff0c;但物理引擎计算发现距离不够时&#xff0c;就会出现角色悬空滑行的诡异画面。这正是AMP&#xff08;Ad…...

搜索时代的命名战略:如何在亚马逊规避“品牌失语症”

在亚马逊这个由算法与关键词统治的商业世界里&#xff0c;一个名字的恰当与否&#xff0c;直接决定了品牌是“响亮宣言”还是“沉默失语”。许多名字如同《时代》或《财富》杂志&#xff0c;在传统语境中或许优雅&#xff0c;但在需要极致精准的数字货架上&#xff0c;却可能因…...

大麦抢票自动化终极指南:5分钟快速上手教程

大麦抢票自动化终极指南&#xff1a;5分钟快速上手教程 【免费下载链接】ticket-purchase 大麦自动抢票&#xff0c;支持人员、城市、日期场次、价格选择 项目地址: https://gitcode.com/GitHub_Trending/ti/ticket-purchase 您是否曾因热门演唱会门票秒光而遗憾&#x…...

CayenneMQTT库详解:嵌入式设备快速接入MQTT平台

1. CayenneMQTT 库概述 CayenneMQTT 是一个专为物联网设备设计的轻量级 MQTT 客户端库&#xff0c;核心目标是将嵌入式终端&#xff08;如 Arduino、ESP8266、ESP32&#xff09;快速、可靠地接入 Cayenne IoT 平台 的可视化仪表盘。该库并非从零实现 MQTT 协议栈&#xff0c…...

告别音乐平台干扰!铜钟音乐如何让你重拾纯净听歌体验?

告别音乐平台干扰&#xff01;铜钟音乐如何让你重拾纯净听歌体验&#xff1f; 【免费下载链接】tonzhon-music 铜钟 (Tonzhon.com): 免费听歌; 没有直播, 社交, 广告, 干扰; 简洁纯粹, 资源丰富, 体验独特&#xff01;(密码重置功能已回归) 项目地址: https://gitcode.com/Gi…...

实测避坑:用华为Atlas 300I DUO推理卡跑Qwen1.5-14B,性能对比3090和配置踩坑全记录

华为Atlas 300I DUO推理卡实战评测&#xff1a;Qwen1.5-14B部署全流程与性能深度对比 当国产AI加速卡遇上千亿参数大模型&#xff0c;会碰撞出怎样的火花&#xff1f;最近半年&#xff0c;我陆续测试了市面上主流的7款推理加速设备&#xff0c;这次终于轮到华为Atlas 300I DUO这…...

树莓派+SocketCAN实战:手把手教你用CanFestival控制伺服电机(附完整配置文件)

树莓派SocketCAN实战&#xff1a;手把手教你用CanFestival控制伺服电机&#xff08;附完整配置文件&#xff09; 在工业自动化和机器人控制领域&#xff0c;CANopen协议因其高可靠性和实时性成为伺服电机控制的首选方案。本文将带你用树莓派这一低成本硬件平台&#xff0c;结合…...