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

AtCoder Beginner Contest 422 游记(VP)

省流

很快过 \(3t\),D 题稍微卡顿,E 题一堆垃圾错误。

10.6

内含剧透,请vp后再来。

不是题解!!!!!!!

赛前

本来在补 \(2023CCPCHarbin\) 的题目,做到最小生成树那题大脑有点不够用了,就丢下开一把 \(ABC\)

赛时

AB 两题略过不谈,按照题意简单模拟就行了。用时 \(5min\)
C 题给了 A B C 分别的数量,要求三个三个组成组合。每个组合中要求至少有一个 A 和一个 B,问最多能组成多少组合。显然组合的数量受两个限制,一是 A 和 B 中较小的那个,二是所有数加起来除以三,这两个值取较小那个就行。\(8min\) 通过。
D 题要求你给出一个长度为 \(2^n\) 的数组,所有数之和为 \(k\)。然后求出最大最小值之差,然后把 \(i\)\(i+1\) 合并成一个,\(i\) 取所有奇数位,再求最大最小值之差,直到数组长度变为 \(1\),要求构造使得所有最大最小值之差中最大的最小。因为合并的操作不会改变总和,所以可以从长度为 \(1\) 的一个 \(k\) 每次翻倍去扩展,而想要最大最小值之差最小显然要尽可能平分,很好处理。我码的时候出现了难以预料的错误,不知道为什么,但稍微改了一点玄学的东西就过了。\(33min\) 以一发罚时通过。
E 题给了你 \(n\) \((n\leq5e5)\) 个点,要求你找到一条包括 \(n / 2\) 以上个点的直线并输出。一开始我想得是去算一下互质一类的东西,但发现线并不是一定要经过某个点就错了。后来注意到 \(n/2\) 的话随机选一个点很大概率就能在所需的直线上,于是随机选点然后查所有直线,看有没有符合的。再重复一些次数就可以了。我的做法先特判有没有水平或竖直的,然后查一个点正确的概率是 \(1/2\),而一次的时间复杂度是 \(nlogn\),用 \(map\) 统计 \(A, B, C\) 这条直线出现的次数,重复 \(n\) 次。其实时间比较紧张,使用了卡时。
在赛中交了很多次,都挂了,查出来了问题是一开始输出成了直线的法线,以及判断大小的时候多了个等号,但最后仍有一些固定点没有通过。

赛后

赛后花了四十分钟没看题解继续调,终于找到了 \(bug\),没输出 \(YES\)
然后看了题解,题解也是随机方法,但是他是随机两个点,恰好需要这条线的概率就是 \(1/4\),但是一次查询只需要看这条直线上有几个点,也就是 \(O(n)\),比我的做法更优一些。

2025年10月6日

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

相关文章:

  • 详细介绍:无人机光纤FC接口模块技术分析
  • 2025 --【J+S 二十连测】-- 第十三套 总结
  • 文件提供的基本操作
  • 深入解析:MySQL(50)如何使用UNSIGNED属性?
  • 迈向人机价值共生文明:AI元人文范式下的演化架构与协同治理
  • 10.6
  • 文件存储空间管理
  • 详细介绍:关于ios点击分享自动复制到粘贴板的问题
  • 新一代数据平台替代传统大数据技术栈
  • 攻击者如何绕过macOS内置安全防护机制
  • 在A列连续且相等行的最后插入空行,并求和
  • 10.6集训改错
  • @Prometheus 监控-MySQL (Mysqld Exporter) - 教程
  • AI元人文:走向人机价值共生的文明新范式
  • 实用指南:【机器学习基础】机器学习入门核心算法:层次聚类算法(AGNES算法和 DIANA算法)
  • CSP-J 第二轮集训 :总结 + 专题细分精讲_from_黄老师
  • ROIR 2024
  • 软件工程第一次随笔 - Nicholas
  • 深入解析:【数据库】关系数据库标准语言-SQL(金仓)下
  • Codeforces Round 1056 (Div. 2) (4/6)
  • 20251006
  • UV使用
  • 动手实验——mybatis generator
  • 学生管理系统面向对象分析报告
  • 荷兰青少年通过Telegram被招募,涉嫌参与俄罗斯支持的黑客活动
  • Moscow International Workshops 2017. Day 4. Lviv NU Contest, GP of Ukraine
  • 小代码使用npm包的方法
  • day18 课程(模块 )
  • Kubernetes(K8s)核心架构解析与实用命令大全 - 教程
  • mzoj 2025/10/6