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

10.4模拟赛总结

2025-2026 赛季 OIFHA 第三十四场 NOIP 模拟赛总结

一休尼(forever)

原题:CF5E Bindian Signalizing

长度为 \(n\) 的整数序列 \(a\) 。求整数对 \((i,j)\)\(i,j\in [1,n]\) 的个数,满足 \((i,j)\) 之间存在至少一条路径,使这条路径中的每个整数都不大于 \(min(a_i,a_j)\)

根据题目的性质很容易想到单调栈,赛时快速有了一个做法:从一个最大的元素开始顺时针遍历这个环,然后单调栈中的每个点维护权值和该权值目前出现的次数,每次遍历比较栈顶元素和当前元素的大小统计答案。

快速写完之后运行代码,发现每个大样例的答案都有小于等于 \(10\) 的偏差,之后进行了长达 2h 的调试和 hack,发现自己的实现会忽略部分含最大值的整数对,同时对于有多个最大值的情况也会出现问题,因此在 A 题上耗费了长达 2.5h。

中心(center)

给定一个由 \(n\) 个节点和 \(m\) 条边构成的带权无向连通图。图中的节点可以被视为城市,边可以被视为连接城市的双向道路,每条边都有一个表示其长度的权重。需要在此图中寻找一个中心点。这个中心点既可以位于图的任意一个节点上,也可以位于任意一条边的内部,以最小化所有节点到该中心点的最短距离中的最大值

这道题是在 A 没有调出来的情况下开的,想到了一个比正解多一个 log 的做法,首先使用 floyd 计算全源最短路,然后先考虑把中心放在节点上的情况,找到最优的城市,考虑在边上的情况,设与 \(u\) 的距离为 \(x\),则其到 \(u\) 的距离为 \(x\),到 \(v\) 的距离为 \(w–x\),对于任一城市 \(i\)
到中心的距离为 $$min(dis_{u,i} + x, dis_{v,i} + (w–x) )$$
整体目标函数为

\[f(x) = max_i min(dis_{u,i} + x, dis_{v,i} + (w–x) ) \]

此函数在区间 \([0, w]\) 上是凸的,可以用三分查找找到其最小值。

但是当时心情非常急躁,三分次数直接写了 \(60\) 次,在飞快通过了所有大样例之后没有意识到常数的巨大,最终导致了 TLE 60 分。。。

好的排列(center)

原题:P11316 [RMI 2021] 去 M / NoM

求将 \(n\) 对黑白石子(编号均为 1 到 \(n\))排成一列,使得任意相同编号的黑白石子之间的距离都不是给定整数 \(m\) 的倍数的方案数。

赛时没有花太多的时间推式子,花 30min 写了一个 30pts 的纯暴力。

\(1…2n\) 的位置按模 \(m\) 分组(位置 \(p\) 的余数为 \(p \mod m\));
对于每个余数组,预先计算从该组中选出 \(j\) 对满足“距离为该模倍数”(不合法)的方案数,式子为:\(C(x, 2j) \times (2j–1)!!\)

用背包把各个余数组组合起来,得到 \(F(i)\)(总共选 \(i\) 对不合法的方案数)根据容斥原理,不合法 \(i\) 对对应的贡献为 \(C(n,i)\times (i! \times 2^i \times (2n-2i)!)\);最后答案为

\[\sum (-1)^i \times F(i) \times C(n,i) \times i! \times 2^i \times (2n-2i)!。 \]

无限回忆(memory)

在给定树上,通过最优地设置 \(p\) 个存档点(必须包含起点 \(1\) 和终点 \(n\)),求从起点随机游走到终点的最小期望步数,其中每次移动等概率选择一个子节点,而走到“错误叶子”会传送回最近经过的存档点。

赛时没有时间看题了,赛后补了 50pts 的部分分,那个 dp 和 wqs 二分还没有看懂。

总结

这场主要存在的问题是 A 题在知道了做法之后花了太长的时间调试,严重影响了做后面题的进度和心态。

同时当在没有通过 A 题的情况下开后面的题,心态一定要平稳,尽量忘记前面的题目,这样才可以避免出现低级错误。

第四题没有时间写暴力也存在策略上的失误,但主要还是 A 2.5h + B 1h + C 0.5h 耗费了所有的时间。

本场模拟赛的理想得分: 100+100+30+50 = 280.

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

相关文章:

  • 01.linux基础
  • 英语完形填空
  • 2025整体橱柜厂家TOP企业品牌推荐排行榜,云南昆明整体橱柜全瓷砖,开放式厨房,经济型,一站式无烟柴火灶,嵌入式,智能,多功能,全屋无烟柴火灶整体橱柜公司推荐
  • Centos7安装mysql8
  • vite-vue3脚手架(参考帝莎编程-后台管理系统开发)
  • 上传文件的后端程序handleFileUpload()、getOriginalFilename()、UUID
  • 从模拟入侵到渗透测试:我摸清了黑客的套路,也懂了企业的软肋 - 详解
  • 同样的Python代码,在Windows上运行没有错误,在Linux Centos上运行出行错误。
  • FreeBSD 14发布后的技术问题解析
  • handleFileUpload()
  • 实用指南:Typescript高级类型详解
  • 集合幂级数,FMT 与 FWT 学习笔记
  • 2025多校CSP模拟赛1
  • 上传文件前端需要注意的三个点:
  • AT_arc189_b [ARC189B] Minimize Sum
  • Jenkins安装与配备
  • 2025-10-04 60S读世界
  • 适合新手的PPT模板网站,简单操作但效果好!
  • 2025多校冲刺CSP模拟赛2 总结
  • pip list 可以查到某个包,但是,import某个包,出现 ModuleNotFoundError: No module named
  • 详细介绍:conda使用指南
  • 探索 Docker/K8s 部署 MySQL 的创新实践与优化技巧 - 详解
  • 基于Registry搭建docker加速镜像服务
  • mssql 无锁读取
  • 2025年四川大学计算机学院专硕考研经验分享
  • 基础数学拾遗
  • 2025多校冲刺CSP模拟赛2(普通的颓唐)
  • 模板大全
  • springCloudMaven打包配置 - br
  • springCloud打包时根目录配置和公共包打包配置 - br