239. 奇偶游戏(带权值并查集,邻域并查集,《算法竞赛进阶指南》)
239. 奇偶游戏 - AcWing题库
小 A 和小 B 在玩一个游戏。
首先,小 A 写了一个由 0 和 1 组成的序列 S,长度为 N。
然后,小 B 向小 A 提出了 M 个问题。
在每个问题中,小 B 指定两个数 l 和 r,小 A 回答 S[l∼r] 中有奇数个 1 还是偶数个 1。
机智的小 B 发现小 A 有可能在撒谎。
例如,小 A 曾经回答过 S[1∼3]中有奇数个 1,S[4∼6]中有偶数个 1,现在又回答 S[1∼6] 中有偶数个 1,显然这是自相矛盾的。
请你帮助小 B 检查这 M 个答案,并指出在至少多少个回答之后可以确定小 A 一定在撒谎。
即求出一个最小的 k,使得 01 序列 S 满足第 1∼k 个回答,但不满足第 1∼k+1 个回答。
输入格式
第一行包含一个整数 N,表示 0101 序列长度。
第二行包含一个整数 M,表示问题数量。
接下来 M 行,每行包含一组问答:两个整数 l 和 r,以及回答 even 或 odd,用以描述 S[l∼r] 中有偶数个 1 还是奇数个 1。
输出格式
输出一个整数 k,表示 01 序列满足第 1∼k 个回答,但不满足第 1∼k+1 个回答,如果 01 序列满足所有回答,则输出问题总数量。
数据范围
N≤109,M≤5000
输入样例:
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
输出样例:
3
解析:
带权值并查集:
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int INF = 0x3f3f3f3f, mod = 1e9;
const int N = 5e3 + 10;
int n,m;
int f[N],d[N];
unordered_map<int,int>mp;int get(int a){if(!mp.count(a))mp[a]=++n;return mp[a];
}int find(int a){if(f[a]!=a){int t=find(f[a]);d[a]^=d[f[a]];f[a]=t;}return f[a];
}int main(){cin>>n>>m;n=0;int ans=m;for(int i=1;i<N;i++)f[i]=i;for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);a=get(a-1),b=get(b);string s;cin>>s;int t=0;if(s=="odd")t=1;int pa=find(a),pb=find(b);if(pa==pb){if(d[a]^d[b]!=t){ans=i-1;break;}}else{f[pa]=pb;d[pa]=d[a]^d[b]^t;}}// cout<<"_______";cout<<ans<<endl;return 0;
}
邻域并查集:
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int INF = 0x3f3f3f3f, mod = 1e9;
const int N = 4e4 + 10,M=(N-5)/2;
int n,m;
int f[N];
unordered_map<int,int>mp;int get(int a){if(!mp.count(a))mp[a]=++n;return mp[a];
}int find(int a){if(f[a]!=a)f[a]=find(f[a]);return f[a];
}int main(){cin>>n>>m;n=0;for(int i=0;i<N;i++){f[i]=i;}int ret=m;for(int i=1;i<=m;i++){int a,b;string s;scanf("%d%d",&a,&b);cin>>s;a=get(a-1),b=get(b);if(s=="odd"){if(find(a)==find(b)){ret=i-1;break;}f[find(a+M)]=find(b);f[find(b+M)]=find(a);}else{if(find(a+M)==find(b)){ret=i-1;break;}f[find(a)]=find(b);f[find(a+M)]=find(b+M);}}cout<<ret<<endl;return 0;
}
相关文章:
239. 奇偶游戏(带权值并查集,邻域并查集,《算法竞赛进阶指南》)
239. 奇偶游戏 - AcWing题库 小 A 和小 B 在玩一个游戏。 首先,小 A 写了一个由 0 和 1 组成的序列 S,长度为 N。 然后,小 B 向小 A 提出了 M 个问题。 在每个问题中,小 B 指定两个数 l 和 r,小 A 回答 S[l∼r] 中…...
程序员做副业,AI头条,新赛道
大家好,我是老秦,6年编程,自由职业3年,今天继续更新副业内容。 在当今信息爆炸的时代,副业赚钱已成为许多人增加收入的重要途径。其中,AI头条模式以其独特的优势,吸引了越来越多的写作者加入。…...
Redis: 内存回收
文章目录 一、过期键删除策略1、惰性删除2、定时删除3、定期删除4、Redis的过期键删除策略 二、内存淘汰策略1、设置过期键的内存淘汰策略2、全库键的内存淘汰策略 一、过期键删除策略 1、惰性删除 顾名思义并不是在TTL到期后就立即删除,而是在访问一个key的时候&…...
【刷题篇】回溯算法(三)
文章目录 1、全排列2、子集3、找出所有子集的异或总和再求和4、全排列 II5、电话号码的字母组合6、括号生成 1、全排列 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 class Solution { public:vector<vector<i…...
pe格式从入门到图形化显示(八)-导入表
文章目录 前言一、什么是Windows PE格式中的导入表?二、解析导入表并显示1.导入表的结构2.解析导入表3.显示导入表 前言 通过分析和解析Windows PE格式,并使用qt进行图形化显示 一、什么是Windows PE格式中的导入表? 在Windows中࿰…...
如何将Paddle(Lite)模型转换为TensorFlow(Lite)模型
模型间的相互转换在深度学习应用中很常见,paddlelite和TensorFlowLite是移动端常用的推理框架,有时候需要将模型在两者之间做转换,本文将对转换方法做说明。 环境准备 建议使用TensorFlow2.14,PaddlePaddle 2.6 docker pull te…...
最新Zibll子比主题V7.1版本源码 全新推出开心版
源码下载地址:Zibll子比主题V7.1.zip...
响应式布局(其次)
响应式布局 一.响应式开发二.bootstrap前端开发框架1.原理2.优点3.版本问题4.使用(1)创建文件夹结构(2)创建html骨架结构(3)引入相关样式(4)书写内容 5.布局容器(已经划分…...
arhtas idea plugin 使用手册
arthas idea plugin 使用文档 语雀...
数组算法——查询位置
需求 思路 使用二分查找找到第一个值,以第一个值作为界限,分为左右两个区间在左右两个区间分别使用二分查找找左边的7,:找到中间位置的7之后,将中间位置的7作为结束位置,依次循环查找,知道start>end,返回…...
【解决leecode打不开的问题】使用chrome浏览器和其他浏览器均打不开leecode
问题描述: 能进入leetcode力扣官网但是对某些栏目加载不出来,比如学习栏目能完成加载、题库栏目不能加载。 解决方法一:cookies缓存问题 首先尝试删除浏览器cookie缓存。 因为以下原因: Cookies损坏或过期:有些网站…...
尝试在手机上运行google 最新开源的gpt模型 gemma
Gemma介绍 Gemma简介 Gemma是谷歌于2024年2月21日发布的一系列轻量级、最先进的开放语言模型,使用了与创建Gemini模型相同的研究和技术。由Google DeepMind和Google其他团队共同开发。 Gemma提供两种尺寸的模型权重:2B和7B。每种尺寸都带有经过预训练&a…...
56、巴利亚多利德大学、马德里卡洛斯三世研究所:EEG-Inception-多时间尺度与空间卷积巧妙交叉堆叠,终达SOTA!
本次讲解一下于2020年发表在IEEE TRANSACTIONS ON NEURAL SYSTEMS AND REHABILITATION ENGINEERING上的专门处理EEG信号的EEG-Inception模型,该模型与EEGNet、EEG-ITNet、EEGNex、EEGFBCNet等模型均是专门处理EEG的SOTA。 我看到有很多同学刚入门,不太会…...
ORA-00600: internal error code, arguments: [krbcbp_9]
解决方案 1、清理过期 2、control_file_record_keep_time 修改 恢复时间窗口 RMAN (Recovery Manager) 是 Oracle 数据库的备份和恢复工具。在 RMAN 中,可以使用“恢复窗口”的概念来指定数据库可以恢复到的时间点。这个时间点是基于最近的完整备份或增量备份。 …...
uni-app实现分页--(2)分页加载,首页下拉触底加载更多
业务逻辑如下: api函数升级 定义分页参数类型 组件调用api传参...
前端工程化理解 (2024 面试题)
最好介绍远古世界最好随性一点,不要太刻板 ,不然像背书 什么是前端工程化? - 知乎 前端工程化的历史 互联网初期,09 年以前,页面只需要展示一些列表、表格、文章内容以及简单图片即可,其目的是为了传送信…...
10 Php学习:循环
在 PHP 中,提供了下列循环语句: while - 只要指定的条件成立,则循环执行代码块do…while - 首先执行一次代码块,然后在指定的条件成立时重复这个循环for - 循环执行代码块指定的次数foreach - 根据数组中每个元素来循环代码块 当…...
FreeSWITCH 1.10.10 简单图形化界面17 - ubuntu22.04或者debian12 安装FreeSWITCH
FreeSWITCH 1.10.10 简单图形化界面17 - ubuntu22.04或者debian12 安装FreeSWITCH 界面预览00、先看使用手册0、安装操作系统1、下载脚本2、开始安装3、登录网页FreeSWITCH界面安装参考:https://blog.csdn.net/jia198810/article/details/132479324 界面预览 http://myfs.f3…...
ZStack Cloud 5.0.0正式发布——Vhost主存储、隔离PVLAN网络、云平台报警优化、灰度升级增强四大亮点简析
近日,ZStack Cloud 5.0.0正式发布,推出了包含Vhost主存储、隔离PVLAN网络、云平台报警优化、灰度升级增强在内的一系列重要功能。云主机管理、物理机运维、密评合规、灾备服务等诸多使用场景和功能模块均有更新,为您带来更完善的平台服务、更…...
商标没有去注册有哪些不好的影响!
有些商家咨询普推知产老杨,商标没有去注册有哪些不好的影响,其实对企业来说还有许多实际不利的影响,有时代价比注册一个商标要大很多。 想的商标名称没去注册商标,如果别人抢注拿下商标注册证,那就会涉及侵权…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
Python的__call__ 方法
在 Python 中,__call__ 是一个特殊的魔术方法(magic method),它允许一个类的实例像函数一样被调用。当你在一个对象后面加上 () 并执行时(例如 obj()),Python 会自动调用该对象的 __call__ 方法…...
