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

AcWing 1250. 格子游戏(并查集)

题目链接

活动 - AcWing本课程系统讲解常用算法与数据结构的应用方式与技巧。icon-default.png?t=N7T8https://www.acwing.com/problem/content/1252/

题解

当两个点已经是在同一个连通块中,再连一条边,就围成一个封闭的圈。一般用x * n + y的形式将(x, y)变成一维。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 40010;int n, m;
int p[N];int get(int x, int y)
{return x * n + y;
}int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{cin >> n >> m;for (int i = 0; i < n * n; i++) p[i] = i;int res = 0;for (int i = 1; i <= m; i++){int x, y;char d;cin >> x >> y >> d;x--, y--;int a = get(x, y);int b;if (d == 'D') b = get(x + 1, y);else b = get(x, y + 1);int pa = find(a), pb = find(b);if (pa == pb){res = i;break;}p[pa] = pb;}if (!res) puts("draw");else cout << res << endl;return 0;
}

参考资料

  1. AcWing算法提高课

相关文章:

AcWing 1250. 格子游戏(并查集)

题目链接 活动 - AcWing本课程系统讲解常用算法与数据结构的应用方式与技巧。https://www.acwing.com/problem/content/1252/ 题解 当两个点已经是在同一个连通块中&#xff0c;再连一条边&#xff0c;就围成一个封闭的圈。一般用x * n y的形式将&#xff08;x, y&#xff0…...

CSS对文本的简单修饰

CSS格式&#xff1a; 格式一&#xff1a;在head中的style标签范围内。 < style> 在style内的只写名字不写 &#xff1a; < > 选择器 { 属性的名称 &#xff1a; 样式&#xff1b; 属性的名称&#xff1a;样式&#xff1b; } < style> style中的注释用/* *…...

C++17中if和switch语句的新特性

1.从C17开始&#xff0c;if语句允许在条件表达式里添加一条初始化语句。当仅在if语句范围内需要变量时&#xff0c;使用这种形式的if语句。在if语句的条件表达式里定义的变量将在整个if语句中有效&#xff0c;包括else部分。 std::mutex mx; bool shared_flag true; // guard…...

极坐标下的牛拉法潮流计算57节点MATLAB程序

微❤关注“电气仔推送”获得资料&#xff08;专享优惠&#xff09; 潮流计算&#xff1a; 潮流计算是根据给定的电网结构、参数和发电机、负荷等元件的运行条件&#xff0c;确定电力系统各部分稳态运行状态参数的计算。通常给定的运行条件有系统中各电源和负荷点的功率、枢纽…...

软件设计师——计算机网络(三)

&#x1f4d1;前言 本文主要是【计算机网络】——软件设计师——计算机网络的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是听风与他&#x1f947; ☁️博客首页&#xff1a;CSDN主页听风与他 &#x1…...

【ArkTS】循环控制与List的使用

ArkTS如何进行循环渲染 现有数据如下 class Item{name:stringimage:Resourceprice:numberdicount:numberconstructor(name:string,image:Resource,price:number,dicount?:number) {this.name namethis.image imagethis.price pricethis.dicount dicount} }private items…...

条款3:尽量使用const

文章目录 const指针和函数声明const修饰指针const修饰函数const修饰容器const应用在函数中 const限定成员函数避免const重载的代码重复总结 const指针和函数声明 const修饰指针 char greeting[] "Hello"; char* p greeting; // non-const 指针,// non-const 数据…...

Chromadb词向量数据库总结

简介 Chroma 词向量数据库是一个用于自然语言处理&#xff08;NLP&#xff09;和机器学习的工具&#xff0c;它主要用于词嵌入&#xff08;word embeddings&#xff09;。词向量是将单词转换为向量表示的技术&#xff0c;可以捕获单词之间的语义和语法关系&#xff0c;使得计算…...

Gin之GORM 操作数据库(MySQL)

GORM 简单介绍 GORM 是 Golang 的一个 orm 框架。简单说&#xff0c;ORM 就是通过实例对象的语法&#xff0c;完成关系型数据库的操作的技术&#xff0c;是"对象-关系映射"&#xff08;Object/Relational Mapping&#xff09; 的缩写。使用 ORM框架可以让我们更方便…...

二十七、读写文件

