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

ABC 427 EF

E

\(BFS\) 求最短路

需要注意到,所有垃圾是作为整体一起移动的,因此可能存在垃圾的所有区域一定是原图的某个子矩阵(子矩阵之外的其他区域至少有过一次出界,说明垃圾已被清除),只有 \(H^{2}W^{2}\) 种。而整张图在每个方向的偏移次数也是固定的,即 \(dx \in [-n,n]\)\(dy \in [-m, m]\)。因此,可以用 \((lx, ly, rx, ry, dx, dy)\) \(6\) 个变量构成的元组表示转移状态,进行 \(bfs\) 转移,总状态数是 \(O(H^{3}W^{3})\) 的,刚好符合限制。

转移过程需要注意两个限制:

  1. 偏移时任何垃圾不能经过 \(T\) 所在位置
  2. 每个方向的偏移次数有上下界

最终符合要求的状态:\((lx, ly, rx, ry)\) 表示的子矩阵内没有任何垃圾(子矩阵之外的垃圾至少出过一次界,此时所有垃圾一定都已被清除)。而判断某个子矩阵内是否有垃圾,直接用二维前缀和预处理即可,实现 \(O(1)\) 查询。具体细节见代码。

code

F

折半搜索 + 斐波那契数性质

\(n \leq 60\),即使将区间分成两半,每侧最多仍会有 \(30\) 个数,不能直接状压暴力枚举所有子序列。但注意到子序列需要额外满足一个性质:不能选择任意相邻的两个数。这样每侧的合法子序列个数就会大幅度减少:具体地,一个长度为 \(n\) 的序列,选择满足任意两个数不相邻的子序列的个数为 \(fib_{n}\),而打表发现 \(fib_{30}\) 约为 \(2e6\)。因此每一侧单独的答案可以直接暴力来求;而求两侧合并的答案,也只需要枚举一侧,找另一侧相对应的余数即可,复杂度是 \(O(NlogN)\) 的,\(N = 2e6\),因此折半搜索即可。但需要注意,将序列分成两半后,需要额外考虑去除左侧结尾和右侧开头两个数相邻的情况,这种情况的计算方式和上述相同,只需要钦定一定选这两个数即可。总复杂度为 \(O(NlogN)\),具体细节见代码。

code

http://www.hskmm.com/?act=detail&tid=29353

相关文章:

  • SHA256文件完整性校验
  • 基于OpenEuler--docker容器化部署ceph集群 - 实践
  • 接口导入 jmeter
  • 深入理解MySQL的MVCC(多版本并发控制)实现原理
  • Kubernetes环境下Nginx代理Nacos服务请求故障诊断
  • 备考笔记1
  • 2025年新型振动电机厂家权威推荐榜:创新技术与高效性能深度
  • SSL/TLS协议如何确保HTTP通信的安全
  • 2025钢衬塑储罐厂家最新权威推荐榜:耐腐性能与结构强度双优
  • 2023-网鼎杯web-platfrom
  • 区分iBatis与MyBatis:两个Java数据库框架的比较
  • 2025大棕拉链厂家权威推荐榜:品质工艺与创新设计深度解析
  • JavaScript加密与解密技术:Hook技术应用案例分析
  • Oracle数据库创建表空间和索引的SQL语法示例
  • NOIP2016普及组port
  • 从增长焦虑到经营确定性:巨益OMS业财一体化的实践路径
  • 数据结构-双向链表
  • Alexa对话式AI技术进展全解析
  • AI小说生成器:智能创作与一致性维护的全流程解决方案
  • 2025无锡考编培训机构权威推荐榜:专业辅导与高通过率口碑之
  • 数据结构-单向循环链表
  • 论人工智能,对人类生产的影响。
  • 2025高频超声波检测设备厂家权威推荐榜:精准检测与技术创新
  • HEU KMS Activator最新功能使用教程及介绍,附HEU KMS Activator最新版下载
  • PWN手的成长之路-14-ciscn_2019_c_1-ret2libc
  • 国内高速下载镜像
  • 2025数控高速滚齿机厂家权威推荐榜:精密加工与高效产能标杆
  • 完整教程:prompt提示词工程---如何让大模型更听得懂人话
  • 2025年10月广州 1688 代运营服务商推荐,阿里巴巴1688店铺代运营、全店托管代运营公司推荐!
  • 2025拉伸器厂家最新权威推荐榜:技术实力与市场口碑深度解析