格子游戏——并查集
Alice和Bob玩了一个古老的游戏:首先画一个 n×n 的点阵(下图 n=3 )。
接着,他们两个轮流在相邻的点之间画上红边和蓝边:

直到围成一个封闭的圈(面积不必为 1)为止,“封圈”的那个人就是赢家。因为棋盘实在是太大了,他们的游戏实在是太长了!他们甚至在游戏中都不知道谁赢得了游戏。
于是请你写一个程序,帮助他们计算他们是否结束了游戏?
输入格式
输入数据第一行为两个整数 n 和 m。n表示点阵的大小,m 表示一共画了 m 条线。
以后 m 行,每行首先有两个数字 (x,y),代表了画线的起点坐标,接着用空格隔开一个字符,假如字符是 D,则是向下连一条边,如果是 R 就是向右连一条边。
输入数据不会有重复的边且保证正确。
输出格式
输出一行:在第几步的时候结束。
假如 m 步之后也没有结束,则输出一行“draw”。
数据范围
1≤n≤200,1≤m≤24000
输入样例:
3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D
输出样例:
4
解析:
当给出(a,b)和(c,d) 时,若在连接这两个点之前,两个点已经连通,此时再添加这条边,就构成了一个“ 封闭的圈 ”。
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
const int N=2e6+10;
map <PII,int> s;
int p[N];
int find(int x)
{if (x!=p[x]) p[x]=find(p[x]);return p[x];
}
signed main()
{int n,m;cin>>n>>m;int cnt=0;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)s[{i,j}]=++cnt;for (int i=1;i<=cnt;i++) p[i]=i;int a,b,x,y;char c;for (int i=1;i<=m;i++){cin>>a>>b>>c;if (c=='D') x=a+1,y=b;else x=a,y=b+1;int l=s[{a,b}],r=s[{x,y}];if (find(l)!=find(r)) p[find(l)]=find(r);else{cout<<i;return 0;}}cout<<"draw";return 0;
}
相关文章:
格子游戏——并查集
Alice和Bob玩了一个古老的游戏:首先画一个 nn 的点阵(下图 n3 )。 接着,他们两个轮流在相邻的点之间画上红边和蓝边: 直到围成一个封闭的圈(面积不必为 1)为止,“封圈”的那个人就是…...
2023最新Python重点知识万字汇总
这是一份来自于 SegmentFault 上的开发者 二十一 总结的 Python 重点。由于总结了太多的东西,所以篇幅有点长,这也是作者"缝缝补补"总结了好久的东西。 **Py2 VS Py3** * print成为了函数,python2是关键字* 不再有unicode对象…...
【STM32】学习笔记(TIM定时器)-江科大
TIM(Timer)定时器 定时器可以对输入的时钟进行计数,并在计数值达到设定值时触发中断 16位计数器、预分频器、自动重装寄存器的时基单元,在72MHz计数时钟下可以实现最大59.65s的定时 不仅具备基本的定时中断功能,而且…...
Parallel Context Windows for Large Language Models
本文是LLM系列文章,针对《Parallel Context Windows for Large Language Models》的翻译。 大语言模型并行上下文窗口 摘要1 引言2 并行上下文窗口3 上下文学习的PCW4 PCW用于QA5 相关工作6 结论和未来工作不足 摘要 当应用于处理长文本时,大型语言模型…...
怎么消除人声保留背景音乐?试试这几种简单方法
消除人声保留背景音乐可以用于许多不同的目的。例如,可以在视频制作中使用,以确保观众能够听到清晰的对话,而不会被其他噪音干扰。此外,它也可以用于音乐制作中,以便更好地混合和控制音频元素。教大家几种简单的提取方…...
积分游戏小程序模板源码
积分游戏小程序模板源码是一款可以帮助用户快速开发小程序的工具,此模板源码包含五个静态页面,分别是首页、任务列表、大转盘、猜拳等五个页面,非常适合进行积分游戏等相关开发。 此模板源码的前端部分非常简单易用,用户可以根据…...
IDEA启动两个Tomcat服务的方式 使用nginx进行反向代理 JMeter测试分布式情况下synchronized锁失效
目录 引出IDEA启动Tomcat两个端口的方式1.编辑配置2.添加新的端口-Dserver.port80833.service里面管理4.启动后进行测试 使用nginx进行反向代理反向代理多个端口运行日志查看启动关闭重启 分布式情况下synchronized失效synchronized锁代码启动tomcat两个端口nginx反向代理JMete…...
Shell 脚本入门
目录 一、Shell是什么 1.1 我们为什么要学习Shell和使用Shell? 1.2 Shell的分类有哪些? 二、Shell脚本入门知识 2.1 Shell文件命名规范 2.2 Shell解析器 2.3 用Shell 编写hello World 三、Shell的四种变量类型 3.1 系统预定义变量 3.2 自定义变…...
管理类联考——逻辑——形式逻辑——汇总篇——知识点突破——性质模态
性质&模态 角度一 角度二 矛盾关系 【对象】(1)所有、有的不;(2)所有不、有的;(3)某个、某个不。 【典例】①所有偶像都是靠颜值的。 ②有的偶像不是靠颜值的。 试分析: (1)如果①为真,试判断②的真假。 (2)如果①为假,试判断②的真假。 (3)①和②是否可…...
无涯教程-Android - ToggleButton函数
ToggleButton将已选中/未选中状态显示为按钮。它基本上是一个带有指示灯的开/关按钮。 Toggle Button ToggleButton属性 以下是与ToggleButton控件相关的重要属性。您可以查看Android官方文档以获取属性的完整列表以及可以在运行时更改这些属性的相关方法。 Sr.No.Attribute…...
unity VS无法进行断点调试
有时候我们的VS无法进行断点调试,报错如下: 原因是:开启了多个项目,vs无法找到调式项目 解决:点击菜单栏--调试----附加unity调试程序 会弹出一个框,然后选择你要调试的项目 即可...
Pandas由入门到精通-组合与合并数据
采集的数据存储后通常会分为多个文件或数据库,如何将这些文件按需拼接,或按键进行连接十分重要。这节将介绍数据索引的复杂操作如分层索引,stack,unstack,seet_index,reset_index等帮助重构数据,数据的拼接如merge,join,concat,combine_first等帮助连接数据,以及数据透视表…...
Unexpected mutation of “xxxx“ prop
原因 是因为子级修改了父级的数据,所以eslint执行的时候报了这个错 修复方式 1 如果是弹窗等组件,可以根据功能进行修改,比如我这块用的 element ui 的 dialog,便可以改成这样 使用 model-value 代替 修复方式 2 新建子组件…...
七、基础篇总结
...
前端面试基础面试题——2
1.什么是json? json可以存在哪几种数据类型?在什么时候用? 2.什么是作用域? 3.http和https分别是什么?区别是什么? 4.介绍一下js的节流与防抖? 5.什么是cookie?cookie的优缺点。 6.js的三种排序方法࿰…...
docker 搭建rknn转换环境
文章目录 下载rknn搭建docker 环境进入镜像并挂载运行代码 下载rknn https://github.com/rockchip-linux/rknn-toolkit2 搭建docker 环境 进入到docker 的文件目录下 docker build -t run:v3 . -f Dockerfile_ubuntu_18_04_for_cp36 进入镜像并挂载 docker run -it -v /ho…...
机器学习:争取被遗忘的权利
随着越来越多的人意识到他们通过他们经常访问的无数应用程序和网站共享了多少个人信息,数据保护和隐私一直在不断讨论。看到您与朋友谈论的产品或您在 Google 上搜索的音乐会迅速作为广告出现在您的社交媒体提要中,这不再那么令人惊讶。这让很多人感到担…...
MATLAB实现AHP层次分析法——以情人节选取礼物为例
问题背景: 情人节来临之际,广大直男(女)同胞在给异性朋友选购礼物时会遇到难题——什么才是礼物好坏最重要的标准?基于层次分析法AHP进行计算,得出最高权重的指标,给出各位朋友选购礼物的一种思…...
flutter使用Chanel与原生通信
在Flutter中,Platform Channel允许Flutter与原生平台(如Android和iOS)之间进行双向通信,以便在Flutter应用程序和原生代码之间传递消息和调用功能。 以下是使用Platform Channel与原生通信的一般步骤: 1. 在Flutter端…...
Kubernetes技术--k8s核心技术Helm
1.引入 我们先回顾一下之前部署一个应用的过程,如部署nginx,实现效果如下所示: -1.编写deployment的yaml文件,然后运行。 -2.使用service中的NodePort对外暴漏端口 -3.为了弥补Nodeport的缺陷,使用ingress实现转发 这样一个应用就部署完了,这一种情况相对于如果你需要部…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...
