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

NOIP2023模拟1联测22 爆炸

NOIP2023模拟1联测22 爆炸

231023_4wt4eAb5wJ.png (667×698) (hszxoj.com)

题目大意

​ 自己看

思路

当一个炸弹被引爆后,它的方向是固定的。如果被竖着引爆,那么应该选择横着引爆,否则选择竖着引爆,这是显然 的。

考虑对于每个炸弹 ( i , j ) (i , j) (i,j) 将第 i i i 行和第 j j j 列连边

对于每个水晶 ( i , j ) (i , j) (i,j) 如果 i i i 行和 $j $ 列不在一个连通块内,各自的连通块的贡献分别加上 1 1 1 ,否则加一个就好了

枚举每一个连通块,如果能够形成一个环,那么这个连通块的答案就是已经统计过的贡献

否则这个连通块的答案就是损失一行或者一列的水晶

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int N = 3005;
int n , m , k , b , mp[N][N] , fa[N << 1] , a[N << 1] , flg , vis[N << 1] , min1 , sum[N << 1] , ans , cnt;
char c;
vector<int> v[N << 1];
int find (int x) { return fa[x] != x ? fa[x] = find (fa[x]) : x; }
void dfs (int x , int fa) {if (flg) return;if (vis[x]) {flg = 1;return;}vis[x] = 1;if (v[x].size() == 1) min1 = min (min1 , a[x]);for (auto it : v[x])if (it != fa)dfs (it , x);
}
int main () {freopen ("boom.in" , "r" , stdin);freopen ("boom.out" , "w" , stdout);scanf ("%d%d%d%d" , &n , &m , &k , &b);fu (i , 1 , n + m) fa[i] = i;fu (i , 1 , n) {fu (j , 1 , m) {c = getchar ();while (c != '.' && c != 'k' && c != 'b') c = getchar ();if (c == '.') mp[i][j] = 1;else if (c == 'b') {mp[i][j] = 2;v[i].push_back(j + n);v[j + n].push_back(i);fa[find (i)] = find (j + n);}]]]elsemp[i][j] = 3;}}fu (i , 1 , n) {fu (j , 1 , m) {if (mp[i][j] == 3) {sum[find (i)] ++;if (find (i) != find (j + n)) {sum[find (j + n)] ++;a[i] ++ , a[j + n] ++;} }}}// fu (i , 1 , n + m) cout << a[i] << " ";// return 0;fu (i , 1,  n + m) {if (vis[i]) continue;min1 = INT_MAX , flg = 0;dfs (i , 0);if (flg) ans = max (ans , sum[find (i)]);else ans = max (ans , sum[find (i)] - min1);}printf ("%d" , ans);return 0;
}

相关文章:

NOIP2023模拟1联测22 爆炸

NOIP2023模拟1联测22 爆炸 题目大意 ​ 自己看 思路 当一个炸弹被引爆后&#xff0c;它的方向是固定的。如果被竖着引爆&#xff0c;那么应该选择横着引爆&#xff0c;否则选择竖着引爆&#xff0c;这是显然 的。 考虑对于每个炸弹 ( i , j ) (i , j) (i,j) 将第 i i i 行…...

http post协议实现简单的rpc协议,WireShark抓包分析

文章目录 1.http 客户端-RPC客户端1.http 服务端-RPC服务端3.WireShark抓包分析3.1客户端到服务端的HTTP/JSON报文3.2服务端到客户端的HTTP/JSON报文 1.http 客户端-RPC客户端 import json import requests# 定义 RPC 客户端类 class RPCClient:def __init__(self, server_url…...

1024程序员节

一年一年真快啊&#xff0c;...

嵌入式--->怎样选择编译语言,C C++或是Rust?

C 老牌语言&#xff0c;不可替代&#xff0c;速度和资源占用都是嵌入式领域着重考虑的 Rust 作为新生语言&#xff0c;已经成长到可以和C进行竞争的地步&#xff0c;不论是速度还是资源占用看&#xff0c;还是安全性 C 嵌入式开发使用C的思想&#xff0c;可以极大地简化代码&am…...

一起学数据结构(12)——归并排序的实现

