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

2025/10/11 模拟赛总结 - sb

2025/10/11 模拟赛总结

太愚蠢了

A. 优势种类

期望分数:100pts

实际分数:100pts

时间分配:35min

思路:首先考虑“优势种类”是什么,容易发现对于两个连续相同数或者两个相同的数夹着一个数都是可以一直往两边扩展的。题目要求最小字典序,那么从小往大考虑每个数字会染色给哪些位置,显然前缀最大值大于我当前这个数就可以一直往前更新,这样一定会使得字典序最小。线段树维护前缀最大值即可

B. 信号塔

期望分数:0pts

世界分数:0pts

时间分配:1h

思路:仅仅发现最终序列是一段段连续被覆盖的区间和没被覆盖的点组成,没有想到可以直接按这些区间转移

总结:因为最终序列是由一些区间组成的,那么实际上就是对于一些给定区间,求出组合这些区间使得被覆盖的点不一样的方案数。这是一个简单 dp,按照极长区间转移可以保证不会有两个小区间拼成一个大区间的重复情况

C. 黑暗密钥

期望分数:65pts

实际分数:10pts

挂分原因:又是数组开小了。。。忘记 01trie 空间要开大一点了

思路:发现 \(k = 1\)\(l = r\) 都是 01trie 模板,其中 \(n, q \le 400\) 需要想一下。可以发现对于 \(l, r\) 二进制中第一个不同位,第 \(k\) 大的数一定小于 \(l\) 或者大于 \(r\),那么直接设置成 \(0\) 或者 \(111111……\),然后发现如果 \(l\)\(r\) 都已经不需要考虑了,那么就没有 \(l, r\) 的限制了,这个就是简单贪心,然而最后不知道哪里写错了,只能打 65pts 还打挂了。

(然而这好像就是相当于把 \([l, r]\) 分解成 \(\log r - l + 1\) 个区间)然而没有想到如何优化后面的贪心,本来以为预处理每一个子树内的第 k 小空间时间都会炸,但是考虑到每个子树内只需要算 \(size_x\) 个第 k 小,就算每个节点都把子树内的答案记录下来总共也才需要 \(n\log n\) 的空间

总结:这个可以暴力存储的方法不太了解说是,好像点分树曾经用过这种东西

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

相关文章:

  • 分布式训练的一些知识
  • Visual Studio 2013 Update 4 中文版安装步骤(带TFS拥护)附安装包​
  • 排列
  • 白纷纷副
  • 低秩适配器(LoRA)
  • ROC曲线
  • 10.12~10.18随笔
  • 面向对象的题目
  • P11229 [CSP-J 2024] 小木棍题解
  • [HZOI] CSP-S模拟29
  • 初识pytorch:数据标准化及数据增强的transforms
  • 谈程序员如何做好业务
  • 10.11 CSP-S模拟29 改题记录
  • 二三阶行列式
  • 2025 年 10 月 8 日 语文作业
  • CHAR与VARCHAR深度解析:MySQL字符类型选择指南与性能对比
  • vivo霸榜背后:以技术打赢用户保卫战
  • 国庆期间做题记录
  • 02020508 EF Core高级08-表达式树、Expression和委托的关系、查看表达式树结构、AST、手动创建表示树、工厂方法
  • UnitTask中的Forget()与 CTS
  • commons-net - 详解
  • 12 种 Pandas 测试技巧,让数据处理少踩坑
  • 02020505 EF Core高级05-实体的5种状态、EntityEntry、AsNoTracking、实体状态跟踪
  • securityCTF 2025 pwn方向题解
  • 02020507 EF Core高级07-悲观并发控制、乐观并发控制、EF Core连接MySQL、RowVersion
  • linux防火墙操作命令
  • 02020506 EF Core高级06-EF Core批量删除更新插入、全局筛选器、软删除、全局筛选的性能问题
  • 机器学习社会影响与导航系统研究
  • ubuntu24.04 desktop 安装vnc远程桌面(亲测)
  • 完整教程:游标查询在对话历史场景下的独特优势