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

ABC424 游记(VP)

省流

前五题没什么难度,第六题恰好会,运气好 6t 没寄

9.23

内含剧透,请vp后再来。

不是题解!!!!!!!

赛前

下午下大雨没去图书馆,浪费了一下午,晚上准备 vp 一下 abc 和 cf,虽然但是最后只打了一把 abc。

赛时

A 题给了一个三角形的三条边,问是不是等腰三角形,直接判断有没有某两边相等即可。2min 通过。
B 题给了 n 个人和一个数 m,接下来给 k 行每行有一个人,如果一个人出现第 m 次就输出,按题意模拟即可。做 B 前调了一下翻译的设置,12min 通过。
C 题给了 n 个技能,每个技能有两个前置技能,必须要先学会其中的一个才可以学这个技能,问最后学了多少技能。发现这个题可以建图,每个技能从他的两个前置技能处连一条有向边,然后跑 bfs 即可。一开始我用 set 实现,在找到这个技能后把到他的另一条有向边也删掉,但很奇怪的挂了两发,后来改成标准的 vis 数组去看有没有走过就过了。总体来说有惊无险,不过此时时间问题比较大,已经 30min 才过,还吃了两发罚时,不过心态没有特别收到影响。
D 题要求在一个 7 * 7 的 01 矩阵里没有 2 * 2 的 1,问要把多少个 1 变成 0。一种很直观的想法是如果从左上角找到右下角,那么每次肯定删右下角那个 1,然而我们没有办法简单的确定一个左上方的定义,可能出现如
0 1 1
1 1 1
1 1 0
这样的情况,那么选择将这种做法推广。每次从上面一行往下去找,肯定只可能删下面的两个 1 中的某个,那么每两行最多删 6 个 1,时间复杂度上界就是 2^18,显然可过,大胆模拟即可。40min 正常通过。
E 题给了你 n 不超过 10^5 根棍,每根棍长度在 10^9 内,要求你每次操作把最长的一根棍平分成两根,操作 k 次,范围是 10^9,最后问你第 x 长的棍是多长。这道题刚拿到时看成棍的长度是 1e5,想着直接按长度统计然后模拟就行,感觉不对劲,仔细一看发现是棍的数量。但思路继续延续,一次掰断的棍还是同样长度的所有棍,那么最坏的情况就是 n 根棍互不相关,每次平分都要掰 n 次,但每轮对 k 减小的速度是以 2 的次幂速度增长的,那么只需要删最多 log(10^4) * 10^5 次就可以了,加上数据结构维护最大的 log 也可过,大胆模拟就过了。58min 没什么压力通过。
F 题给了一个时钟,上面有 1e6 个点均分这个圆,然后按顺序给你 3e5 个询问,每个询问给定两个点,如果这两个点间的连线与其他连线相交就输 no,否则输 yes 并把这条连线加到圆上。比较容易想到只需要判断两点连线间是否有某条线段的一端在里面,而另一端在外面。想到可以把每个加到圆上的点记录下来,然后判断中间出现点次数的奇偶性,这种做法适配线段树,于是开始码。码完后发现不能只判断奇偶性,因为如果出现偶数条线段的一端在要查询的区间内就会出现错误,于是要记录是否有特定线段连到外面,考虑使用异或哈希。如果两端都在里面或外面异或的结果就是 0,否则不是 0。稍微改动后交上去挂了一发,此刻只剩十三分钟,有一点点慌张但还好,静态查错发现是线段树异或的是点的哈希值,而不是询问的哈希值,修改后在只剩 3min 时通过,勉强可以算绝杀了。

赛后

这场题目难度比较偏低,但并不影响我做完 6t 就下班,以及打的比前几天 cf 都好得多。于是合电脑刷牙睡觉了。逐渐要开始 vp 区域赛备战,强度会越来越高,必须在这几天调整好状态。

2025年9月24日

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

相关文章:

  • Java实现大乐透历史是否中奖查询
  • 阿德勒的课题分离是很好用的东西
  • 别再混淆 PHP8.1 中纤程 Fibers 和协程 Coroutines 了 一文搞懂它们的区别
  • 主要测试的测试用例
  • 详细介绍Seata的AT模式分布式事务
  • VMware VeloCloud 漏洞分析:未授权远程代码执行全链条攻破
  • 【GitHub每日速递 250924】18 个 AI 投资大师齐上阵!这个开源对冲基金让你看透市场底牌
  • HJ9 提取不重复的整数
  • 2025年国家科技奖初评公布(科技进步奖)
  • 2025年国家科技奖初评公布(科技发明奖)
  • 12
  • 2025年国家科技奖初评公布(自然科学奖)
  • 近端策略优化算法PPO的核心概念和PyTorch实现详解
  • JAX快速上手:从NumPy到GPU加速的Python高性能计算库入门教程
  • Memento:基于记忆无需微调即可让大语言模型智能体持续学习的框架
  • 记录一次附加属性失效全过程
  • Java 与物联网(IoT):边缘计算与智能终端应用
  • 为你的数据选择合适的分布:8个实用的概率分布应用场景和选择指南
  • AI 落地应用最新工具集
  • 台风呢
  • Day07-C:\Users\Lenovo\Desktop\note\code\JavaSE\Basic\src\com\David\method-Demo041比较难
  • Markdown基本与阿法
  • 对称二叉树
  • 一例电动车充电器防反接电路分析
  • isEmpty/isNotEmpty/isNotBlank/isBlank-isAnyEmpty/isNoneEmpty/isAnyBlank/isNoneBlank
  • NetCore+Web客户端实现gRPC实时推送
  • 个人项目-论文查重
  • 个人项目作业
  • 软工第二次作业--王腾
  • 牛客周赛 Round 110 E,F题解