首页 > 其他分享 >SS241009B. 贪吃蛇(snake)

SS241009B. 贪吃蛇(snake)

时间:2024-10-09 19:13:45浏览次数:8  
标签:吃掉 连通 点权 合并 SS241009B 贪吃蛇 snake 权值 清零

SS241009B. 贪吃蛇(snake)

题意

给你一个 \(n \times m\) 的矩阵,满足 \(n \times m \le 10^6\)。每个点有一个权值 \(a_{i,j}\)。从一个点出发,能量值是这个点的点权,然后可以走到四周比它能量小的结点,吃掉它并合并能量。问从每个位置出发,能不能吃完整个地图。

思路

首先显然的贪心是我们每次吃掉最小的可以吃的点,然后可以做暴力了。

经过敏锐的观察显然我没有可以发现,我扩展到的所有比我大的点,如果有一个大点可以吃完所有,那么我也可以吃完所有。

题解说加上一些面向数据的剪枝可以水过去。

然后考虑对于每个点,向所有点权小于等于它的点权的点扩展,直到周围一圈的点权都比它大,这样形成一个关于这个点的连通块。然后再判断现在的它在吃掉连通块内的所有点之后更新能量后能否吃掉周围最小的点。

这个看起来就比较有前途,吧。考虑按照权值顺序枚举每一个点,然后充分利用之前的信息,以此降低复杂度。

按照权值从小到大枚举权值 \(v\),对于 \(a_i=v\)(这里把坐标的两维压成一维),可以继承四周比它小的点的已经处理了的连通块,合并连通块。

这样的连通块满足每个连通块内最大值 \(=v\)。也就是说连通块内每一个点权都 \(\le v\)。维护连通块的权值和,如果连通块权值和小于周围最小的点,那么整个连通块所有点的答案都是 \(0\)。

对于吃掉全部的连通块,它是由若干个权值最大的点,合并若干个连通块得到的一个连通块,对于答案没有钦定为 \(0\) 的点,叫做我,关于我的连通块的周围的最小点权的点到时候一定会把我合并,然后一直合并,直到合并成吃掉全部,这一路上没有因周围过大而导致连通块清零的情况,因此我出发可以吃掉全部,我的答案是 \(1\)。因此,最后所有没有被清零的点的答案都是 \(1\)。

连通块合并用并查集维护,同时维护连通块权值和。判断连通块周围的最小点能否到达,线性做法是在枚举到外面那个最小的点的时候,把连通块称作我,它就会把我合并,然后这时候判断它和我的大小关系,如果我比较小就把我清零。清零连通块就钦定每个连通块是哪个点的时候合并起来的,即每个连通块是关于哪个点的连通块,以那个点作为连通块的祖先,然后把这些祖先按照合并关系建成树,在树上打标记,最后遍历树即可。

时间复杂度 \(O(n \log n)\)。

标签:吃掉,连通,点权,合并,SS241009B,贪吃蛇,snake,权值,清零
From: https://www.cnblogs.com/liyixin0514/p/18454535

相关文章

  • P7078 [CSP-S2020] 贪吃蛇 题解
    P7078[CSP-S2020]贪吃蛇这题好啊题目传送门看到题之后觉得有点像砍蚯蚓的那道题看看题目可以证明,若一条蛇在吃完之后不是最弱的那一条蛇,那么他一定会选择吃,证明如下设蛇长为\(a_{1,\dots,n}\)且依次递增,那么很明显的因为​......
  • 贪吃蛇游戏
    Win32API知识1.Windows这个多作业系统除了协调应用程序的执行、分配内存、管理资源之外,它同时也是⼀个很大的服务中心,调用这个服务中心的各种服务(每⼀种服务就是⼀个函数),可以帮应用程序达到开启视窗、描绘图形、使用周边设备等⽬的。2. 由于这些函数服务的对象是应用程......
  • python贪吃蛇小游戏
    1.简介使用了turtle库来创建图形界面,你可以使用键盘的W、A、S、D键来控制蛇的移动方向。蛇吃到食物后,身体会增长,如果蛇撞到自己或者游戏边界,游戏就会结束。2.代码importturtleimporttimeimportrandomdelay=0.1#生成食物的位置food=turtle.Turtle()food......
  • 豆包MarsCode初体验,用 React 创建一个最经典的贪吃蛇游戏
    以下是「 豆包MarsCode 体验官」优秀文章,作者Find。背景在人工智能快速发展的时代,大模型(LLM)只要有足够的算力和数据就可以做到任何的事情,甚至可以模拟出另一个地球。LLM作为一个革命化的科技,可以取代很多岗位,甚至可以让人类达到“躺着领钱的时代”。Marscode作为一个新推出的IDE......
  • 贪吃蛇的逻辑 scratch 20240921_113436
    项目名称贪吃蛇单蛇版添加角色自制绘制角色我们画一个蛇头注意方向要朝右有一个舌头(红)角色的移动通过上下左右方向键控制蛇头的移动添加角色添加了一个食物食物的克隆重复执行不停的克隆自己每次克隆完成后要等待几秒克隆体设置随机位置等待几秒钟就删除此克隆......
  • turtle实现贪吃蛇小游戏
    今天分享一篇利用python的turtle库实现贪吃蛇小游戏,适合初学者的朋友学习技术点:函数应用time库应用random库应用turtle库应用无身体碰撞的版本,完整代码先附上importturtleimportrandomimporttimedelay=0.1#延迟时间score=0#当前分数high_score......
  • C#编程挑战: 从零开始构建贪吃蛇游戏
    C#编程挑战:从零开始构建贪吃蛇游戏引言贪吃蛇游戏是一款经典且广受欢迎的电子游戏,玩家通过控制一条蛇在屏幕上移动,吃掉食物并避免撞到墙壁或自己的身体。本文将指导你如何使用C#编程语言从零开始构建一个简单的贪吃蛇游戏。我们将涵盖游戏的基本逻辑、图形用户界面(GUI)的实现以及......
  • 贪吃蛇游戏开发 scratch 20240916_140728
    项目名称贪吃蛇规则只要吃食物就会变长碰到边界就死亡碰到自己的尾巴就会死亡角色贪吃蛇食物障碍物关于图像图像分为矢量图与位图矢量图可以无限放大位图放大后会模糊绘制蛇头要求:使用一个圆形来画蛇头圆形有边框蛇头有两个眼睛蛇头有一根红蛇头使用矢量图来绘......
  • 简易贪吃蛇js
    functionsta(){varshe=[{x:0,y:0,s:0}];//身体varshenti='';//当前前进方向varzou='';//下次前进方向vardan={x:0,y:0}//蛋坐标functionadddan(){//生成一个蛋varsy=[];......
  • 贪吃蛇项目实现(C语言)——附源码
    前言贪吃蛇是一款十分经典的游戏,其通过控制贪吃蛇的上下左右移动来吃食物,延长自己的身体,也会因为撞到墙体和自身而死亡。下面我们通过C语言来实现贪吃蛇。1.技术要点C语言枚举,结构体,链表,动态内存管理,预处理指令,函数,Win32API等。2.Win32API 要使用Win32API我们就需......