2025多校冲刺省选模拟赛3
神秘 IOI 赛制。
T1、 等差
因为是 IOI 赛制,所以赛时过了整整一车的假做法,包括但不限于什么写了两份假做法,一份发现后面的点 T 了,另一份发现前面的都 WA 了,但后面的过了,而且他们两个的并集等于全集,于是发挥了一下传统手艺,将两份代码拼在一起,然后就过题啦!
先讲一下我的假做法吧,就是你发现对于同样的长度 $ n $ ,如果 $ k $ 可以构成等差数列的话,那么 $ x k , x ∈ N_+ $ 都可以,于是可以用他来优化一下,求出对于每个 $ k $ 最长可以使他合法的长度是多少,成为 $ r_k $ ,然后判断答案时看看符合题目范围的 $ k $ 里 $ r_k $ 最大值是否 $ \ge i $ 即可。
上面的做法并不能真正的优化复杂度,只是让他大概率跑不满而已,所以我们需要更快的判断对于一个长度 $ n $ , $ k $ 是否合法。
这个东西应该只有 哈希 能做了。
我们正常去判这个东西的时候,应该是逐个抽出来 $ a_{i+1} , a_{2i+1} , a_{3i+1} ...... , i \lt k $ 每一个数列,然后去判他是不是等差数列,我们考虑转化一下,这相当于判对于每一个位置 $ i , i+2k \le n $ ,满足 $ a_{i} - a_{i+k} = a_{i+k} - a_{i+2k} $ 。
如图,每条边表示两端相减的值,那么我们相当于要判断每一条红遍和对应的绿边依次相等,我们把它看成字符串,然后直接哈希判等即可。
T2、 叉积
赛时先推了半个小时叉积是啥,然后 会了 $ n^2 $ 做法,写了个凸包,然后忘了特判 $ \Delta x = 0 $ 的情况 ,WA了 12 pts。
先说 $ n^2 $ 的,我们考虑最后答案是 $ ans = \sum_{i=l}^{r} b_{i} x - \sum_{i=l}^{r} a_i y $ ,然后整体除以 $ x $ 并移项,得到 $ \frac{ans}{x} + \frac{y}{x} \sum_{i=l}^{r} a_i = \sum_{i=l}^{r} b_i $ ,类似于斜率优化的形式,我们类比进行考虑,将 $ \frac{ans}{x} $ 当做截距, $ \frac{y}{x} $ 是斜率, 有点集 $ (\sum_{i=l}^{r} a_i , \sum_{i=l}^{r} b_i) , 1 \le l \le n , l \le r \le n $ ,我们直接把 $ n^2 $ 个点枚举出来将他们见一个凸包,然后直接询问即可(想要好写一点的话,可以分别维护一个上凸壳和一个下凸壳) 。
然后考虑怎么优化这个东西,维护凸包应该是不可避免的吧,但我们又不能直接枚举所有的点。然后需要用到一些神秘算法。
接下来介绍一下 闵可夫斯基和 :
先推一篇博客:wqs二分&闵可夫斯基和学习笔记
首先这个东西是用来求两个向量集合相加的向量集合,即 $ x ∈ A , y ∈ B , x + y ∈ C $ ,的 C 集合,截一张网上的图:
两个黑色的区域分别是 $ A,B $ 粉色的是 $ C $ ,可以看做是两个图形,一个图形 $ A $ 绕着 $ B $ 的边界走了一圈,走过的点的集合 $ C $ ,很形象对吧。
那么怎么求呢?
首先凸包就是由两个凸壳组成的,那么我们只讲凸壳(因为凸包没写过,不敢胡)怎么做。
对于上凸壳,我们直接拿出两凸壳最左侧的两个点 $ x , y $ ,那么最终的凸壳里一定有 $ x + y $ 这个点,所以我们先把这个点加进去。
然后我们去比较他们俩连着的那条边的斜率,谁斜率大,就把谁及连着的那个点加进去
然后一直这样比较直到将所有的点的加进去
然后你就建完啦。
那么会了闵可夫斯基和能干什么呢?可以看到他就是用来快速的求两个向量集合相加后的凸包的,那么我们考虑分治,对于区间 $ [l,r] $ ,每次我们解决跨过中点的那些区间,即 $ pre_r - pre_l , r \gt mid , l \le mid $ ,其中 $ pre_i $ 表示前缀和,这可以看做是两个向量集合相加的形式,于是我们可以 $ O(n) $ 的去解决分支的每一层,那么时间复杂度到这是 $ O(n \log n) $ 的,然后考虑维护了每个小凸包后我们应该把他们合成一个大凸包,如果实时合并的话需要二分,是 $ O (n \log ^2 n) $ 的,如果最后排序维护凸包的话也是 $ O (n \log ^2 n) $ 的,以及询问也需要 $ O ( q \log n ) $ 的,所以总时间复杂度为 $ O ( n \log ^2 n + q \log n ) $ 。
T3、 序列变换
不会,run了
\[return \ \ 0 \] 标签:le,log,省选,sum,多校,然后,凸包,2025,我们 From: https://www.cnblogs.com/GGrun-sum/p/18663426