首页 > 其他分享 >2025多校冲刺省选模拟赛3

2025多校冲刺省选模拟赛3

时间:2025-01-10 10:11:45浏览次数:1  
标签:le log 省选 sum 多校 然后 凸包 2025 我们

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} $ 。

image

如图,每条边表示两端相减的值,那么我们相当于要判断每一条红遍和对应的绿边依次相等,我们把它看成字符串,然后直接哈希判等即可。

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 集合,截一张网上的图:

image

两个黑色的区域分别是 $ A,B $ 粉色的是 $ C $ ,可以看做是两个图形,一个图形 $ A $ 绕着 $ B $ 的边界走了一圈,走过的点的集合 $ C $ ,很形象对吧。

那么怎么求呢?

首先凸包就是由两个凸壳组成的,那么我们只讲凸壳(因为凸包没写过,不敢胡)怎么做。

image

对于上凸壳,我们直接拿出两凸壳最左侧的两个点 $ x , y $ ,那么最终的凸壳里一定有 $ x + y $ 这个点,所以我们先把这个点加进去。

image

然后我们去比较他们俩连着的那条边的斜率,谁斜率大,就把谁及连着的那个点加进去

image

然后一直这样比较直到将所有的点的加进去

image

image

image

image

然后你就建完啦。

那么会了闵可夫斯基和能干什么呢?可以看到他就是用来快速的求两个向量集合相加后的凸包的,那么我们考虑分治,对于区间 $ [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

相关文章

  • 【2025-01-09】母亲的面
    20:00今天就该好好活下去。要珍重每一天。要爱每一天,尊重每一天,千万不要糟蹋一天,不要妨碍开花结果。                                                 ——罗曼·罗兰......
  • 2025 款 特斯拉 焕新版 Model Y All In One
    2025款特斯拉焕新版ModelYAllInOneTeslaModelYJuniper焕新版ModelY售价后轮驱动首发版¥263,500593 公里 续航里程 (CLTC预估)*5.9 秒 0-100公里/小时加速201 公里/小时 最高车速长续航全轮驱动首发版¥303,500719 公里 续航里程 (CLTC......
  • 【05】2025年1月首发完整版-篇幅较长-苹果app如何上架到app store完整流程·不借助第
    【05】2025年1月首发完整版-篇幅较长-苹果app如何上架到appstore完整流程·不借助第三方上架工具的情况下无需花钱但需仔细学习-优雅草央千澈详解关于APP签名以及分发-们最关心的一篇来了-IOS上架app背景介绍接第四篇提交了安卓商店后,需要等待审核结果,但是目前苹果上架我们......
  • [Arch Linux]系统安装教程2025
    #查看磁盘状况lsblk-f #进入xxx硬盘来分区cfdisk/dev/xxx 硬盘格式GPT新建EFI分区,300-500M,类型为EFI新建交换分区,类似虚拟内存,swap,通常为4G剩下全部为根目录分区,默认类型选择write,输入yes确定,quit退出#查看分好区的硬盘fdisk-l mkfs.ext4/dev/     ......
  • 【2025最新】渗透测试是什么?怎么分类?测试流程(超详细)是什么?
    一、渗透测试是什么?渗透测试是一种模拟黑客攻击的方法,通过对系统的弱点进行测试,以发现系统可能存在的安全漏洞。渗透测试可以帮助组织了解其系统的安全性,并采取必要的措施来增强系统的安全性。二、渗透测试怎么分类?(一)外部渗透测试和内部渗透测试。1.外部渗透测试:这种......
  • 程序员2025年新兴赚钱机遇:独立开发,通向财富自由的新路径
    引言随着2025年的临近,你是否也开始感受到“赚钱焦虑”的袭击?社交媒体上充斥着关于“经济寒冬”和“收入困境”的讨论,聚会中“副业刚需”和“财富自由”成为了绕不开的话题。在这个变幻莫测的时代,每个人都渴望找到一条可靠的赚钱之路。本文将为你揭示2025年极具潜力的赚钱方......
  • 2025最全Java八股文(完整版)
    问:抽象类和接口有什么区别呢?从方法编写方面,抽象类中可以抽象方法和普通方法,而接口中只能编写抽象方法。从继承和实现方面,抽象方法只能继承一个类并且可以实现多个接口,而接口可以继承多个接口。在变量的定义方面,接口只能定义静态变量,抽象类可以定义普通变量和静态变量。问:fi......
  • Java集合面试题集——2025最新大厂面试
    1.集合框架2. ArrayList和LinkedList2.1 源码分析成员变量<spanstyle="color:#000000"><spanstyle="background-color:#282c34"><codeclass="language-java"><spanstyle="color:#5c6370">//Defaultinitial......
  • [20250109]dbms_xplan.display_cursor+peeked_binds无法查看绑定变量值.txt
    [20250109]dbms_xplan.display_cursor+peeked_binds无法查看绑定变量值.txt--//在我使用自己写的dpc.sql脚本中我会加入peeked_binds参数查看绑定变量值,但是有时候会遇到无法查看的情况。--//以前自己很少关注这个细节,应该有别的途径获取绑定变量值,最近在优化一条sql语句正好遇到,......
  • [20250109]19c使用or_expand提示遇到的问题.txt
    [20250109]19c使用or_expand提示遇到的问题.txt--//生产系统使用19c,在使用or_expand提示时遇到的问题,在测试环境演示并做分析。1.环境:1.环境:SCOTT@book01p>@ver2==============================PORT_STRING                  :x86_64/Linux2.4.xxVERSION......