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

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

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

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

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...