AcWing 1250. 格子游戏(并查集)
题目链接
活动 - AcWing本课程系统讲解常用算法与数据结构的应用方式与技巧。
https://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;
}
参考资料
- AcWing算法提高课
相关文章:
AcWing 1250. 格子游戏(并查集)
题目链接 活动 - AcWing本课程系统讲解常用算法与数据结构的应用方式与技巧。https://www.acwing.com/problem/content/1252/ 题解 当两个点已经是在同一个连通块中,再连一条边,就围成一个封闭的圈。一般用x * n y的形式将(x, y࿰…...
CSS对文本的简单修饰
CSS格式: 格式一:在head中的style标签范围内。 < style> 在style内的只写名字不写 : < > 选择器 { 属性的名称 : 样式; 属性的名称:样式; } < style> style中的注释用/* *…...
C++17中if和switch语句的新特性
1.从C17开始,if语句允许在条件表达式里添加一条初始化语句。当仅在if语句范围内需要变量时,使用这种形式的if语句。在if语句的条件表达式里定义的变量将在整个if语句中有效,包括else部分。 std::mutex mx; bool shared_flag true; // guard…...
极坐标下的牛拉法潮流计算57节点MATLAB程序
微❤关注“电气仔推送”获得资料(专享优惠) 潮流计算: 潮流计算是根据给定的电网结构、参数和发电机、负荷等元件的运行条件,确定电力系统各部分稳态运行状态参数的计算。通常给定的运行条件有系统中各电源和负荷点的功率、枢纽…...
软件设计师——计算机网络(三)
📑前言 本文主要是【计算机网络】——软件设计师——计算机网络的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是听风与他🥇 ☁️博客首页:CSDN主页听风与他 …...
【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 词向量数据库是一个用于自然语言处理(NLP)和机器学习的工具,它主要用于词嵌入(word embeddings)。词向量是将单词转换为向量表示的技术,可以捕获单词之间的语义和语法关系,使得计算…...
Gin之GORM 操作数据库(MySQL)
GORM 简单介绍 GORM 是 Golang 的一个 orm 框架。简单说,ORM 就是通过实例对象的语法,完成关系型数据库的操作的技术,是"对象-关系映射"(Object/Relational Mapping) 的缩写。使用 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 应用混淆: Flutter 应用的混淆非常简单,只需要在构建 release 版应用时结合使用 --obfuscate 和 --split-debug-info 这两个参数即可。 –obfuscate --split-debug-info 用来指定输出调试文件的位置,该命令会生成一个符号映射表。目前…...
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 关闭上面的窗口,继续操作 激活ParallelsDesktop 关闭上面的…...
【云原生kubernets】Service 的功能与应用
一、Service介绍 在kubernetes中,pod是应用程序的载体,我们可以通过pod的ip来访问应用程序,但是pod的ip地址不是固定的,这也就意味着不方便直接采用pod的ip对服务进行访问。为了解决这个问题,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,此版本包含诸多更新: Material 3 成为新的默认主题、为 Android 带来 Impeller 的预览版、允许添加适用于 DevTools 的扩展程序等等,以及同步推出 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 项目,于是将自己的开源项目进行了一些升级。 JDK 版本从 JDK8 升级至 JDK17。SpringBoot 版本从 SpringBoot 2.7.3 升…...
AR游戏开发
增强现实(Augmented Reality,AR)游戏是一种整合了虚拟和现实元素的游戏体验。玩家通过使用AR设备(如智能手机、AR眼镜或平板电脑)来与真实世界互动,游戏中的数字内容与真实环境相结合。以下是一些关于AR游戏…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
