AIME & AIOC 游记
这次是我第一次参加三题制的OI比赛, 感觉战术执行非常成功, 虽然四个小时的时间浪费了五个小时, 然是还是暴力打满了
2022/02/09
考了AIME, 题目比较有挑战性, 还好后面的第14题和第15题看起来完全不会做, 最后剩下半个小时对着完全不会做了两题莫名的思考了一下就去检查了, 所以时间也还算充裕
第8题和第12题都讲过类似的题目, 算了小一个小时就算出来了, 比较好玩的是第5题, 还好我在学校的数学课上认真听了物理的内容, 然后应用一下就做出来了, 感觉很趣味
最后得分是12/15pts, 应该算是不错, 算是做了热身
2022/02/10
进入了考场, 开始按照顺序做题
第一题读完题发现题目的意思是给一棵树, 每个点有一个权值, 求所有联通子图内权值和的最大值, 因此做法应该是
\[f[u] = \sum_{v \in \rm{Son}}\max(f[v],0)+p[u]\]
写了十分钟做出来了就去看第二题了(https://orac2.info/problem/aiio22hike/)
读完题发现了是个最短路径问题, 跑两次最短路然后显然上山时只在乎下山路反之也相同, 然后Dijkstra写错了调了半个小时发现没有带vis数组之后终于做出来了
然后就去看最后一题(https://orac2.info/problem/aiio22square/), 读完题发现是个不可做题, 就先打暴力\(O(n^5)\)了, 结果发现读错题了, 不是求数量而是最大值, 可能存在优化的方法
首先题目的难点是一共有 \(O(n^3)\) 种可能的正方形, 思考了两个小时不太会做, 发现时间要没了, 赶紧写了一个 \(O(n^3\log n)\) 的做法, 然后最后五分钟提交成功了, 其中发现数组开大了一惊一乍了十几分钟
最后得分是270/300pts, 应该是寄了
2022/02/20
Alpha比赛由于我莫名其妙很有自信, 没什么压力, 吃完饭就开始做题了
一共有四道题, 只有四个小时时间比较紧, 就抓紧看题了
第一题看起来不是很难, 写了写莫名其妙就过了
第二题看起来不是很难, 写了写莫名其妙就过了
第三题看起来不是很难, 写了写莫名其妙就过了
第四题是说有 \(n\) 个人, 在 \(l_i\) 到 \(r_i\) 天来庙里旅游, inclusive. 庙里有一个僧人, 僧人每天只能接待一位客人, 问使得每个人都能被接待 \(k\) 次的 \(k\) 最大是多少
写了写莫名其妙就挂了, 发现二分之后是个陷阱题, 对于 \(n\) 条线段来说, 它们本身意义是不大的, 而有意义的是它们所构成的交的线段的集合, 发现了题目的本质之后好像就做了出来
看起来是提前两个小时做完了, 就去睡觉了, 400/400pts
2022/03/03
因为感觉FARIO没什么用, 就不是很紧张
第一题是说有 \(n\) 个歌手拍成一队, 实力分别是 \(a_i\). 按照顺序从舞台左边进场, 右边出去, 其中歌手两两之间距离固定. 有 \(j\) 名导师, 可以看到 \(l_i\) 到 \(r_i\) 范围内的歌手, 然后每秒会给范围内实力最强的选手一分.
已知所有歌手每秒往右边移动一格, 求每个歌手的分数
发现导师的信息只有区间长度有关, 然后随便维护一下应该就可以了, 大概是一个二维的数据结构, 考虑到时间很紧凑, 我打算乱搞搞然后拿到了93分
第二题很难, 不会做, 就先跳过了
第三题是说给 \(n\) 个圆心, 要求构造一些圆, 使得这些圆互不相交, 并且周长尽量大.
题目看起来很乱搞, 但是往后读发现对答案精度要求很高, 就不知道怎么办了. 高斯消元和差分约束都不太适合这个场景, 因为互不相交这个条件是不等式.
但是尽然发现了是不等式, 其实也刻画出了数学模型,
\[ (x_i-x_j)^2+(y_i-y_j)^2 ≤ r_i + r_j \]
其中左边是常数, 右边是我们需要最大化的变量, 画图实验一下可以蒙到这个条件是当且仅当
然后写个线性规划就可以做出来了, 但是 \(n≤5000\), 而我写的是指数级的, 不太懂怎么优化, 就硬着头皮写了, 最后坚韧不拔的在坏掉的评测机上调试拿到了40.6分.
评测机坏了就顺便读一读第二题, 仔细读了读说的是有 \(n\) 个人排成一列, 实力分别是 \(a_i\). 每次选择最左边的三个人决斗, 留下中位数的那位玩家, 你需要维护一个数据结构:
修改 - 移动一个人的位置
查询 - 查询存活的人是谁
有一些部分分是只会修改前100个人和后100个人, 还有一个部分分是只移动一个人, 这些部分分都挺简单的, 可惜我前面花的时间很多, 后面花的时间很多, 最后就只写了后100个人的分
156.6/300pts
2022/03/07
问了问AIIO的奖项, 是银牌, 悲