二十七、读写文件 27.1 文件类QFile #include <QCoreApplication>#include<QFile> #include<QDebug>int main(int argc, char *argv[]) {QCoreApplication a(argc, argv);QFile file("D:/main.txt");if(!file.open(QIODevice::WriteOnly | QIODe…...

flutter 代码混淆

Flutter 应用混淆&#xff1a; Flutter 应用的混淆非常简单&#xff0c;只需要在构建 release 版应用时结合使用 --obfuscate 和 --split-debug-info 这两个参数即可。 –obfuscate --split-debug-info 用来指定输出调试文件的位置&#xff0c;该命令会生成一个符号映射表。目前…...

05 Vue中常用的指令

概述 All Vue-based directives start with a v-* prefix as a Vue-specific attribute. 所有基于 Vue 的指令都以 v-* 前缀作为 Vue 特有的属性。 v-text The v-text directive has the same reactivity as with interpolation. Interpolation with {{ }} is more perform…...

Mr. Cappuccino的第67杯咖啡——MacOS通过PD安装Win11

MacOS通过PD安装Win11 下载ParallelsDesktop安装ParallelsDesktop激活ParallelsDesktop下载Windows11安装Windows11激活Windows11 下载ParallelsDesktop ParallelsDesktop下载地址 安装ParallelsDesktop 关闭上面的窗口&#xff0c;继续操作 激活ParallelsDesktop 关闭上面的…...

【云原生kubernets】Service 的功能与应用

一、Service介绍 在kubernetes中&#xff0c;pod是应用程序的载体&#xff0c;我们可以通过pod的ip来访问应用程序&#xff0c;但是pod的ip地址不是固定的&#xff0c;这也就意味着不方便直接采用pod的ip对服务进行访问。为了解决这个问题&#xff0c;kubernetes提供了Service资…...

docker安装Prometheus

docker安装Prometheus Docker搭建Prometheus监控系统 环境准备(这里的环境和版本是经过测试没有问题,并不是必须这个版本) 主机名IP配置系统说明localhost随意2核4gCentOS7或者Ubuntu20.0.4docker版本23.0.1或者24.0.5,docker-compose版本1.29 安装Docker Ubuntu20.0.4版本…...

了解 Flutter 3.16 功能更新

作者 / Kevin Chisholm 我们在季度 Flutter 稳定版发布会上带来了 Flutter 3.16&#xff0c;此版本包含诸多更新: Material 3 成为新的默认主题、为 Android 带来 Impeller 的预览版、允许添加适用于 DevTools 的扩展程序等等&#xff0c;以及同步推出 Flutter 休闲游戏工具包重…...

python之画动态图 gif效果图

import pandas as pd import matplotlib import matplotlib.pyplot as plt import os# set up matplotlib is_ipython inline in matplotlib.get_backend() if is_ipython:from IPython import displayplt.ion()def find_csv_files(directory):csv_files [] # 用于存储找到的…...

【JavaWeb】用注解代替配置文件

WebServlet("/query") public class QueryServlet extends HttpServlet {...}在Servlet类上写WebServlet("query"),就相当于在配置文件里写了↓ <servlet><servlet-name>query</servlet-name><servlet-class>QueryServlet</se…...

SpringBoot 3.0 升级之 Swagger 升级

文章目录 SpringFox3.0.0openapi3Swagger 注解迁移ApiApiOperationApiImplicitParamApiModelApiModelProperty 最近想尝试一下最新的 SpringBoot 项目&#xff0c;于是将自己的开源项目进行了一些升级。 JDK 版本从 JDK8 升级至 JDK17。SpringBoot 版本从 SpringBoot 2.7.3 升…...

AR游戏开发

增强现实&#xff08;Augmented Reality&#xff0c;AR&#xff09;游戏是一种整合了虚拟和现实元素的游戏体验。玩家通过使用AR设备&#xff08;如智能手机、AR眼镜或平板电脑&#xff09;来与真实世界互动&#xff0c;游戏中的数字内容与真实环境相结合。以下是一些关于AR游戏…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

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

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

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...

uni-app学习笔记三十五--扩展组件的安装和使用

由于内置组件不能满足日常开发需要&#xff0c;uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件&#xff0c;需要安装才能使用。 一、安装扩展插件 安装方法&#xff1a; 1.访问uniapp官方文档组件部分&#xff1a;组件使用的入门教程 | uni-app官网 点击左侧…...

Mac flutter环境搭建

一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...