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

ZR 2025 NOIP 二十连测 Day 6

啊啊啊第一次上 200 /oh


25noip二十连测day6

链接:link
题解:题目内

时间:4.5h (2025.10.21 13:40~18:10)
题目数:4
难度:

A B C D
\(\color{#F39C11} 橙\)
*1200

估分:100 + 72 + 35 + ? = 207 + ?
得分:100 + 72 + 35 + 0 = 207
Rank:61/131


场祭

读题。

开 A,发现似乎很简单,注意到答案一定形如 AAAABBBBABABAB 的形式,就做完了,直接枚举即可。

先不写了,应该是很好写的,继续开 B,显然是 dp,但是发现无论怎么样都逃脱不了要记录两个 \(O(n)\)\(O(V)\) 的状态,于是放弃思考,去进行一个部分分的想,随便搞搞写出来了一个 \(O(nV^2)\) 的 dp,非常优秀,足足有 72pts。

写写写,过样例了。

10min 把 A 写了。

甚至只过了不到 2h。所以有足够的时间去打 CD 的暴力和特殊性质了。

然后发现似乎只会暴力,D 甚至不知道暴力对不对,所以先把 C 的暴力打了。然后继续研究 C,发现可以转化成把所有满足 \(a_i + a_j \ge d\)\((i,j)\) 连边,得到一个图,求删掉最少条边使图成为一个二分图,或者说在二分图左右两边中间保留尽可能的多的边。这样似乎 \(d \le 3\) 就可以做了,可以发现实际上只有 \(0,1,2,3\)\(4\) 种不同的点,然后 \(3\) 一定会产生贡献,所以把 \(1,2\) 分到两边一定是最优的,而 \(0\) 显然放在 \(3\) 少的那一边更优。

注意到是 \(d \le 3\) 而不是 \(d = 3\),所以还需要把 \(d = 0,1,2,3\) 都分讨一遍 /tuu,不过还好,因为 \(1,2\) 都可以直接枚举,毕竟 \(n \le 1000\) 嘛。然后写到 \(3\) 的时候发现过不去样例,于是不想了直接枚举去了,算了下 \(5000 / 1000 \times 333^3 \approx 1.8 \times 10^8\),常数不大 1s 挺能过的,写了之后对着暴力拍出来几个 corner case 就过大样例了。

D 直接爆搜,过掉了 3 个样例,应该能有一些分。


补题

哦 D 看来数据比较强,都 T 飞了呢。


天依宝宝可爱!

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

相关文章:

  • 20251021
  • [论文笔记] Precision-Guided Context Sensitivity for Pointer Analysis
  • 英语_备忘_疑难
  • 数学题刷题记录(数学、数论、组合数学)
  • 朋友圈文案不会写?这个AI指令可能帮得上忙
  • 「JOISC2020-掃除」题解
  • 结对作业
  • CF简单构造小计
  • 深入认识ClassLoader - 一次投产失败的复盘
  • python 包来源镜像
  • CSharp基础复习-1
  • Linux7种文件类型
  • 米理 课程描述/学习计划/Study program
  • 2025年线路调压器厂家推荐榜:10kv线路调压器/单相线路调压器/三相线路调压器/助力电网稳定运行,优选品牌指南
  • Day15
  • 2025 智能/商超照明/灯具/灯光/源头厂家推荐榜:上海富明阳凭分区域光效领跑,生鲜 / 百货场景适配优选
  • 2025 艺考文化课推荐榜:济南震华学校 5 星领跑,全阶段体系适配基础补弱到高分冲刺
  • 2025 广州人力资源/派遣/劳务外包/人事代理/推荐榜:精典人才凭派遣合规 + 全场景适配领跑,企业用工优选
  • 2025 变电站厂家推荐榜最新资讯:撬装变电站/移动车载变电站/预制舱式变电站/移动变电站/预装式变电站/聚焦智能适配与可靠服务,这家企业成优选​
  • 题解:P12525 [Aboi Round 1] 私は雨
  • 完整教程:罗技G102有线鼠标自己维修教程
  • 挖矿-学校挖矿排查
  • 杂谈
  • 读书日记2
  • 鸿蒙hdc命令【杭州多测师】
  • 定位问题3:明明堆栈已经打印出来了,偏就是定位不出来?
  • Spring 统一机制处理 - 拦截器与适配器
  • 如何将海量纸质表格一键数字化?表格识别技术给出答案
  • 10.21 NOIP 模拟赛 T1. 小 h 学步
  • 深入解析:大数据Spark(六十六):Transformation转换算子sample、sortBy和sortByKey