首页 > 其他分享 >9.18 模拟赛

9.18 模拟赛

时间:2024-09-19 22:34:27浏览次数:9  
标签:障碍物 连通 炸掉 9.18 相邻 le col 模拟

https://mna.wang/contest/1412/problem/3

很好很好的计数题。

给定一个 \(n \times m\) 的网格图,其中 . 表示空地,# 表示障碍物。

你需要选出恰好两个不同的障碍物,将它们变成空地,使得操作完成后,节点 \((1, 1)\) 和 \((n, m)\) 恰好通过空地四联通,保证初始时 \((1, 1)\) 和 \((n, m)\) 不为障碍物,请你输出方案数。

\(n,m \le 1000\)。

首先如果原本 \((1, 1)\) 和 \((n, m)\) 就连通那么简单特判掉即可。以下讨论的都是 \((1, 1), (n, m)\) 不得不炸若干障碍物后才能连通的情况。

我们给每个连通块一个编号。\((i, j)\) 所在的连通块的编号为 \(col_{i, j}\)。

我们思考将两个什么样的障碍物炸掉后能让 \((1, 1), (n, m)\) 连通。分类讨论。

一种情况是其中一个障碍物是特殊点,换言之只需要炸掉这一个障碍物即可连通。那么另一个障碍物显然无限制随便选。

思考什么样的点是特殊点。显然将某个点 \(A\) 炸掉后,原本与 \(A\) 相邻的连通块会合并成一个。我们希望将 \((1, 1), (n, m)\) 连通,也就是将 \(col_{1. 1}\) 和 \(col_{n, m}\) 合并,也就是说 \(A\) 必须与连通块 \(col_{1, 1}, col_{n, m}\) 均相邻。统计这个是极易的。

我们把上面说的特殊点标记。那么在下面的情况中这些被标记的点一定不能被选,否则会算重。我们默认下面说所有点都是没有被标记的。

对于剩下的情况,即只有炸掉两个障碍物才能连通。

首先你做掉这两个障碍物相邻的情况。接下来我们考虑这两个障碍物不相邻的情况。

如果炸掉点 \(A, B\) 后合法,等价于 \(A\) 原本与 \((1, 1)\) 连通,\(B\) 原本与 \((n, m)\) 连通,且 \(A, B\) 与至少一个连通块均连通。换言之存在至少一个连通块 \(C\) 满足 \(A\) 与 \(col_{1, 1}, C\) 相邻且 \(B\) 与 \(col_{n, m}. C\) 相邻。

我们求出与障碍物 \((i, j)\) 相邻的连通块编号组成的集合为 \(S_{i, j}\)。显然 \(\mathbf{ |S_{i, j}| \le 4}\)。那么问题等价于求:

  • 有多少障碍物 \((i_0, j_0),(i_1,j_1)\) 满足 \(col_{1, 1} \in S_{i_0, j_0}\) 且 \(col_{n, m} \in S_{i_1, j_1}\) 且 \(S_{i_0, j_0} \cap S_{i_1, j_1 } \ne \varnothing\)。

我们求出所有满足 \(col_{1, 1} \in S_{i, j}\) 的 \((i, j)\) 组成的集合为 \(A\),满足 \(col_{n, m} \in S_{i, j}\) 的 \((i, j)\) 组成的集合为 \(B\)。显然 \(A, B\) 没有交集(有交集会在最开始被特判掉)。上面的问题等价于:

  • 求有多少 \(v \in A, u \in B\) 满足 \(S_v \cap S_u \ne \varnothing\)。

集合?交集?大小 \(\le 4\)?容斥!

做完了。

标签:障碍物,连通,炸掉,9.18,相邻,le,col,模拟
From: https://www.cnblogs.com/2huk/p/18421520

相关文章

  • 国标GB28181设备端SDK,支持将本地文件、网络流、实时流模拟接入国标GB28181视频平台
    现在市面上的国标设备端SDK,基本上都是收费的,一个是这个东西比较小众,还有一个就是确实有一些研发成本,于是,在前段时间,我就将我们之前一直对外收费的EasyGBD国标GB28181设备端的SDK免费了,SDK地址在:https://github.com/EasyDarwin/EasyGBD/tree/main简单看一下EasyGBD的接口://......
  • 2024.9.18
    线性表的顺序存储结构用一组连续的存储单元依次存储线性表的数据元素。特点:线性表的顺序存储是一种随机存取的存储结构。随机存取:即读写存储的消息的时间与存储的位置无关defineMAXSIZE100typedefstruct{ElemTypeelem;//存储空间的基地址intMAXSIZE//容量intlength;......
  • 派遣函数 - 缓冲区设备模拟文件读写
            我们已经明白了缓冲区方式的读写操作,下面根据这部分知识,来编写一个虚拟设备。这个设备来模拟一个文件,可以将这个设备想象成一个普通文件,可以进行读写作。另外,每次写这个文件,文件的长度会增加,可以利用GetFileSize函数(API函数)得到该文件的长度。      ......
  • 2024.9.18 LGJ Round
    C\(n\timesm\)个人,选择某人的代价是\(a_{i,j}\),可以使其负责其所在的行/列,问使得所有行列被负责最小代价。\(nm\le10^5\)。若选择\(a_{i,j}\),看做是第\(i\)行跟第\(j\)列连了一条有向边,你发现最后图的形式是一个基环树森林。但是边是有向的,不难发现如果我们确定了基......
  • 4路同步AD模拟量采集卡800K采样频率—PCIe9757
    阿尔泰科技概述:信息社会的发展,在很大程度上取决于信息与信号处理技术的先进性。数字信号处理技术的出现改变了信息与信号处理技术的整个面貌,而数据采集作为数字信号处理的必不可少的前期工作在整个数字系统中起到关键性、乃至决定性的作用,其应用已经深入到信号处理的各个领域......
  • C++ 面试模拟02
    第一部分:基础知识什么是拷贝构造函数和赋值运算符?它们之间有什么区别?在C++中,const关键字的作用是什么?有哪些常见用法?C++中的内存管理机制是怎样的?如何避免内存泄漏?虚函数(virtualfunction)的作用是什么?虚函数表(vtable)是如何工作的?第二部分:面向对象编程什么是多态性?C++中......
  • 使用Code-Prompt模拟实现openai o1
    背景帮忙点点star吧https://github.com/Disdjj/prompt_in_code前段时间,openai发布了o1,体验一段时间之后,虽然我认为在实际上没有基础模型的提升,但是其自动产生COT,主动思考解决问题的方案,我觉得非常有趣,在一段时间的研究之后,我认为Code-Prompt能够模拟实现一部分......
  • 模拟创建分类.java
    Category.javapublicclassCategory{privateLongid;privateStringname;privateintpostCount;publicCategory(){}publicCategory(Stringname){this.name=name;}publicCategory(Stringname,intpostC......
  • 2024.9.18
    又要早八了,哎呀呀。上午数分,感觉还行,讲了关于e的事情,非常有道理啊,待会儿复习一下。然后是数算,没听课,在后面写数算作业。大主播不来上数算课了,不喜欢,本来想请他吃午饭的。下午计概,大概听明白了,我觉得我作业全对。然后打农,以及问大主播来不来一起吃晚饭,得到的结果是没空。大......
  • 9.18 CSP-S初赛模拟
    一、单项选择题在8位二进制补码中\(10101011\)表示的数是十进制下的()。答案:\(-85\)解析:正数的补码是其自身,负数的补码是除符号位外所有位取反后再加一(这样方便加减)。我们把\(10101011\)减一后取反回去就可以得到\(-85\)了。下列算法中,没有用到贪心思想的算法为()。......