1. 归并排序原理&#xff1a; 归并排序的大概原理如下图所示&#xff1a; 从图中可以看出&#xff0c;归并排序的整体思路就是把已给数组不断分成左右两个区间&#xff0c;当这个区间中的数据数量到达一定数值时&#xff0c;便返回去进行排序&#xff0c;整体的结构类似二叉树…...

读书笔记之《敏捷测试从零开始》(一)

大家好&#xff0c;我是rainbowzhou。 子曰&#xff1a;学而时习之&#xff0c;不亦说乎&#xff1f;今天我想和大家分享一本测试书籍——《敏捷测试从零开始》。以下为我的读书笔记&#xff1a; 精彩片段摘录&#xff1a; 焦虑往往来自于对比&#xff0c;当你在自己的圈子里面…...

视频亮度太低了,如何调高

充足、均匀、稳定的光亮对于视频制作是至关重要的&#xff0c;在现实生活中&#xff0c;不可预见的天气变化和拍摄地方的阴暗常常给我们留下暗淡无光的视频片段。 如果你的视频太暗想知道如何使它变亮&#xff0c;且又不知道使用哪个工具&#xff0c;那你无需担心&#xff0c;因…...

Xubuntu16.04系统中安装create_ap创建无线AP

1.背景说明 在Xubuntu16.04系统的设备上安装无线WIFI模块后&#xff0c;想通过设备自身的无线AP&#xff0c;进行和外部设备的连接&#xff0c;需要安装create_ap软件&#xff0c;并设置无线AP的名称和密码&#xff0c;并设置为开机自启动。 create_ap是一个用于在Linux系统上创…...

WPF 设置全局静态参数

可以使用system官方库来设置参数 引入system xmlns:system"clr-namespace:System;assemblymscorlib"设置参数资源 <Window.Resources><system:Double x:Key"ButtonWidth">90</system:Double></Window.Resources>使用参数资源 &l…...

Leetcode链表问题汇总

