省流
很快过 \(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日