⏰ 格式
(1)按时间顺序
(2)标题加粗
【10.9周日】2/4 = 9k
第四题比第三题简单太多了,然后就是只要在规定时间内做出来第四题,就是能够达到2.7k的排名,做题的策略还是要有的✅ 就是有些时候就是第四题比第三题简单,这是自己策略的问题,就是要选好策略,就是不会的题目,或者思路卡住的题目,马上换题,真的特别重要的,第一次感受到就是第四题比第三题简单,就是直接gg了,所以还是需要就是注重做题的策略
最后时间只要专注最后一题,就是第三题就行了,这是自己面试的难度
(1)贪心题想到了就是很快,想不到这一场就是99%是想不到的,这就是现在的情况✅ 所以贪心题最多想5分钟,想到了就就是运气好,想不到马上放弃,贪心题的特点
1、
2、
贪心
交换律✅ 看y总的讲解视频
异或的前缀和,对res的前缀和
3、
字典序最小,就是首先保证第一个字母最小,不管长度,就是只要前面的字母小就行了✅ 正确的贪心思路:先把所有的a输出,然后把所有的b输出,然后再把所有的c输出,就是只要考虑前面字符的大小,完全不用考虑长度,这是字典序的题目的特殊的考虑方式
栈
(0)y总的贪心思路:
① 先预处理每个字符的最后一个位置,因为遍历每个字符的时候,需要找到最后一个位置,这是最重要的,因为当前字符是最小的字符,需要全部输出,才能输出第二小的字符,这是字典序最小的特征
② 这里只有26种可能,就是这个是经常在贪心题里面用到的技巧,就是对于字符进行遍历,就是只有26种可能
(1)我的贪心思路:
看右边有没有比当前字符更小的字符,直接依据这个来判断,没有的时候,就是弹出
❎ 相同的怎么处理,这个是这个题目的难点⚠️ 相同的没法处理
4、
Dp,就是玉米地的那个dp的升级版,主要就是mod的处理,单独做出来一维就行了
【10.2 周赛】3/4 = 7k
最后一题很难,前三题很简单
字符串hash经常作为综合题考察
✅ 连续两周的自己卡住的题目是dp了,就是这种只要求“最值,数量”的题目,优先考虑dp,dp真的是周赛筛掉后1k名的最好的知识点,因为贪心很难,基本上不可能想出来✨总结:以后碰到卡住的题目,只要是求最值、数量的,必然是dp,这是lc周赛的出题规律
(1)自定义dp的状态的话,就是一定要思考清楚细节:状态转移,状态初始化,这个是多做题才会有的经验
1、
⚠️ 基础课因数相关的题目 + 新做因数的相关的lc的题目,
2、
3、
Y总思路:
(1)对于k个1,就是填写上去的话,就是实际上是从集合里面选择k个数总和最小,所以就是选择k个最小的数就行了✅ 就是这个转换非常巧妙,就是每一位填1,本质就是加上或者减去一个数,就是排序就行了
我的思路:
分情况讨论,cfca训练很多,特别是贪心题,本质就是贪心的
(1)小于的情况,就是原来的1直接加上;从小到大填1
4、
Y总思路
(1)这里是一维dp,然后更新的过程是需要o(n)的
(2)这个是需要用后面的状态,来更新前面的状态,因为前面的删除的方式是固定的,就是相同的两个字符串删掉;后面是可以任意操作次数的,这个题目是思路比较新颖
我的思路:
Dp⚠️ 状态如何定义,如何转移
(0)✅ 这里f[i]是表示删除[i,n]这段需要的最大的次,因为这里只能是从前往后删除,就是枚举删除的长度j,然后以i为起点,然后去删除掉,所以这里f[i]的定义是定义i为起点,因为这里需要从前往后删除✅ 这是这个题目之所以是hard的原因,就是和常规的dp定义是不同的,就是套路的dp定义都是以i为终点的情况
① 我的本能的思路,或者说我做过的99%的dp都是以i结尾的情况,但是这里如果以f[i]表示结尾的情况,那枚举j的长度的话,那f[i - 2 * j]是没法更新f[i]的,因为就是我们不能先删除中间这段,再删除[1,i - 2 * j]这段,这是不符合题意的
(1)因为只有从前往后,就是这是线性的,天然符合dp的思路
(2)dp + 字符串hash✅ 思路是对的,细节还需要打磨
❎ 怎么贪心?没有找到相应的贪心策略⚠️ 很难在比赛想到贪心,除非运气很好或者题目很简单
思路路二:
从前往后考虑,就是找到最短的相同(字符串hash),连续字符串
(1)找到开头字母相同的位置,然后字符串hash算出来是否相同o(1) -> o(n)
思路一:
都是从前往后删除 -> 从后往前考虑
【9.25周日 周赛】2/4 = 5k名
第三题就就是其实很简答,但是自己思路没有对上,所以就是很难了
啊这,两题都能5028,我感觉第三题应该还是挺简单的,就是这么多人没做出来?✅ 主要是思路,就是子数组这种,绝对不能用单调队列和单调栈,优先适用dp,踩坑
(1)然后30min做出来第三题,就能有1k的排名的,错过了上分的
✅ 体会到了增量学习的好处,就是新学习的知识点影响到了旧的知识点,就是滑动窗口、单调栈的学习就是影响到了自己的就是dp的知识点的学习,所以人的本质其实也不是纯粹的增量学习,所以机器能够走到增量学习的话,是非常好的一个性能表现的就进步空间的
专注前三题,就是半个小时就行了,达到了自己的目的,最后一个题目,就是专注这十几分钟的
一个题目,一旦思路不对,就是第一个反应的思路不对,就是基本上就无了,就是这是lc的周赛的经验,就是关键是第一个思路,这是最重要的
1、
2、第二题
母题:归类到一起,就是数字的与或运算,y总说就是题目少,但是思维难度高
(1)a | b是越来越大;a & b是越来越小的
1、周赛是按位“与”的最大值的最大长度
(1)因为a & b <= a,就是必然是越来越小,就是每一位都是独立的,只有全1的时候才是1,才能保持这一位相等
最大值的最长连续的长度✅ 比上次双周赛就是简单
2、上次双周赛的题:
Y总答案:✅ 通过记录最近一位1,这个思路有点意思,就是有点类似单调栈的思路,找到最近的一位1
统计每一位1最近出现的次数,然后所有位数上最近一位1出现的位置的最大值,就是j的位置
❎ 我的思路:统计1的个数
(1)双周赛是按位“或”的最大值的最小长度?复习双指针
(2)或运算的话,a | b >= a 或者 b,就是越来越大的✅ 所以就是i固定之后,j越大,值必然是>=原来的值,这是单调的
代码:
(1)反过来遍历,就是只要有32位里面有减少到0的,必然就是
(2)不让他减少,这是正常的逻辑
3、
✅ 尝试了三个思路,终于秒掉了
(1)就是单调栈、单调队列的这个思路,本质缺陷就是没法保证长度为k的这个区间里面,都是连续递增的,这是这两个方法不行的本质原因✅ 果然做了才是就是能够确定这个思路是不行的
(2)dp的话,能够保证就是连续的递增的长度
(3)✅ 训练了单调栈、单调队列的使用,还是可以的,就是只要训练了自己ide手段就行了就是只要慢慢熟悉就像那两个
我的两种方法的本质是一样的?就是没法处理判断持续递增的情况,就是需要判断的是持续递增的长度
思路一:单调栈
⚠️ 单调栈的一个题目非常类似,回看这个题目和这个有什么不同的✅ 思路是一样的, 就是找到最长的长度,然后比较是否是>=k,就是直接看最长的长度
不能这样做,因为你right[i + 1]只保证了就是开头和结尾,但是不能保证中间是单调的
思路二:滑动窗口✅ 这种窗口大小的,天然适合滑动窗口的
控制窗口大小是k,然后保证窗口k里面都是递减的,或者递增的
窗口大小>= k,设置成true
⚠️ 滑动窗口可以做吗?因为有K大小
(1)队列为空的标
✅ 需要保证的是窗口里面完全单调递增,这是这个题目的难点❎ 就是怎么用单调队列实现⚠️ 有样例没有考虑清楚的
❎ 单调栈只能保证首尾就是大小关系;滑动窗口可以保证窗口内的大小关系,是更加扶着这个题目⚠️ 单调队列里面也没法保证就是完全的顺序,就是左边的23比右边的数字都大,但是并不能保证就是整个区间都是递增的
① 就是a[i],只有就是队列里面的元素是上一个,然后弹出上一个,这样才能保持连续
✅ 思路三:dp
正反向(前后缀分解)做一遍dp,直接秒了
(1)本质就是那个单调栈题目里面用的技巧的,就是左右各扫描一遍
✅ 因为dp是能够保证就是是子数组就是连续,所以直接就是秒了
⚠️ 思路是在一个单调栈的里面题目学到的,就是还是有价值的
4、
思路一:
树分治的简化版
(1)⚠️ 找到树的重心,提高课
思路二:
Lc里面写的比较多的:树的遍历,并查集✅ 思路要往这个方向去靠
套路题
⚠️ acwing = https://www.acwing.com/problem/content/348/ = 提高课做过了,最小生成树的扩展应用
并查集,类似求最小生成树的做法,kruskal推导过程的扩展应用
(1)将点按照从小到大排序,然后逐步合并两个点,只要合并<=x的点
(2)当把<=x的所有点都处理好之后,看下每个x在哪个连通块里面,
① 因为这里并查集里面只加<=x的结点,所以会导致图就是不连通,是分成多个连通块❎ 整体就是连通的,所以最后所有相同的点必然是在一个连通块里面,只有一个连通块把,任意选择两个点 + k
代码:
(1)q里面存的是vals数组的下标;然后建图之后,图里面结点的值也是下标✅ 因为给出来的边的数组,就是下标之间的关联
(2)✅ 用并查集来维护值为x的集合,并且把x出边中所有值小于<=x的点加入进来,就是加入到并查集
① 这个公式非常的优雅,就是把x的数量 = 1,和x数量>=2的情况都包含进去了
(3)sort只能定义小于号,不能定义<=,否则就就是会有匪夷所思的buffer overflow的问题的
【9.18周日 周赛】3 / 4,9k名
签到题比双周赛简单多了,真的是周赛确实比双周赛简单很多✅ 专注自己每次双周赛的机会,因为难度确实是自己就是体会到自己当前水平所有的竞赛的天花板,只要能够适应双周赛的难度就行了
自己写完上双周赛,就是把周赛就是思考得太复杂了,就是字的第三题就是思考得没有思考清楚是交换值,所以就是写的太辣鸡了
提高课的好处,就是我看到所有题目考察的知识点我都是会的,就是数位dp、字典树之类的,就是我可以节约自己母题专题训练复习的时间和精力,这是我感学完提高课最爽的地方✅ 这里深刻体会到了就是算法提高课的作用,就是竞赛是为了复习算法提高课系统训练的东西,就是无死角,只要时间够长,绝对是无死角
没过的话,就是提交错误的不算,有点意思
只要能够复习字典树就行了,就是当做游戏就是补充自己的技能,这是自己应该有的心态✅ 就是把心态弄好就行了
1、
2、
连续字符数组
(1)双指针
+1
不同就是指针跳过来✅ 简化版的双指针的题目
首尾差 = 长度
(2)❎ 二分
3、
完全二叉树
16384 = 20000各结点,10^4
(0)考察bfs的按层遍历,手写栈
① 系统的stl怎么实现 = 广度优先搜索的每一轮中,我们首先记录下当前队列中包含的节点个数cnt,即表示上一层的节点个数。在这之后,我们从队列中依次取出节点,直到取出了上一层的全部cnt个节点为止。✅ 变量记录上一层的个数
(1)如果是奇数层,单独放在一个数组,然后reverse之后,直接修改值
⚠️ 换结点的值就行了,这个简单很多,就是只要交换结点的值就行了,就是前面思考得太复杂了
Y总:dfs
(1)左边子树按照LNR遍历,右边子树按照RNL遍历
① 这样当前左边遍历到L的时候,和右边遍历到R的时候的两个点,就是需要交换的两个点;同理左边遍历到R的时候,右边遍历到L的时候,也是需要交换的两个点✅ 这个思路好像在镜像二叉树里面见过
(2)如果是奇数层,直接对换两个点
✨总结:只有二叉树才能这样镜像交换遍历,
4、
字典树⚠️ 母题专题训练复习
(1)预处理每个结点作为前缀的数量
(2)遍历的时候加法处理
方法是对的,就是极限情况下没有通过,
代码:c静态成员,就是声明之后,可以节约空间,就是保证通过
(c静态成员变量)
✨一个类的所有对象,对于静态成员变量是共享的,所以只需要存一份静态成员变量就行了
静态成员是属于整个类的而不是某个对象,静态成员变量只存储一份供所有对象共用。 所以在所有对象中都可以共享它。 使用静态成员变量实现多个对象之间的数据共享不会破坏隐藏的原则,保证了安全性还可以节省内存
(0)有一个类变量改变了静态成员的值,其它类的成员变量test都会发生改变 + 通过验证可以得到静态成员变量内存在生命周期里对于所有类变量来说共享
(1)声明类的成员为静态时,这意味着无论创建多少个类的对象,静态成员都只有一个副本。
(2)也就是数据共享,就是一个对象修改了,后面对象也会知道
在定义类的时候不能对成员变量赋值,因为类只是一种数据类型或者说是一种模板,本身不占用内存空间,而变量的值则需要内存来存储。
静态成员为所有类对象所共享,不属于某个具体的实例
静态成员变量必须在类外定义,定义时不添加static关键字
(1)或者在类内定义,用static关键字
静态成员在类的所有对象中是共享的。如果不存在其他的初始化语句,在创建第一个对象时,所有的静态数据都会被初始化为零
(1)在类的外部通过使用范围解析运算符 :: 来重新声明静态变量从而对它进行初始化
静态成员函数只能访问静态成员数据、其他静态成员函数和类外部的其他函数。
【9.17周六 双周赛】
yxc直接就是no1,还是有实力的,就是天赋还是厉害的
1、
Y总思路:✅ 两个知识点都要清楚,才能一分钟ac
(0)统一转化为天数,就是每个日期用这一年的第几天来表示
(1)两个日期之间的天数
① 区间求交问题问题,公式:https://www.acwing.com/problem/content/1763/
我的思路:
先排序,就是左边是小的
纯模拟题,就是看细心程度,有点类似PAT的签到题,还是有点难度的
2、
Y总:
(1)贪心,因为保证小的worker能够尽量匹配小的trainer,就是从小到大
我的想法:
建立图⚠️ 这里就超时了,就是如果全部都有就建图的时候赢超时了
匈牙利算法✅ 竞赛考察两次了,会就是很快,不会就是很难受
(1)复杂度实际上为 O(n1^2×n2),这表明当两侧的点的数量相差悬殊时,应该选择点较少的一侧作为男
① 男生n1遍历一遍,
② 每个男生有n2个女生 = 对所有女生的查看状态st清空,因为要所有女孩都能遍历
③ 然后每个女生有n1个男生,相当于判断三次
3、
必然二分或者双指针,二分细节比较多,双指针思路比较难
Y总:
(0)思路关键::
或的话,每一位是独立的,因为逻辑运算的操作,二进制的每一位都是独立的,就是每一位单独考虑
✅ 全局的最小值,其实是所有位的最小值的最大值,这是独立情况求最小值的方法
(1)双指针
固定区间的起始端点,求出每一位满足条件的最小值,然后里面的最大值就是要求的位置
(2)分情况讨论:
对于i,如果当前第k位是0,那就是j = i;如果当前第k为是1,然后后面没有1,那就是j = i;如果当前第k位是1,然后后面有多位1,那就是只要距离i最近的1的位置t,然后j = t,保证满足第k位上,区间最小
我的想法:
(1)二分
子数组,连续的区间,就是本质就是两个点,就是天然的二分或者双指针✅ 就是确定区间的一个点
(2)与或非对于数字的操作,一般是操作为数组,就是前缀和,因为一般是10^9,所以就是32位二进制,就是这样就是可以用32位,就是真的是挺爽的,就是相当于有一维度是常数
代码:
(1)10^9 < 2^30,也就是最多30位
或的话,每一位是独立的,因为逻辑运算的操作,二进制的每一位都是独立的,就是每一位单独考虑
4、
答案:
(1)列出来不等式,就是分为两块,关键是左边这块的最大值,是所有正数相加,保证任意顺序下的最大值这✅ 关键是列出这个右边的式子,然后贪心得出他的最大值
(2)对于当前这笔交易,如果在里面,就是需要先减掉,然后再加上item[0];如果不在里面,就是直接加上item[0] = 最大的消费
① 处理单独元素的方法,先减掉,然后再加上单独的项,这样逻辑会清晰很多
✨回想类似的题目:cfca 1707A
(1)这个题目是保证从前往后顺序可行,就是当前顺序就是从后往前是可以的,就是贪心找到满足后面序列的最小值,从而决定当前的这个constest选择或者不选择,就是不要透支未来,可以从未来回看考虑 -> ⚠️ 这个题目是任意顺序,所以就是需要贪心找到等式的最大值,就是利用正数相加,负数就是完全不考虑的情况下,就是最大值,这个点是最难贪心的
❎ 我的思路:⚠️ 完全没有思路,贪心题
最坏情况下能够保证就是完成,那肯定就是最少的钱数
(1)先做差值最大的
dp
【友塔游戏-9.16周五笔试】
还是挺有难度的,就是有点类似高考,就是多个知识点的综合,就是每个题目至少考察了两个知识点,这个确实是让人很难受,确实也是综合题,就是比周赛要难一点,但是除了第四题,前三题基本上知识点都是知道的,就是关键是代码实现,特别是第二题,这个还是需要总结的 = 双周赛的题目,需要两种或以上的算法联合一起使用
✅ 双周赛这是自己要做的事情,就是真的是自己要做的就是事情的
T1
贪心⏰ 但是只过了1/8的样例,很奇怪
T2
高精度四则运算
栈模拟表达式,分数表达式
(1)比小数转分数的这个题目还是要简单一些
T3
最小生成树
(1)prime算法,并查集✅ 因为并查集系统训练过,所以就是真的是非常的内化了
(2)kruskal⚠️ 母题专题训练
T4
网上搜索不到答案,这种野题比赛,就死以后不参加了,浪费是阿金,就是做了止呕没法补题,这是最难受的✅ 就是一定要做就是有官方题解,或者就是有很多人参加的比赛,机试泽阳自己弥补自己ide漏洞也是方便很多的
❎ 求出任意两个点的最短路,然后就是按时间遍历,看下当前两个点的最短路的 <= 两个点的时间间隔,就是说明可以到达⚠️ 这种方法不行,因为后面可能有更近的点,就是你当前走的这一步可能就是收获到了A,但是可能距离后面的三个东西就更远了,从而就是没法获取到
⚠️ 只能暴搜了,就是不断的重复⚠️ 终止的条件不知道,就是没有收集玩就一直循环
(1)100个格子,搜索或者不搜索,一共就是有2^n,就是肯定会超时
样例:
4
1 1
4
2 2
2 3
3 2
3 3
4
1 2 1
3 1 4
4 2 4
7 3 4
ans = 3
【9.11 周日 310场周赛】3/4 = 3k名
自己平时就是做到自己的极致,就是机会来的时候,关键就是看你过去的积累,就是你没法预测,但是你能够做好你当前的每个时间啊in快,这是最重要的
1、
判断偶数,x & 1 == 0,还是!(x & 1)
Sort函数的编写,第一个属性的所有情况都要写出来
2、
经典双指针,刚好训练了一周的双指针
3、
比赛里面做过的第三遍了,做过无数遍了,最深刻的是PAT
4、
答案:
(1)初始的dp状态定义
(2)线段树优化找到区间[a[i] - k,a[i] - 1]的的最大值,就是通过线段树logn找到✅ 就是用提高课的数据结构硬优化,就是这么猛,提高课的数据结构就是这么猛
我的想法:
方法一:
Dp + 滑动窗口
(1)做过类似的,就是用滑动窗口,保证状态更新是o(1)
❎ 双指针
方法二:最长上升子序列的方法二,也不行,因为二分之后
(1)https://www.acwing.com/solution/content/137435/ 这个题解解释得很清楚就是为什么不能用
【9.4周赛】3/4
⚠️ 竞赛和lc的区别,和数奥和高中数学的区别,高数以考基础为主,数奥以考技巧为主,就是考察的重点不同⚠️ 第四题是对于面试来说很难,但是对于竞赛来说还是比较简单
(1)想要技巧,首先基础要非常扎实,所以就是技巧是在基础之上的 + 思维是技巧的一个重要的来源
(2)你需要就是能够快速的学习好基础的知识,这是作用的
⚠️ 只要做到自己的极致就行了,就是三个题目就行了,这次排名太惨了,就是WA了太多次,一次五分钟
⚠️ 做多了综合题,就是才能思维更加清晰有条理,这是很重要,就是对于二分的使用场景很熟悉之后,就是可以在这个基础上去优化
✅ 第三题已经是很多公司笔试的难度了,就是能够做出来已经算很好了
1、
Unordered_map或者set,都是用find(val) == .end()来判断是否存在,
2、
数值的范围,就是最好开大一点,特别是边界情况,直接WA了六次✅ 教训,就是dp的状态,对于这种有移动的,一定要就是特别注意
✅ 这个是区间dp,就是自己真的是能够想到先更新区间长度,然后是点,这是因为区间长度小的更新区间长度大的
代码:y总
(1)直接就是让start,end就是先变成正数,就是直接 + N,这个是厉害的
3、
✅ 二分 + 二进制存储,就是两个单独的知识点都训练过,然后综合起来
一个数组是优雅数组,那他的子数组也必然是优雅子数组✅ 这是回文串里面学到的 -> 二分
Vector<>在前面加一个元素,方便求前缀和
读错题目:✅ 任意两位与起来等于0❎ 与上的结果,所有位都是0;反过来就是只要有一位是全1,就不会出现0的结果❎ 不是所有的数与起来等于0,而是任意两位,思路是一样的,任意两个
(1)做过了,就是二进制的那个加法,就是那个三数的那个,就是统计二进制位置上的1
方法二:双指针还行,就是也是保证了就是right往右边移动,那left也是往右边移动,利用的是一个性质
4、
堆,默认是大根堆,这是最特殊的地方
会议是用开始时间来排序
房间是用堆来维护,记录的是结束时间
⚠️ 当前的这个meeting时间都大于所有的这个room,才是选择结束时间最早的;如果start的这个时刻有空的,那就是选空的里面的最小编号✅ 用两个堆,因为有两种情况,处理会议室空闲和占满两种情况✨对于空闲的会议室,就是直接看编号就行了,就是因为都是能够用的,当没有空闲的,就是找满的里面的结束的最小值,这个是思考的一个漏洞的,就是空闲的是只看编号,不看它什么时候空闲的
(1)当有会议空闲的时候,需要在空闲的会议室里面找到编号最小的会议室
(2)当有会议室沾满的时候,需要找到一个最早结束的会议室
✨总结:关键就是空闲会议室,是完全不看前面任务的结束时间,只看编号,所以就是通过两个堆来分别存储using、empty的room,这是数据结构体的考点
【8.28周日 lc周赛】3/4 = 1h写出来
⚠️ 三题做的太慢了,就是明显思考得很慢
⚠️ 第四题,只有一千个人过了,已经很多了,因为正常的是800个人,正常难度,但是过了三题只有1w多名✅ 第四题才是分水岭,就是突破3k名的分水岭✨总结:稳定三题,冲第四题,这是22年下半年要做的事情
(1)第四题关键知道考什么,知道考什么瞬间就能写出来
1、
Sort这一下就是贪心
2、
⚠️ 手写栈,循环栈就是不断的循环,就是超过了就是循环
⚠️ 循环队列
3、
整体思维,感觉cfca做过类似的
4、
✅ 答案:
(0)✅ 顺序限制,一般用topsort,最经典的就是课程先后顺序的课程表,就是经典的topsort,记住这种经典的应用场景
(0)贪心:因为行列各有k个,所以每个点可以行列均不同,这样就是行列独立的✅ 找出行顺序之后,列其实可以任意放,都不会影响已经确定的行的顺序;然后找到一种符合要求的列的顺序就行了
(1)topsort:(a,b)顺序表示一条有向边,就是a -> b,最后需要给出一个拓扑排序,就是包含所有点的拓扑排序的序列,只要确定所有点的拓扑序列就行了
代码:
(1)topsort的板子,就是bfs的板子,只要记录每个点的入度就行了 + ✅ 时间复杂度是nlogn
(2)重边和自环,这是图问题的两个常见边界
(3)用return{},来找到报错的地方,就是和注释的效果是一样的, 就是写起来更方便
❎ 我的想法:模拟 + 类似并查集维护限制条件✅ 不是并查集,这里向上的有多个
(1)根据condition构建一维数组 -> 并查集,带权并查集,路径表示距离,距离相同的点,在一个x的一个范围里面
① 1;[2,2 + count(同一层的结点数量)]
(2)有了每个点的x坐标范围和y坐标范围,就是任意取其中的一点就行了
【8.25 周四 微软笔试Test4】
1、
❎ 字符串hash应用在int范围内的整数,就是o(1)时间取值
⚠️ 正数必然是删除前面的5,负数删除的后面的5
s.substr(1)表示从位置1开始,一直到结尾j
2、
(1)区间和,大概率转换成前缀和 -> 就考察前缀和转换题意
① 比sliding window做的那个T2398里面的sum处理要简单很多
(2)sum[0] = 0也算一个元素,这个9.6周二的sliding window里面刚做过,就是前缀和转换的问题,sum[0]也是前缀和数组的一个元素,经常忽略,这是编码的一个细节
❎ 好像做过,就是双指针,因为小于0的时候,⚠️ 没有单调性,没法双指针
❎ 感觉好像做过,但是又感觉有点陌生
3、
一段区间如果是stable的,那他的子区间(元素个数>=3)必然是stable的,就是双指针统计连续相同的区间长度,这也太简单了
(代码)
1、
#include <iostream>
using namespace std;
int main(){
string s;
cin >> s;
int res = 0;//最后的结果
bool flag = true;//正数
if(s[0] == '-'){//负数
flag = false;
s = s.substr(1);
string tmp;
int n = s.size();
int i = n - 1;
for(;i >= 0;i--){
if(s[i] == '5') break;
tmp.push_back(s[i]);
}
i--;
while(i >= 0){
tmp.push_back(s[i]);
i--;
}
//计算结果
for(int i = tmp.size() - 1;i >= 0;i--){
res = res * 10 + tmp[i] - '0';
}
}else{
string tmp;
int n = s.size();
int i = 0;
for(;i < n;i++){
if(s[i] == '5') break;
tmp.push_back(s[i]);
}
//i是指向5的位置
if(i + 1 < n) tmp += s.substr(i + 1);
//计算结果
for(auto c : tmp){
res = res * 10 + c - '0';
}
}
res = flag ? res : -res;
cout << res << endl;
return 0;
}
2、
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 100010,MAXV = 1e9;
int n;
vector<int> a = {2,-2,3,0,4,-7};
// vector<int> a = {2,-2,3,0,4,-7};
LL sum[N];
unordered_map<LL,int> h;//h[x] = cnt
int main(){
n = a.size();
h[0]++;//sum[0] = 0也算一个元素,这个9.6周二的sliding window里面刚做过,就是前缀和转换的问题,sum[0]也是前缀和数组的一个元素,经常忽略
for(int i = 1;i <= n;i++){
sum[i] = sum[i - 1] + a[i - 1];
h[sum[i]]++;
}
// for(int i = 1;i <= n;i++) cout << sum[i] << ' ';
// cout << endl;
LL res = 0;
for(auto item : h){
int cnt = item.second;
res += (cnt * (cnt - 1) / 2);
if(res > MAXV){
cout << -1 << endl;
break;
}
}
if(res <= MAXV) cout << res << endl;
return 0;
}
3、
#include <iostream>
#include <vector>
using namespace std;
const int MAXV = 1e9,N = 60010;
typedef long long LL;
vector<int> a = {-1,1,3,3,3,2,3,2,1,0};
LL cnt[N];
//递推推导,o(len)
// LL cal(int len){
// LL res = 0;
// for(int i = 3;i <= len;i++){//区间长度
// res += len - (i - 1);
// }
// return res;
// }
//递推预处理
void init(){
for(int i = 3;i <= N;i++){
cnt[i] = cnt[i - 1] + (i - 2);
}
}
int main(){
init();
int n = a.size();
if(n <= 2){//元素不够3个
return 0;
}
vector<LL> b(n);
for(int i = 1;i < n;i++){
b[i] = (LL)a[i] - a[i - 1];//记录d
}
// b[0] = b[1];//前两个位置的d必然相等
//双指针找连续相同元素的区间
for(int i = 0;i < n;i++) cout << b[i] << ' ';
cout << endl;
int i = 1,j = 1;
LL res = 0;
while(j < n){
while(j < n && b[j] == b[i]) j++;
//j指向第一个不相同的位置
//[i,j - 1]是相等的一个区间
int len = j - 1 - i + 1;
if(len >= 2){//len >= 2,则[i - 1,j - 1]的区间元素个数>=3,合法的
// res += cal(len + 1);
res += cnt[len + 1];
if(res > MAXV){
cout << -1 << endl;
break;
}
}
//更新坐标
i = j;
}
if(res <= MAXV) cout << res << endl;
return 0;
}
【8.21 周日 kickstart E轮】
【kickstart E轮 8.21】
前三个题目思维还是挺简单的,就是感觉就是lc周赛的前三题的水平,果然就是最后几场就是难度下降了很多
做完两个题目就会3.5k了
怎么突然笔试题目这么简单,就是思路基本上都是暴力解法,有点奇怪
1、
Cfca题目,想到一种固定的构造方法
✅ 向上取整,就是这种序号的方法,就是最保险的方法是向上或者向下取整,❎ 就是绝对不要n / 4 + 1,这是非常容易发生的错误
2、
对于每个元素10^5,找到<=2 * Ri,的最后一个数,set的
⚠️ 怎么忽略当前元素,找到剩下的里面最后一个的<=a[I]的值✅ 记录位置信息,如果找出来的数位置 == I,就找左边的这个
Set不支持随机访问,不能用二分
3、
不用实际弄出来,就是把添加的当做xxx,万能符号匹配就行了
✅ 题目:Q也必须是palindrome,palindrome string Q
(1)微软笔试的时候也看错了,就是pair,应该是两数之和
✨总结:自己的英文读题,就是卡住的地方还是要翻译一下,就是用google翻译
❎ 样例错了?结束之后查一下论坛的讨论
⚠️ 要做到o(n),就是用o(1)时间判断两边是否是回文串✅ o(1)时间判断是否是回文串,字符串hash的板子
(0)字符串hash,就是可以用o(1)的时间去判断✅ 这是palindrome的一个利器
(1)❎ 马拉车算法,当时没有学习https://www.youtube.com/watch?v=5U-qKyTPLX4⚠️ 直接字符串hash也可以判断,就是线性判断
⚠️ 复习字符串hash的使用场景
(1)⚠️ 复习palindrome的常用公式,主要是dp
(2)字符串hash,o(1)判断是否是hash
4、⚠️ 三维dp需要找题目母题专题训练
经典的dp问题
三维dp
【8.21周日 307场周赛】3/4 = 1h
✅ 残酷群只有46个人ak,说明就是最后一题还是挺难的,就是自己能够用自己的中等题的两题就是做完就行了,就是自己能力范围的极致了,这就足够了;y总100+名
稳定在3.5k名,就是这是需要通过系统训练突破的
✅ 思路还是比较universal,就是写起来有点复杂✅ 比赛竞赛就是要写的块,就是写的块才是真理
⚠️ 两个medium都在微软的笔试题里面做过,就是果然平时积累很重要,出题人肯定是做过了微软的笔试
Lc的比赛的时候的测评,明显快了很多,就是这是他故意就是在平时的题目放慢,就是让你开会员
1、
❎ enegy是sum - init✅ 保证每个都是足够时间的,就是遍历一遍
2、
微软的原题
Lc的样例还不完整, 就是微软的样例还是完整的,少了很多坑
✅ 有了微软的样例,就是解决得还是挺顺利的
3、
⚠️ 复习:树的结构的定义✅ 碰到一次复习一遍
(1)默认的状态下,要给初始值;
(2)给了定义的参数的,要传入;其他的也要给初始阿虎✅ 就是初试化方法,就是所有的属性都要给初始值
❎ 建树⚠️ 给的是根节点
只定义了二叉树的结构,重新建树
(1)除了固定的遍历,其他的都直接用数字,就是 != -1
Dfs找到最大深度
✅ 找最大深度,就是可以用bfs,这是bfs擅长的,就是求最大的深度
4、
完全没有思路
⚠️ 复习:第k个,k-th elements = 快速选择 = 应用场景 + 套路
答案:
(1)acwing的序列是母题,⚠️ 多路归并,属于贪心的一种
① 周赛题目,是从2^n个值里面取出最大的k个值
② 对于当前的a[i],前面的2^(i - 1)种情况从小到大已经排序;加上a[i]之后,还是2^(i - 1)种情况,从小到大排序 -> 合并两个有序序列,就是二路归并,组成2^i个数
② 因为求前k大的数,所以就是保留前k大大的数,然后就是每加入一个数就做二路归并之后,还是保留前k个数,一次二路归并时间复杂度是o(k),一共是o(nk)
③ 从和的角度反过来考虑,就是最大的和必然是所有的正数相加 = sum;然后前k大的和,必然是sum - (前k个靠近0的数),这样产生的和是前k大的✅ 贪心了一下,就是从最大数 - 前k小的数来考虑,就是减或者不减,就是有两种情况,从而二路归并
代码:
(1)sort(q.begin(),q.end(),greater[HTML_REMOVED]());//从大到小排序
(2)vector的删除操作:b.clear();a.erase(a.begin() + k,a.end())
✨总结:用二路归并去考虑数组的序列选择,思路很新,就是选或者不选a[i],从而有两个序列,合并两个有序序列
【8.19 周五 微软第三次笔试】
1、
Set的遍历,就是 p.next,就是下一个指针
S.find(x)是一个查找元素的操作✅ 有序,查找是logn的
s.lower_bound(x),
2、
⚠️ 回文串的两个公式,复习一下 = dp公式 + 字符串hash + 插入字符的处理方法
⚠️ 可以打乱顺序,感觉做过类似的,就是cfca里面感觉做过,贪心✅ 周爱出国
(1)奇数个数也是先放到只剩下一个,最后中间的是最大的那个数字
思路:
(1)hash记录每个数出现的次数
(2)偶数个的先放小的,最后放大的;奇数个的先放小的,再放大的
代码:
(1)string(2,’c’),先个数,再字符
3、
车尽量多
主干路的边,尽量一辆车
思路:
(1)计算每个点的每个子结点的个数,就是a -> b这条边需要花费的权值数量就是个数 / 5上取整
(2)本质就是dfs统计结点的个数
⚠️ bfs记录parent的信息
⚠️ y总存储的方法,无向图的这种存储怎么判断叶子结点?✅ 又考到了,就是周赛考到了
(2)~h[u] || ~ne[h[u]]
① 这个题目就是树,就是树的根节点要特判,就是u != root && (~h[u] || ~ne[h[u]])
(1)必然然有一个结点,必然有边的情况下
1、
set的遍历,是双向迭代器
#include <iostream>
#include <vector>
#include <set>
using namespace std;
vector<int> x,y;
int w;
int main(){
// x = {2,4,2,6,7,1},y = {0,5,3,2,1,5};
// w = 2;
// x = {4,8,2,2,1,4},y = {1,2,3,1,2,3};
// w = 3;
x = {0,3,6,5},y = {0,3,2,4};
w = 1;
w++;
//n = 10^5
int n = x.size();
set<int> s;
for(auto item : x){
s.insert(item);
}
int last = -1;
int res = 0;
auto p = s.begin();
while(p != s.end()){
if(last == -1 || *p - last + 1 > w){
res++;
last = *p;
}
p++;
}
cout << res << endl;
return 0;
}
2、
#include <iostream>
#include <unordered_map>
#include <set>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;//{值,个数}
string s;
int main(){
// s = "39878";
// s = "00900";
s = "54321";
unordered_map<int,int> h;
int n = s.size();
for(int i = 0;i < n;i++){
h[s[i] - '0']++;
}
set<PII> num_set;//从小到大排序
int max_val = -1;//奇数个数的最大值
for(auto item : h){
int val = item.first,cnt = item.second;
if(cnt / 2){//>=2个
num_set.insert({val,cnt / 2 * 2});
}
if(cnt & 1){//奇数个
max_val = max(max_val,val);
}
}
//xyyyyy,先拼接右半部分
string res;
if(max_val != -1) res.push_back('0' + max_val);
//边界情况
if(num_set.size() == 1 && num_set.begin() -> first == 0){//num_set里面只包含0
if(max_val == -1){//没有奇数个数的值,说明只有0
cout << "0" << endl;
}else{//有奇数个数,说明res有值
cout << res << endl;
}
return 0;
}
//正常情况
auto p = num_set.begin();
// while(p != num_set.end()){
// int val = p -> first,cnt = p -> second;
// cout << val << ' ' << cnt << endl;
// p++;
// }
// p = num_set.begin();
string right;
while(p != num_set.end()){
int val = p -> first,cnt = p -> second;
string tmp = string(cnt / 2,'0' + val);
res += tmp;
right += tmp;
p++;
}
reverse(right.begin(),right.end());
res = right + res;
cout << res << endl;
return 0;
}
3、
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int N = 100010,M = 2 * N;
vector<int> a,b;
int h[N],e[M],ne[M],idx;
int count[N];//每个结点的子结点的个数
int res;
void add(int x,int y){
e[idx] = y,ne[idx] = h[x],h[x] = idx++;
}
//parent表示遍历的父节点,就是不重复遍历
void dfs(int u,int parent){
//
count[u] = 1;//任何结点都是包括自己的
//无向图的这种存储怎么判断叶子结点?
//必然有一个结点,必然有边的情况下
// int i = h[u],~i;i = ne[i]
if(u != 0 && (h[u] == -1 || ne[h[u]] == -1)){//叶子结点,除了0
return;
}
//
// int cnt = 0;//当前u结点的孩子结点的所有结点数量之和
//
for(int i = h[u];~i;i = ne[i]){
int j = e[i];//j是结点编号
if(j == parent) continue;
dfs(j,u);
// cnt += count[j];
count[u] += count[j];
}
// count[u] += cnt;
//
return;
}
void dfs_res(int u,int parent){
//
if(u != 0 && (h[u] == -1 || ne[h[u]] == - 1)){//叶子结点,除了0
return;
}
//
//
for(int i = h[u];~i;i = ne[i]){
int j = e[i];
if(j == parent) continue;
int cnt = count[j];
res += (cnt + 4) / 5;
// cout << res << endl;
dfs_res(j,u);//往下去算
}
//
return;
}
// void bfs(int start){
// queue<int> q;
// q.push(start);
// while(q.size()){
// auto t = q.front();
// q.pop();
// //对于每条边计算车辆消费
// for(int i = h[t];~i;i = ne[i]){
// int j = e[i];
// if(j == t) continue;//不能等于父节点
// int cnt = count[j];
// res += (cnt + 4) / 5;
// q.push(j);
// }
// }
// }
int main(){
memset(h,-1,sizeof h);
// a = {0,1,1},b = {1,2,3};
a = {1,1,1,9,9,9,9,7,8},b = {2,0,3,1,6,5,4,0,0};
int n = a.size();//边的数量
for(int i = 0;i < n;i++){
int x = a[i],y = b[i];
add(x,y),add(y,x);
}
// cout << h[1] << endl;
// for(int p = 0;p <= 3;p++){
// cout << p << ' ';
// for(int i = h[p];~i;i = ne[i]){
// int j = e[i];
// cout << j << ' ';
// }
// cout << endl;
// }
// cout << endl;
//计算每个结点的孩子结点的个数
dfs(0,-1);
//计算每条路需要的车子的数量
// bfs(0);
// for(int i = 0;i <= 3;i++){
// cout << count[i] << ' ';
// }
// cout << endl;
dfs_res(0,-1);
cout << res << endl;
return 0;
}
【8.14周日 LC周赛】3/4 = 三题30min
上次ak也是3000名左右,这次半个小时做出来三题也是3000名左右,稳定在3000名,一步一步上去
1、
2、
基环树
Set的使用,
⚠️ 只要是加法,就是需要考虑是否用LL
3、✅ 半个小时三个题目,完成了目标
Dfs的板子题
4、
答案:y总的数位dp模板
(0)这里0xxxx是一种不容易处理的情况,所以就是不处理
① 先处理长度[HTML_REMOVED] 数位dp✅ 因为最高位是1~A(n - 1) - 1,所以是必然长度是这么多
(1)这里算的是不包含0,所以就是首位是没有0的,可能性是9,然后第二位也是9种可能
(2)代码
① 长度<m的,就是枚举各个长度
⚠️ 数位dp?的推导思想,y总讲透彻了
(1)场景:求区间里面有多少个符合一定规则的整数
(2)收尾两位为0的特殊处理情况
① 首尾0的话,如果是连续的,可以看做没有
② 最后一个数,直接处理,不用分支
【8.13周六 微软笔试 Test2】2/3
⚠️ 秋招笔试是限定三个小时之内;春招笔试是两天之内,所以秋招还是比较严格的
1、
贪心,用堆写,每日一题写过很多次
2、
⚠️ 分数数的题目,可以单独拿出来做一下,总结这个母题
(1)用最大公约数通分,就是只要看分子就行了,这是一种常规处理手段
一、
✅ 正确的题目要求,求出来pair是两数之和,就是非常简单了,就是统计和为mc的数量就是非常简单了,pair是一对,就是两个数⚠️ 最大公约数+map,应该可以O(N)
✅ 数组的最大公约数 + 最大公倍数
(1)一个数组的最小公倍数,初始化为1
a * b / gcd(a,b)
(2)一个数组的最大公约数,初始化为0
❎ 求一个数组中和等于k的子序列的数量,板子题,n^3⚠️ dp的板子题
(1)时间复杂度不行
(2)空间复杂度不行
二、朴素的三维dp
Dp,三维dp
10^5
分数相加
(1)等于1:分子 = 分母
(2)超过1:分子 > 分母
3、
✅ 先写暴力,然后写更新
从暴力优化过来的,只要记录两个个数就行了
(1)本质就是数学运算
【8.7周日 周赛】ak = 1:00:00
1
2、
新题,先考虑常规,然后最后考虑边界(一般特判)
⚠️ bfs的公式
(1)多一个st数组
3、
连续子串的划分,必然是dp✅ 区间dp的母题专题训练的作用
(0)一维dp就行了,因为就是不管是什么状态,只要判断合法就行了,不用管最后是什么状态
(1)i = 2的时候,就是对于i >= 3可以特判一下
4、
思路在每日一题里面出现过的思路
⚠️ 循环表示的话,怎么去做?✅ 计算当前遍历的字符范围,就是环形考虑就行了,就是都是考虑一个区间里面的情况,就是考虑的方法是一样
(1)拆环成链,就是用两倍的空间去表示
【8.6 微软笔试Test1】
1、
在一组数组中,找到最接近B的和 = DFS
(1)只能递归枚举所有组合进行试算,找到最接近的组合。
(2)因为三数之和是极限了,就是三数之和找到最接近的,这是模板题的极限了
2、
本题: = 简化版本
(1)关键是反向思维:找到移动0出去的最小代价,整体上就是凑成连续的1的最小代价
(2)然后代码实现,就是统计1001中的0,然后就是计算移动0的最小代价,中位数的技巧min(i - left,right - i),这样就是知道往左边还是右边移动代价最小
(3)移动0,就是看左边的1的个数,这是可以直接通过下标o(1)得出来,这是合并同一个区间0的技巧的作用,也是这个题目考察的第二个技巧
T1703
(1)贪心:两边的1往中间移动,也就是0往两边之中,cost最小的一边移动
(1)反过来想,把0往窗口两端移,因为0移动出去,交换的次数就是交换路径上1的个数✅ 这个思路确实可以的,就是只看0,这样就不用关心最终1移动到的位置,反向思考
(2)滑动窗口原因:k个1,中间的0的区间个数必然是k - 1个,相当于在zeros数组上做长度为k - 1的滑动窗口
(3)✅ 通过滑动窗口来更新当前zeros数组中长度为k - 1的cost,其实就是一个递推更新过程
① 关键是这个推导公式,就是用上一个滑动窗口的res[i - 1]来更新这一个滑动窗口的res[i]
3、基础课匈牙利算法的模板题,直接复制模板过来就行了
(1)二分图,就是所有的边连接的点分为两个集合
(2)匹配成功的病人个数 = n
1、
#include <iostream>
#include <vector>
using namespace std;
string s = "....xxxx....xxxx...xx";
int maxlen = 7;
int res = 0;
vector<int> a;
//第u个的长度刚开始还没有加到len上面
void dfs(int u,int len,int n){
//
if(u >= n || len > maxlen){
return ;
}
//
res = max(res,len);
//
dfs(u + 1,len,n);//不选
dfs(u + 1,len + a[u],n);//选
//
}
int main(){
int n = s.size();
int i = 0,j = 0;
for(int i = 0,j = 0;i < n;i++){//[i,j]区间
//i
if(s[i] == '.') continue;
//j
j = i;
while(s[j] == s[i]) j++;
//结果[i,j - 1]
a.push_back(j - 1 - i + 1 + 1);
i = j;
}
for(auto x : a) cout << x << ' ';
cout << endl;
//dfs
dfs(0,0,n);
cout << res << endl;
return 0;
}
2、
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 100010;
string s = "RWRRRWWR";
vector<int> zeros,cost;
int stk[N];
int tt = -1;
int main(){
int n = s.size();
for(int i = 0;i < n;i++){
if(s[i] == 'R'){
if(tt != -1){
zeros.push_back(i - (stk[tt]) - 1);
}
stk[++tt] = i;
}
}
int m = zeros.size();
cost.resize(m);
for(int i = 0;i < m;i++){
cost[i] = min(i + 1,m - i);
}
//求最小消费
LL res = 0;
for(int i = 0;i < m;i++){
res += zeros[i] * cost[i];
}
cout << res << endl;
return 0;
}
3、
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 510, M = 100010;
// int n1, n2, m;
int n = 7,s = 10;
vector<int> a = {1,2,1,6,8,7,8},b = {2,3,4,7,7,8,7};
// int n = 3,s = 3;
// vector<int> a = {1,3,1},b = {2,3,2};
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool find(int x)
{
for (int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true;
if (match[j] == 0 || find(match[j]))
{
match[j] = x;
return true;
}
}
}
return false;
}
int main()
{
// scanf("%d%d%d", &n1, &n2, &m);
memset(h, -1, sizeof h);
// while (m -- )
// {
// int a, b;
// scanf("%d%d", &a, &b);
// add(a, b);
// }
for(int i = 0;i < n;i++){
add(i,a[i]);
add(i,b[i]);
}
int res = 0;
for (int i = 0; i < n; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) res ++ ;
}
// printf("%d\n", res);
if(res == n) cout << "true" << endl;
else cout << "false" << endl;
return 0;
}
【7.31周日 周赛】
1、
2、
Lc的题目,case还是比较水的
贪心 = 关键是最后一段的处理
累加的时候,注意数据范围
3、
✅ 就是dijkstra的母题专题训练的作用就体现出来了
正权边
⚠️ 答案不存在的情况,要考虑的
4、陈年老题
方法一:强连通分量的tarjan算法,
方法二;基环树dp,手动找环
⚠️ 公式默写的重要性,稳定 -> 修改题就是对于公式的修改,所以默写出来公式特别重要的
① 判断是有有正环
(0)负环,用spfa + BF -> ⚠️ 这里是求环,正环
(2)✅ 这里判断是否有正环,就是跑一遍最长路,然后就是上面的这个技巧了✅ 这个应用非常巧妙
② 求最长环的长度
(1)多个环呢?
❎ 从j开始跑,就是跑一次最长路,就是最长的⚠️ 没法停下来
(基环树专题)
✅ 基环树是一种非常简单的图,就是直接用while循环就能找,完全不用遍历的方法
定义:每个点只有一条出边,这样的图就是基环树,就是形状上就是一个环上面挂了很多树
① 有向图:每个连通块都是一个基环树
② 无向图:N个点,n条边的图必然是基环树
性质
(1)求一个点A到所有点的距离,只要从点A一直走到不能走位置,这样就求出了一个点a到所有点的唯一的路径✅ 不能走只有两种情况
求距离的话,直接用上一个点来更新当前点就行了
① p[x] = -1,表示走到头了
② dist[x] != INF,表示这个点走过了✅ 同时表示有环
(2)对于一个点,只有两种走的可能性,一种是被别的点走到了,被标记了或者求出了距离;一种是现在这个点走到了
(3)求基环树的环的入口点,直接就是装到走过的点,必然是环的入口
代码:
(1)存储的话,存p[x] = y,表示x的出边指向y,因为就是只有一条出边
周赛题目:
T3:很简单,就是求两个dist,然后遍历一遍所有点就行了
T4:每个点遍历一遍,o(n)
① 如果遍历过了,必然是已经找过经过这个点的环了
② 记录p[x]是否遍历过,如果遍历过了,有两种情况:一种是以前遍历的,直接break,因为已经找过了环;一种是现在遍历的,就是刚找到环,直接就是计算最长环
T2127
(1)基环树,最大环的应用
【7.24周日 周赛】
3、
(1)我的方法:
sort指定类别排前面,可以实现⚠️ acwing里面试一下就是能不能这样排序,就是等于类别的排在前面
✅ lc里面的比较函数,直接写在比较函数里面,真的是两次周赛都踩坑了
空间炸了,就是自己存的东西在一个地方太多了
✨答案:✅ 我能够想到这种方法,但是set容器使用不熟悉
(1)set中的pii默认就是排序的 + 去重;⚠️ set容器的使用,有缺陷 + 对于两个存储结构中数据的对应设计也有漏洞,一直都有,就是设计的时候思路没有那么清楚,需要母题专题训练找到一种高效的打草稿的方法⚠️ 语法题的专题训练
① 两个存储数据的结构,通过[HTML_REMOVED]中的string的类别来联系起来,然后就是找到对应的类别中的元素然后杀出
(2)更新的时候,删除掉之后,再插入,set都是logn
(3)set默认是从小到大,这里需要从大到小,就是存成负数,这是一个技巧✅ 对于只有从小到大,然后数值类的排序
4、
相同的算一个,不同的算两个
(1)我的方法:非数学的方法,就是和上周周赛一样的,都是就是写了一大推的模拟
(2)数学性质✅ 模拟样例就能看出来
① 或和与是互补的,就是构造题✅ 模拟样例的重要性,就是一定要把样例模拟一遍,很大程度都是有惊喜的,这是做算法题的经验
【7.17 302lc周赛】
2、
Sort是从小到大,
Heap是默认是大根堆
3、
❎ 还是要学习py刷题,很多字符串的题目都能够就是秒掉,这是c的弱点⚠️ c写起来比较麻烦,但是string里面也讲过了对应的函数,就是必然能够分析清楚时间复杂度
这里是返回下标,所以是int,但是string可能超过范围
⚠️ 这里直接不用截取,直接按照trim开始的字符串就是排序,写在比较函数里面,这样就是保证他们的长度是一样的,就是比较起来比较方便,因为截取出来比较的时候要考虑长度,就是非常不方便⚠️ 就是题目不要求求截取出来的字符串,只要下标✅ 就是想求什么你就算什么,没有要求的东西尽量就是不算出来,
⚠️ 需要稳定排序,就是相同的数字,下标在前面的放在前面⚠️ 这个正常怎么实现,sort怎么实现✅ 手写归并排序
⚠️ s.substr(I,len)复杂度多少?✅ Its time complexity is O(N) where N is the size of the substring.
⚠️ 字符串的排序函数的实现,这个是自己的一个漏洞⚠️ 就是自己实现排序的比较函数
(1)cmp在lc里面的写法
4、
包括x的因数
必然是最小的这个数的因数,因为就是需要是所有数的因数,那最小的这个因数就是必然是,不能超过
Gcd:一个数d能够能够整除所有数d1、d2,等价于能够整除所有数的最大公约数⚠️ 显然的✅ 关键就是这个gcd的结论
(1)求数组元素的最大公约数,初始化d = 0,因为0能够整除任何数,直接返回a
(2)gcd的板子:就是里面的元素的顺序,如果b > a会调换顺序gcd(b,a % b) : a
【7.10周日 301周赛】
✅ cf的思维题的训练,还是有很大帮助的,就是对于第三题、第四题都是能够思考出来一半,就是能够有一半的思路;说明就是构造题的训练在方向上是正确的,只要自己能够坚持下去就行了,只要方向正确,哪怕速度慢一点也是没有关系的✨总结:只要有进步就行了,就是落后只是暂时的,只要方向是对的,加上时间、努力的积累,就是自己肯定hi能够慢慢赶上去的
1、
构造题,自己想构造的方法✅ cf的构造题的训练还是对周赛的稳定性有很大的好处
⚠️ 感觉周赛的数据很水,就是没有cf那么卡手或者说周赛的样例就是会把大部分的这种数据的坑给展示出来,cf需要自己推导✅ 所以就是cf的题目能够训练自己debug的能力✨总结:前面是签到题
(1)好像只要能够模拟出来样例,就是成功了80%,这个和cf的题目的差别特别大,因为cf的样例模拟出来才是刚刚开始
2、
小根堆
直接暴力做,因为infinit = 1010
3、777题原题,X变成_
① 首先判断字符串是否相等
② 再判断空的地方,这个需要自己构造
(1)利用一一对应相等的性质,就是把判断的条件放在了对应的每个字符的判断上面,需要完全相等 ⚠️ 对于每个字符去考虑,因为就是需要最后是一一对应的:就是遍历一遍,判断就是每个字符,因为l的话,就是不能往右边移动,所以就是如果i < j,就是不能往右边移动,所以就是没法对应上
4、
肯定是需要从另外一个角度构造解法,降低复杂度
(1)长度为n结尾为x的情况,这是自己思考到的,没有进一步思考了
从mx反过来枚举,就是思路上有的,就是分解因数的应用,但是代码写起来有点麻烦,而且有重复方案,因为可能4、6的因数都有2,就是重复枚举了
(2)分解质因数,质因数是倍率,把倍率放置在相应的位置上;然后就是可以累加放起来,就是把质因数放在相应位置上
For循环的j和j有什么区别⚠️ 大神都是用j,就是好像因为i会产生一个临时变量,而i不会,但是现在据说已经被优化了,没有这个性能问题,所以还是用j
【kickstartD 7.10周日】
专注打kickstart的比赛,就是这次的D轮的比赛就是自己应该专注的,只要做到自己能力范围的极致,就是没有遗憾就行了✅ 平时还是多加训练就行了
构造题的训练确实是非常有用的,就是自己做贪心题的能力,或者思考题目的能力就是真的提升得非常快✅ 专注训练到构造题的2000分,就是这就是自己做到了自己的能力的极致
Kickstart的输出,就是for(int I = 1;i <= t;i++){solve(i)};
A、
构造一种贪心的max的方法
这个提示的方法,就是数据集的提示是非常重要的,就是基础的解法是需要通过数据集来推导的
B、
❎ 构造方法,没有任何思路
动态规划 + 前缀和、后缀和
⚠️ 互相没有限制的话,就是可以单独求解,从最佳答案反向思考,就是顺序不会影响就是最佳答案
1、就是两个队列是不互相限制的,所以就是可以分开来求解,然后就是enumerate组合的方式
2、找前面和找后面也是不互相限制的,所以就是分开求解✅ 这种没有限制的,就是最佳方案反向推导就是前后是可以单独求解的 + 前后的话,说明选择就是有限的,那就是用dp
C、
就是当前的选择会影响后面的选择,就是用dp,就是递推搜索;整体是暴搜,就是有限种方案
TS2:动态规划
1、只有移动的时候是需要时间的,去掉重复的数字
2、就是从当前的这个数字a移动到b,就是有多种选择,这就是状态转移的方程,就是转移出来的状态是有限个
3、❎ 怎么处理就是前面出现的1,在后面不再就是处理这个1⚠️ 重复使用一个按键是没有关系的
TS3:
1、加上一个贪心,就是扩展的只有两个方向的最近的可能性的值
D、没有必要看,就是竞赛都很少考
强连通分量,就是tarjan模板
这种说谎,不知道是否真假的题目,这种题目我完全没有思绪,需要专题训练就是dfs训练清楚
【7.3 lc周赛第300场周赛】
✅ 确实做cf的构造题,就是能够让自己就是思维提高很多,真的太爽了,就是这种思维的提高,是自己写代码思路更加清晰的训练,就是做简单的题目确实能够让自己的体会到这种思路清晰的作用⚠️ 所以就是构造题确实能够训练自己的思维,太爽了,作用特别大
1、
签到题
2、
前两题都是签到题,后两题才是真的有区分度的题目
普通的螺旋矩阵,方法完全一样,就是思路都是出现过了
3、
一、以人为思考对象
思考每个人创造出来的人数,包括自己
✅ 通过把思路记录下来 + 模拟样例,才能保证这个题目就是思考到自己ide极致
(1)特别就是自己需要把自己的思路都记录下来,就是任何一种可能的思路都通过笔记记录下来,这是让自己思考到自己的思路记得极致,记录 = bfs,然后尝试 = dfs深挖✅ 这个方法特别有用,
(2)就是这种思路的开阔,也是做了cf的构造题扩展的,太爽了,就是确实看到了效果
就是自己的constructive的题目的思考过程确实痛苦,但是也是有效果的,毕竟cf的题目是8h一套,比lc周赛题目的思维量要大很多
⚠️ 差分就是把一个区间里面数 + a,优化
二、以天数为思考对象
4、
最后一个题目,就是40min只要把这个题目做完我就行了,已经达到了三题的目标了,然后就是可以吃西瓜休息一下,这40min只要专注在这个题目上就心里搁
Lc周赛有简历推荐的机会,还是要给与足够的曝光,说不定就存在潜在的机会
一、数量,必然是dp
坐标转数字,是(a,b) = a * n + b,其中n是横向的长度,就是横向的格子数量
⚠️ 有方向的路径就是没法用dp,这个在以前的题目中碰到过,因为有更新顺序的问题,需要找到一种有效的更新顺序
关键是路径的方向是四个方向,那就是有先后更新的问题,按值的大小递增更新格子,解决了更新方向的问题
①、 以路径长度为对象
② 以路径终点为对象