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