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网络、云平台报警优化、灰度升级增强在内的一系列重要功能。云主机管理、物理机运维、密评合规、灾备服务等诸多使用场景和功能模块均有更新,为您带来更完善的平台服务、更…...

商标没有去注册有哪些不好的影响!
有些商家咨询普推知产老杨,商标没有去注册有哪些不好的影响,其实对企业来说还有许多实际不利的影响,有时代价比注册一个商标要大很多。 想的商标名称没去注册商标,如果别人抢注拿下商标注册证,那就会涉及侵权…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...

【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...

【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...