目录 [2. 两数相加](https://leetcode.cn/problems/add-two-numbers/)[206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/)[206. 反转链表 II](https://leetcode.cn/problems/reverse-linked-list-ii/)[19. 删除链表的倒数第 N 个结点](https://leetcode.cn/p…...

基于卷的磁盘扫描算法设计

1、设计目的 常规情况下&#xff0c;当我们扫描计算机的硬盘时&#xff0c; 通常会使用诸如FindFirstFile/FindNextFile(Windows)&#xff0c;或者opendir/readdir(Linux)遍历扫描的目录。 一般情形下&#xff0c;由于文件数量相对较少&#xff0c;文件夹层次低&#xff0c;扫…...

计算机组成原理-存储器概念

计算机组成原理-存储器 存储系统的基本概念 1.层次结构 可以直接被CPU读取: 高速缓存:cache主存储器: 主存和内存 辅助存储器: 辅存和外存 2.分类 1.按层次结构划分 如上面所示 2.按存储介质 半导体存储器磁表面存储器光存储器 3.按信息可更改性 r/w存储器ROM(只读存储器) 4…...

力扣刷题 day54:10-24

1.十进制整数的反码 每个非负整数 N 都有其二进制表示。例如&#xff0c; 5 可以被表示为二进制 "101"&#xff0c;11 可以用二进制 "1011" 表示&#xff0c;依此类推。注意&#xff0c;除 N 0 外&#xff0c;任何二进制表示中都不含前导零。 二进制的反…...

Java基础篇 | Java8流式编程

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; Java从入门到精通 ✨特色专栏&#xf…...

SolidworksSimulation完成对压力容器的强度分析

如何通过使用SolidworksSimulation完成对压力容器的分析并查看实 体的膜片应力强度以及弯曲应力强度&#xff0c;操作简单易学&#xff0c;让我们进入到操作界面。 我们以罐体底部实体模型为例&#xff0c;这里已经提前设置好了材料。 点击新算例&#xff0c;选择静应力分析 由…...

【C++】继承 ⑨ ( 继承中成员变量同名的处理方案 )

文章目录 一、继承中成员变量同名的处理方案1、继承中成员变量同名的场景说明2、使用域作用符区分同名成员变量 二、代码示例 - 继承中成员变量同名的处理方案 一、继承中成员变量同名的处理方案 1、继承中成员变量同名的场景说明 子类 继承 父类 的 成员 , 如果 子类 中定义了…...

Python报错:‘EagerTensor‘ object has no attribute ‘reshape‘

在使用RPython时&#xff0c;发现python代码部分报错&#xff1a;‘EagerTensor‘ object has no attribute ‘reshape‘ 如何解决&#xff1f; 使用np.array 转换为array&#xff0c;再进行reshape 参考&#xff1a; ‘EagerTensor‘ object has no attribute ‘reshape‘处…...

docker-compose手册

大家好&#xff0c;我叫徐锦桐&#xff0c;个人博客地址为www.xujintong.com。平时记录一下学习计算机过程中获取的知识&#xff0c;还有日常折腾的经验&#xff0c;欢迎大家访问。 前言 一些自己经常用到的docker-compose知识。 一、运行和启动项目 1.1、docker-compose运行…...

【珠峰 WEB 前端架构师课程】学习笔记 100 篇(完结)

该课程是珠峰姜文老师讲的&#xff0c;个人觉得讲的很不错&#xff0c;一路在 b 站学习下来做了 100 篇的学习笔记&#xff0c;收获颇丰。 该课程主要讲了高阶函数、函数柯里化、发布订阅模式、观察者模式、从 0 到 1 实现一个 promise&#xff0c;co 库的实现、eventloop 执行…...

Java线程中sleep()、wait()、yield()、join()方法的使用

1.sleep() sleep(): sleep 方法属于 Thread 类&#xff0c;该行为中线程不会释放锁&#xff0c;只阻塞线程&#xff0c;让出cpu给其他线程&#xff0c;当达到指定的时间后会自动恢复运行状态继续运行。 2.wait() wait(): 该方法属于 Object 类&#xff0c;在这个过程里线程会…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...

【PX4飞控】mavros gps相关话题分析,经纬度海拔获取方法,卫星数锁定状态获取方法

使用 ROS1-Noetic 和 mavros v1.20.1&#xff0c; 携带经纬度海拔的话题主要有三个&#xff1a; /mavros/global_position/raw/fix/mavros/gpsstatus/gps1/raw/mavros/global_position/global 查看 mavros 源码&#xff0c;来分析他们的发布过程。发现前两个话题都对应了同一…...

Web APIS Day01

1.声明变量const优先 那为什么一开始前面就不能用const呢&#xff0c;接下来看几个例子&#xff1a; 下面这张为什么可以用const呢&#xff1f;因为复杂数据的引用地址没变&#xff0c;数组还是数组&#xff0c;只是添加了个元素&#xff0c;本质没变&#xff0c;所以可以用con…...

Vuex:Vue.js 应用程序的状态管理模式

什么是Vuex&#xff1f; Vuex 是专门为 Vue.js 应用程序开发的状态管理模式 库。它采用集中式存储管理应用的所有组件的状态&#xff0c;并以相应的规则保证状态以一种可预测的方式发生变化。 在大型单页应用中&#xff0c;当多个组件共享状态时&#xff0c;简单的单向数据流…...

【SSM】SpringMVC学习笔记7:前后端数据传输协议和异常处理

这篇学习笔记是Spring系列笔记的第7篇&#xff0c;该笔记是笔者在学习黑马程序员SSM框架教程课程期间的笔记&#xff0c;供自己和他人参考。 Spring学习笔记目录 笔记1&#xff1a;【SSM】Spring基础&#xff1a; IoC配置学习笔记-CSDN博客 对应黑马课程P1~P20的内容。 笔记2…...

Prompt工程学习之思维树(TOT)

思维树 定义&#xff1a;思维树&#xff08;Tree of Thoughts, ToT&#xff09; 是一种先进的推理框架&#xff0c;它通过同时探索多条推理路径对思维链&#xff08;Chain of Thought&#xff09;** 进行了扩展。该技术将问题解决视为一个搜索过程 —— 模型生成不同的中间步骤…...