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

格子游戏——并查集

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玩了一个古老的游戏&#xff1a;首先画一个 nn 的点阵&#xff08;下图 n3 &#xff09;。 接着&#xff0c;他们两个轮流在相邻的点之间画上红边和蓝边&#xff1a; 直到围成一个封闭的圈&#xff08;面积不必为 1&#xff09;为止&#xff0c;“封圈”的那个人就是…...

2023最新Python重点知识万字汇总

这是一份来自于 SegmentFault 上的开发者 二十一 总结的 Python 重点。由于总结了太多的东西&#xff0c;所以篇幅有点长&#xff0c;这也是作者"缝缝补补"总结了好久的东西。 **Py2 VS Py3** * print成为了函数&#xff0c;python2是关键字* 不再有unicode对象…...

【STM32】学习笔记(TIM定时器)-江科大

TIM&#xff08;Timer&#xff09;定时器 定时器可以对输入的时钟进行计数&#xff0c;并在计数值达到设定值时触发中断 16位计数器、预分频器、自动重装寄存器的时基单元&#xff0c;在72MHz计数时钟下可以实现最大59.65s的定时 不仅具备基本的定时中断功能&#xff0c;而且…...

Parallel Context Windows for Large Language Models

本文是LLM系列文章&#xff0c;针对《Parallel Context Windows for Large Language Models》的翻译。 大语言模型并行上下文窗口 摘要1 引言2 并行上下文窗口3 上下文学习的PCW4 PCW用于QA5 相关工作6 结论和未来工作不足 摘要 当应用于处理长文本时&#xff0c;大型语言模型…...

怎么消除人声保留背景音乐?试试这几种简单方法

消除人声保留背景音乐可以用于许多不同的目的。例如&#xff0c;可以在视频制作中使用&#xff0c;以确保观众能够听到清晰的对话&#xff0c;而不会被其他噪音干扰。此外&#xff0c;它也可以用于音乐制作中&#xff0c;以便更好地混合和控制音频元素。教大家几种简单的提取方…...

积分游戏小程序模板源码

积分游戏小程序模板源码是一款可以帮助用户快速开发小程序的工具&#xff0c;此模板源码包含五个静态页面&#xff0c;分别是首页、任务列表、大转盘、猜拳等五个页面&#xff0c;非常适合进行积分游戏等相关开发。 此模板源码的前端部分非常简单易用&#xff0c;用户可以根据…...

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&#xff1f; 1.2 Shell的分类有哪些&#xff1f; 二、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无法进行断点调试&#xff0c;报错如下&#xff1a; 原因是&#xff1a;开启了多个项目&#xff0c;vs无法找到调式项目 解决&#xff1a;点击菜单栏--调试----附加unity调试程序 会弹出一个框&#xff0c;然后选择你要调试的项目 即可...

Pandas由入门到精通-组合与合并数据

采集的数据存储后通常会分为多个文件或数据库,如何将这些文件按需拼接,或按键进行连接十分重要。这节将介绍数据索引的复杂操作如分层索引,stack,unstack,seet_index,reset_index等帮助重构数据,数据的拼接如merge,join,concat,combine_first等帮助连接数据,以及数据透视表…...

Unexpected mutation of “xxxx“ prop

原因 是因为子级修改了父级的数据&#xff0c;所以eslint执行的时候报了这个错 修复方式 1 如果是弹窗等组件&#xff0c;可以根据功能进行修改&#xff0c;比如我这块用的 element ui 的 dialog&#xff0c;便可以改成这样 使用 model-value 代替 修复方式 2 新建子组件…...

七、基础篇总结

...

前端面试基础面试题——2

1.什么是json? json可以存在哪几种数据类型?在什么时候用&#xff1f; 2.什么是作用域&#xff1f; 3.http和https分别是什么&#xff1f;区别是什么&#xff1f; 4.介绍一下js的节流与防抖? 5.什么是cookie&#xff1f;cookie的优缺点。 6.js的三种排序方法&#xff0…...

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…...

机器学习:争取被遗忘的权利

随着越来越多的人意识到他们通过他们经常访问的无数应用程序和网站共享了多少个人信息&#xff0c;数据保护和隐私一直在不断讨论。看到您与朋友谈论的产品或您在 Google 上搜索的音乐会迅速作为广告出现在您的社交媒体提要中&#xff0c;这不再那么令人惊讶。这让很多人感到担…...

MATLAB实现AHP层次分析法——以情人节选取礼物为例

问题背景&#xff1a; 情人节来临之际&#xff0c;广大直男&#xff08;女&#xff09;同胞在给异性朋友选购礼物时会遇到难题——什么才是礼物好坏最重要的标准&#xff1f;基于层次分析法AHP进行计算&#xff0c;得出最高权重的指标&#xff0c;给出各位朋友选购礼物的一种思…...

flutter使用Chanel与原生通信

在Flutter中&#xff0c;Platform Channel允许Flutter与原生平台&#xff08;如Android和iOS&#xff09;之间进行双向通信&#xff0c;以便在Flutter应用程序和原生代码之间传递消息和调用功能。 以下是使用Platform Channel与原生通信的一般步骤&#xff1a; 1. 在Flutter端…...

Kubernetes技术--k8s核心技术Helm

1.引入 我们先回顾一下之前部署一个应用的过程,如部署nginx,实现效果如下所示: -1.编写deployment的yaml文件,然后运行。 -2.使用service中的NodePort对外暴漏端口 -3.为了弥补Nodeport的缺陷,使用ingress实现转发 这样一个应用就部署完了,这一种情况相对于如果你需要部…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...