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

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 在玩一个游戏。 首先&#xff0c;小 A 写了一个由 0 和 1 组成的序列 S&#xff0c;长度为 N。 然后&#xff0c;小 B 向小 A 提出了 M 个问题。 在每个问题中&#xff0c;小 B 指定两个数 l 和 r&#xff0c;小 A 回答 S[l∼r] 中…...

程序员做副业,AI头条,新赛道

大家好&#xff0c;我是老秦&#xff0c;6年编程&#xff0c;自由职业3年&#xff0c;今天继续更新副业内容。 在当今信息爆炸的时代&#xff0c;副业赚钱已成为许多人增加收入的重要途径。其中&#xff0c;AI头条模式以其独特的优势&#xff0c;吸引了越来越多的写作者加入。…...

Redis: 内存回收

文章目录 一、过期键删除策略1、惰性删除2、定时删除3、定期删除4、Redis的过期键删除策略 二、内存淘汰策略1、设置过期键的内存淘汰策略2、全库键的内存淘汰策略 一、过期键删除策略 1、惰性删除 顾名思义并不是在TTL到期后就立即删除&#xff0c;而是在访问一个key的时候&…...

【刷题篇】回溯算法(三)

文章目录 1、全排列2、子集3、找出所有子集的异或总和再求和4、全排列 II5、电话号码的字母组合6、括号生成 1、全排列 给定一个不含重复数字的数组 nums &#xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 class Solution { public:vector<vector<i…...

pe格式从入门到图形化显示(八)-导入表

文章目录 前言一、什么是Windows PE格式中的导入表&#xff1f;二、解析导入表并显示1.导入表的结构2.解析导入表3.显示导入表 前言 通过分析和解析Windows PE格式&#xff0c;并使用qt进行图形化显示 一、什么是Windows PE格式中的导入表&#xff1f; 在Windows中&#xff0…...

如何将Paddle(Lite)模型转换为TensorFlow(Lite)模型

模型间的相互转换在深度学习应用中很常见&#xff0c;paddlelite和TensorFlowLite是移动端常用的推理框架&#xff0c;有时候需要将模型在两者之间做转换&#xff0c;本文将对转换方法做说明。 环境准备 建议使用TensorFlow2.14&#xff0c;PaddlePaddle 2.6 docker pull te…...

最新Zibll子比主题V7.1版本源码 全新推出开心版

源码下载地址&#xff1a;Zibll子比主题V7.1.zip...

响应式布局(其次)

响应式布局 一.响应式开发二.bootstrap前端开发框架1.原理2.优点3.版本问题4.使用&#xff08;1&#xff09;创建文件夹结构&#xff08;2&#xff09;创建html骨架结构&#xff08;3&#xff09;引入相关样式&#xff08;4&#xff09;书写内容 5.布局容器&#xff08;已经划分…...

arhtas idea plugin 使用手册

arthas idea plugin 使用文档 语雀...

数组算法——查询位置

需求 思路 使用二分查找找到第一个值&#xff0c;以第一个值作为界限&#xff0c;分为左右两个区间在左右两个区间分别使用二分查找找左边的7,&#xff1a;找到中间位置的7之后&#xff0c;将中间位置的7作为结束位置&#xff0c;依次循环查找&#xff0c;知道start>end,返回…...

【解决leecode打不开的问题】使用chrome浏览器和其他浏览器均打不开leecode

问题描述&#xff1a; 能进入leetcode力扣官网但是对某些栏目加载不出来&#xff0c;比如学习栏目能完成加载、题库栏目不能加载。 解决方法一&#xff1a;cookies缓存问题 首先尝试删除浏览器cookie缓存。 因为以下原因&#xff1a; Cookies损坏或过期&#xff1a;有些网站…...

尝试在手机上运行google 最新开源的gpt模型 gemma

Gemma介绍 Gemma简介 Gemma是谷歌于2024年2月21日发布的一系列轻量级、最先进的开放语言模型&#xff0c;使用了与创建Gemini模型相同的研究和技术。由Google DeepMind和Google其他团队共同开发。 Gemma提供两种尺寸的模型权重&#xff1a;2B和7B。每种尺寸都带有经过预训练&a…...

56、巴利亚多利德大学、马德里卡洛斯三世研究所:EEG-Inception-多时间尺度与空间卷积巧妙交叉堆叠,终达SOTA!

本次讲解一下于2020年发表在IEEE TRANSACTIONS ON NEURAL SYSTEMS AND REHABILITATION ENGINEERING上的专门处理EEG信号的EEG-Inception模型&#xff0c;该模型与EEGNet、EEG-ITNet、EEGNex、EEGFBCNet等模型均是专门处理EEG的SOTA。 我看到有很多同学刚入门&#xff0c;不太会…...

ORA-00600: internal error code, arguments: [krbcbp_9]

解决方案 1、清理过期 2、control_file_record_keep_time 修改 恢复时间窗口 RMAN (Recovery Manager) 是 Oracle 数据库的备份和恢复工具。在 RMAN 中&#xff0c;可以使用“恢复窗口”的概念来指定数据库可以恢复到的时间点。这个时间点是基于最近的完整备份或增量备份。 …...

uni-app实现分页--(2)分页加载,首页下拉触底加载更多

业务逻辑如下&#xff1a; api函数升级 定义分页参数类型 组件调用api传参...

前端工程化理解 (2024 面试题)

最好介绍远古世界最好随性一点&#xff0c;不要太刻板 &#xff0c;不然像背书 什么是前端工程化&#xff1f; - 知乎 前端工程化的历史 互联网初期&#xff0c;09 年以前&#xff0c;页面只需要展示一些列表、表格、文章内容以及简单图片即可&#xff0c;其目的是为了传送信…...

10 Php学习:循环

在 PHP 中&#xff0c;提供了下列循环语句&#xff1a; while - 只要指定的条件成立&#xff0c;则循环执行代码块do…while - 首先执行一次代码块&#xff0c;然后在指定的条件成立时重复这个循环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网络、云平台报警优化、灰度升级增强四大亮点简析

近日&#xff0c;ZStack Cloud 5.0.0正式发布&#xff0c;推出了包含Vhost主存储、隔离PVLAN网络、云平台报警优化、灰度升级增强在内的一系列重要功能。云主机管理、物理机运维、密评合规、灾备服务等诸多使用场景和功能模块均有更新&#xff0c;为您带来更完善的平台服务、更…...

商标没有去注册有哪些不好的影响!

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

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

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

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

初学 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的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...