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

2025.9.21 测试 (a1a2a3a4a5)

这套题比较简单 ?

1.

P10528 [XJTUPC 2024] 崩坏:星穹铁道

这题就是矩乘板子

2.

P3667 [USACO17OPEN] Bovine Genomics G

原题应该是想让二分长度后 ,哈希判断的

但数据范围小了(我的 \(n^3\) 暴力过了 )

哈希模数取小点,然后用数组存就是 \(o(1)\) 的,有点冲突的危险

3.

P3084 [USACO13OPEN] Photo G

这题有显然的差分约束做法

就是把每个前缀看成点,然后列关系

然后朴素 \(spfa\) 被卡了

然后线性做法给了 \(dp\)\(dp[i]\) 表示考虑 \(i\) 个,选了第 \(i\) 个,最多选几个

然后设 \(L[i]\)\(i\) 左边的区间,左端点最大值,上一个位置必须在其右才能保证每个区间至少选一个

\(R[i]\) 为包含 \(i\) 的区间的最端点最小值,上一个位置必须在其左才能保证每个区间至多选一个

那么 \(j\) 取值范围即为 \(L[i]\) ~ \(R[i] - 1\)

然后预处理这两个数组就是先扫所有区间给初始化,然后再整体扫一遍,去 \(max / min\)

预处理出来后根据定义我们知道转移区间单调,上单调队列即可

然后这题有归纳证明 \(f[i]\) 有值即单调,可以不写单调队列

单调队列实现

4.

P11660 我终将成为你的倒影

烤柿的时候傻了,考后感觉正解所有的思路都想到了,为何没写 ? 666

考虑 \(a , b\) 是根号级别

主要是 \(n \times b\) 复杂度刚刚好

暴力考虑枚举 \(i , a , b\) 然后处理出,然后 \(O(1)\) 查询即可

发现了什么 ?

预处理复杂度超标并且存不下,询问却游刃有余

那我们可以可以根号平衡一下 ?

继续观察柿子

我们可以发现 \(x_i / b\)\(x_{i - 1} / b\) 只有差 \(1\) 的时候才可能有贡献

那具体一点呢

我们发现知道 \(x,b\) 后,合法的 \(a\) 是一段区间

这样我们使用差分完美解决

但存不下怎么办,都到这了,自然很容易想到可以存一部分

发现信息可差分,存根号个前缀和的点即可

然后这一步其实也可以用分块做

分块实现

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

相关文章:

  • 原码、反码和补码
  • Русский язык
  • 基于Hex Editor Neo的二进制文件模板
  • 【F#学习】字符
  • kubebuilder创建Operator示例
  • 集训总结(八)
  • 使用try-finally结构执行状态重置
  • java03预习
  • x6831卡顿分析
  • 实测对比:权威榜单之微信排版软件Top5(含详细测评)
  • 【F#学习】布尔运算优先级
  • 粘连字符验证码的分割与识别思路
  • 深入解析:【Spark+Hive+hadoop】基于spark+hadoop基于大数据的人口普查收入数据分析与可视化系统
  • part 8
  • 【本地音乐库】的搭建管理工具推荐
  • 扭曲变形验证码的图像处理与识别思路
  • 每日收获
  • C++中std::map容器中元素删除方法汇总 - 详解
  • 物理半程与半时问题
  • 从用户态到内核态:Windows CC 技术深度解析(第一篇:DNS隧道)
  • 9.22 科研小结:不要总是预设成功,失败才是常态
  • STM32光强传感器实验详解 - 实践
  • 在CodeBolcks下wxSmith的C++编程教程——从Hello world开始讲述wxSmith使用基础
  • 【Azure Batch】使用Start Task来挂载Storage Blob
  • HP notebook set your key to action key /multimedia key
  • newDay01
  • springboot 整合Redis实现发布/订阅功能
  • CCPC online 2025题解 ( A~H+K)
  • 2025.9.22总结 - A
  • 实用指南:GESP三级考纲+三级考试知识点详解