Summary

2017

面试

在输入第i个人的身高的时候,使用双指针i和j对排序过的之前的身高数据进行遍历,使得i到j之间的身高差满足范围,相应地移动i或者j,减小或增加范围。最后判断出来能够囊括的范围是否大于m是多少。
这个在实现的时候,因为要拿到排序的身高数据,如果每次插入一个新的,就重新进行排序,用快排应该不会比较慢。那么可以就不用i和j两个指针,只需要考虑i和i+m(即直接考虑m个小孩)看看身高差距是否满足条件。

扫雷

大模拟

多项式求和

的时候
交换了次序, 是可以用拉格朗日插值在 的时间复杂度下求得,总的时间复杂度为
的时候,
后面的 可以用Abel求和来求
但是感觉这个实际代入 之后,并不能降低复杂度
在子任务中,有 的子问题有5个,这个应该说明给了给取 的特判进行求和的思路

2018

这个是 2018/7/13 的题目

思考熊的马拉松

明显,每个熊跑了的圈数为
套圈总次数每只熊超过之前的熊的圈数线下取整的和,但是这个是一个 的解,只能处理 10 个节点
可以抓住 的条件,说明每只熊跑的圈数都是整数,这个时候,可以预处理相邻两只熊之间的圈数,然后可以两两之间连线,然后看看每个之间,会有多少条连线所覆盖。如果有n个节点,那么第k个间隔之间会有k*(n-k)个连线
如果要处理所有的情况,可以按照圈数进行离散化,根据小数来进行判断,当前的小数为x,那么在之前如果有x~1之间的情况,说明这个熊并没有超过之前的那个熊,如1.7和3.3,3-1=2,但是0.3<0.7,说明在最后一圈并没有完全超过,实际超过的圈数为1。可以用Splay来统计这个到目前为止,当前的小数有多少是小于之前的。使用上面的减去这个就可以去掉没有完全超过的。

棋盘

大模拟
这里面有删除vector里面的某一个节点的需求,但是vector在遍历过程中进行删除可能会导致遍历出问题,用deleted的标记来进行处理

路径

dp[i] 代表第i个节点有多少条可行的路径,那么很明显有 dp[i] = sum(dp[j]*F(a[i]&a[j]))
但是这个时间复杂度是
这个是二进制的进行运算,可以试试按照位进行dp,可以把 a[i] 拆成每位的数相加,那么 F(a[i]&a[j]) 就是 F((q0+q1+q2...q_n)&a[j]) 这里就是看 a[j] 的某位上是否为 1,如果为1,那么就是dp[j],否则为0,因此可以维护第k位为1的a[j]的dp[j]的和s[k],这样可以转化求和方式,时间复杂度为

4

4个操作的那一题
查询第i个数到第j个数之间的序列是否存在三个或以上相同数
只会有0、1、2这3个数,根据鸽巢原理,可以得到如果长度大于6,那么至少有一个数的数量大于等于3了。最少的能够均小于3的总长为2*3=6,只需要检查长度小于6的时候是否是满足条件

2019

P1

按照着题目的要求直接算,时间复杂度为 的量级的
但是实际上可以用数位DP,OI Wiki上数位DP的第一个例题就是原题

P2

先用 求一个大致的解,然后二分出精确的解

P3

题目是说这个是可以同时进行实验的,因此按照拓扑排序,依次将入度为0的点加入到优先队列中,按照预期的结束时刻进行排序,然后在取出节点的时候,可以判断是否有子节点的入度变为0了,那么将这个节点再次入队。最后一个出队的就是最晚的时间
对于第二问,按照出队的时间逆向排序,对于已经是最晚的时间的了,那么可以开始的最晚的时间也就是可以开始的最早的时间。在上一问求出的是可以开始的最早的时间,在求最晚的时间的时候,也就是这个节点的子节点的最晚的开始时间的最早的值减去这个事件需要花费的时间,因为如果再晚,就会无法使得子节点完成任务。

T1 数据预处理

单链:没有度大于2的节点,并且不是森林
树:没有环,用并查集确定没有多个树
有环:并查集
无环:并查集

T2 积木

wp 是重量的前缀
相对的支持能力ra[i]=a[i]+wp[i-1]。一个积木最底下的横截面超过了重量,即wp[h]-wp[i-1] ≥ a[i],把wp[i-1]移过去,就成为了wp[h]≥a[i]+wp[i-1],这个左边是一个单调增加的,右边的可以维护一个单调队列,在每次添加一个新的砖块上去得时候,取出相对支撑能力最小的,可以判断出这个添加过的积木之后得整体是否超过了这个相对支撑能力,如果大于,说明是超过了承重能力的。
同时,需要注意到,添加了一个新的积木上去之后,原先就已经超重的积木只会越来越超重,因此超重的体积是单调增加的w

T3 蒜法

 

2020

统计次数

直接做就可以了,时间复杂度

2

统计每一行和每一列是否有两个或以上的点,如果有,那么就可以恢复该行、该列
恢复的过程中,可以添加到处理队列之中

3

背包问题
dp[i][j] 在节点i,剩余的代价为j的时候可以拿到的价值总和最大值

2021

二叉树

直接做,时间复杂度

发电

在工厂的数量为1的时候,用最短路,枚举发电厂,拿到最短的路径
工厂为2,发电厂为1的时候,以两个工厂和发电厂为起点,跑3次最短路,枚举图上的每一个点,作为分叉点,到3个点的距离最小

Quorum 机制

这个题目的题意看了example之后才知道
大模拟的题目可以在看看example之后久大致清楚流程了,可以进行操作
set以及multiset都是有序的,默认是从大到小的逻辑

2022

K叉树

用并查集可以判断是否是树
然后对于每一个节点,对于根节点,那么它的度全部都是儿子节点个数,而对于非根的节点,它的度是儿子节点个数+1
那么可以判断,是否有度大于k+1的节点,并且必须要有一个小于等于k度数的节点

我的世界

总k次方差

那么,排序之后,即有
可以把绝对值去掉了
第一行为
这里的求和展开方式可能也会影响判断
原本是按照距离进行展开,即
这里我就没有看出来有什么办法了,拆开来也不像上面的那样可以有一些合并

租约机制

大模拟,看完了样例也就可以大概知道过程了,一些细节的东西也可以有了了解
这需要进行排序,按照时间排序,并且相同时间写入在前,读取在后
数位DP