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

核桃 HT-082-Div.2 S 模拟赛

假装自己过了 2 个题。


【HT-082-Div.2】核桃CSP-S组模拟赛

链接:link
题解:

时间:4h (2025.10.17 08:00~12:00)
题目数:4
难度:

A B C D
\(\color{#FFC116} 黄\)
*1400

估分:100 + 30 + 30 + 40 = 200
得分:
Rank:


场祭

读 AB。

A 大水题,20min 切掉了。

B 一眼 dp,令 \(f_{i,j}\) 为前 \(i\) 个,有 \(j\) 个还原点,且 \(i\) 必须被翻转的方案数,然后尝试转移,发现要考虑的东西不少,因为在选了上一个状态 \(f_{p,*}\) 之后,包含 \(i\) 的被翻转区间的左端点可以是 \((p,i]\) 中的任意一个位置,然后还要考虑 \(j\) 的限制,挺麻烦的,得到了一个复杂度过于可怕的方程(\(c_{l,r}\) 表示翻转 \([l,r]\) 得到的还原点个数):

\[f_{i,j} = \sum _{p=0} ^{i-1} \sum _{x=0} ^j f_{p,j-x} \cdot \sum _{q=p+1} ^i [q-p+c_{q,i} = x] \]

而且根本不好优化,不过想了想发现直接枚举 \(p,q\) 就可以不需要枚举 \(x\) 了,得到:

\[f_{i,j} = \sum _{p=0} ^{i-1} \sum _{q=p+1} ^i f_{p,j-c_{q,i}-(q-p-1)} \]

然后发现似乎后面那个 \(\sum\) 可以前缀和优化?令 \(s_{i,j,p} = \sum _{q=p+1} ^{i} f_{p,j-c_{q,i}-(q-p-1)}\),那么 \(s_{i,j,p}\) 似乎是可以从 \(s_{i,j,p+1}\) 递推过来的?

没管,先写了个不优化的 \(O(n^4)\) dp,然后发现过样例了,于是开始写优化,写写写没过样例,哦原来不可以这样,因为 \(p\) 是会影响每一项的。

不会了。不过为什么不给高复杂度正解的部分分啊喂!

考虑到 \(k=0\) 可以砍掉一个 \(n\),所以这个 dp 应该有 30pts。然后 \(a_i\) 两两不同的不会,\(k=n\) 好像会,不过就 10pts 等最后写吧(

读 CD。

欸这个 D 怎么给了 40pts 的暴力高消!这么好!

不过还是先写 C,注意到操作次数不会太多,所以直接模拟,期望能拿到 \(\ge\) 30pts 吧。

写 D,不过大样例,回去看看题面发现 \(a_i,c_i\) 可能相等,哦又过不去另一个样例了,继续看题面发现没有规定不存在自环(,改了就过样例了。

10min 摆了。


补题


天依宝宝可爱!

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

相关文章:

  • 2025 选双曲铝单板,就找四川汇才铝业
  • 2025 氟碳铝单板采购,四川汇才是优选
  • 题解:P7275 计树
  • 实验1现代C++编程初体验
  • mysql新建用户并授权,mysql新建用户并授权完整指南
  • Vue3 父子组件之间的双向数据绑定
  • 2025年10月上海老房翻新公司推荐榜单:多维度数据驱动的理性选择参考
  • 2025年10月金融街附近豪华酒店推荐对比榜:结合奖项数据与用户体验的实用攻略
  • 2025年10月石墨电极厂家推荐榜单详解:从产线到应用看晶碳科技真实表现
  • 2025年西安买房新楼盘口碑排行榜:地建嘉信臻城领跑高端住宅市场
  • 2025年西安买房新楼盘口碑排行榜TOP10:地建嘉信臻城领跑高端住宅市场
  • 2025年10月石墨电极厂家推荐榜单:河北晶碳科技深度评测与行业对比
  • 2025年数粒机厂家推荐排行榜,防爆/新型/高速/高精度/智能/大容量/多通道/电子/视觉/全自动/低噪音/制药用/农业用/食品用/电子元件/光电/定制化/鹌鹑蛋/糖果/坚果/药品/片剂数粒机公司推荐
  • 2025 年国内铝单板厂家权威推荐榜
  • git和gitee的学习研究
  • CRMEB批量发货源码解析:自定义扩展与性能优化实践
  • 解析国标GB28181算法算力平台EasyGBS设备统一管理与视频汇聚能力
  • 深度解析 AI Agent、MCP 与 RAG:原理、区别及应用全景洞察
  • Java并发之AQS详解
  • 从“看得见”到“看得懂”:国标GB28181算法算力平台EasyGBS与公安安防数字化的深度融合
  • 2025 年优法兰品牌最新推荐榜:优法兰骨相支撑、优法兰魔法 CC 针、优法兰 CaHA、优法兰骨相塑形、优法兰面部注射填充剂五大国内医美品牌专利技术、市场口碑及选择指南全景解析
  • 10.13课后作业 - GENGAR
  • 山海鲸可视化可以导入哪些常用的3D模型?
  • 2025 年光谱仪厂家最新推荐排行榜:便携式 / 有色金属 / X 射线荧光等多类型设备优质厂家深度解析
  • 2025 年分析仪生产厂家最新推荐榜单:覆盖便携式、有色金属、荧光等多类分析仪,帮企业选靠谱优质品牌
  • Kafka、RabbitMQ、RocketMQ、ZeroMQ等 消息中间件 介绍和对比
  • 猪脚与猪脚饭与猪脚饭之店
  • 2025年10月中国高端医美机构推荐榜单:安全认证与专家资质全解析
  • 读书笔记:什么时候该用B*树索引?一个接地气的解读
  • 2025年工作服厂家权威推荐榜:防静电/劳保/国网/餐厅/工厂/电工/防酸碱/电力/车间/航空/员工工作服,文化衫/T恤/POLO衫/冲锋衣全品类精选