首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
钱逸凡
获赞
17
粉丝
0
关注
5
看过 TA
2
男
东南大学
2023
Unity3D客户端
IP属地:广东
学生
私信
关注
拉黑
举报
举报
确定要拉黑钱逸凡吗?
发布(14)
刷题
钱逸凡
2022-07-02 17:48
Unity3D客户端
2022-07-02
在牛客打卡1天,今天学习:刷题 7 道/代码提交 16 次
每日监督打卡
0
点赞
评论
收藏
转发
钱逸凡
2020-11-21 23:17
Unity3D客户端
捉迷藏__题解
数据规模 从别的oj网址上找的对于20%的数据, N ≤50, M≤100;对于60%的数据, N ≤3000, M ≤10000;对于100%的数据, N ≤100000, M≤500000。 解题思路 这题我做了两种解法,第一种思路不好想,但是很快,复杂度为O(nlogn),另一种比较好想(但实际上并不好写),但是复杂度略高,为O(n logn logn) 思路一:括号序列 用到的知识:线段树 括号序列的定义 括号序列是可以理解为把一颗树拍扁,变成一个序列,这样我们就可以用各种数据结构来维护这颗树了具体的方法如下:这是一颗树:我们从根节点开始遍历,每经过一个点,就加入一个"(",每当...
0
点赞
评论
收藏
转发
钱逸凡
2020-11-17 22:12
Unity3D客户端
Palindrome__题解
用到的知识点 Manacher+线段树/树状数组Manacher算法是一种能在O(n)复杂度内求出每个点最大回文半径的算法,没学过的点这里 解题思路 暴力解法 我们第一个想到的肯定是暴力解法:枚举每一个字符串,判断是否为题目要求的one-and-half串,然后统计答案时间复杂度:O(n^3) 肯定不行,于是尝试优化 考虑使用Manacher算法进行优化 为什么想到Manacher呢?因为题目与回文串有关,往这方面想说不定就做出来了。我们先跑一遍Manacher,于是得到了所有点的最大回文半径。 重点1 此处我们不需要引入'#' , 因为根据题目要求,我们所需的回文串一定是两个相连的奇回文...
0
点赞
评论
收藏
转发
钱逸凡
2020-11-17 20:43
已编辑
Unity3D客户端
网络__题解
用到的知识 线段树/树状数组+树链剖分+整体二分没学过的建议先去学了再回来做这道题 解题思路 题目要求的是不经过x的所有路径中最大的路径,那么我们可以考虑使用二分:对于每条v大于mid的路径,将路径上的点+1(路径上的点对应线段树的点,这部分使用树链剖分+线段树/树状数组实现),并统计路径总数,然后查询x点的值,如果x点的值与路径总数相等,即证明所有大于mid的路径都经过x,此时需要减小mid,重复操作,否则,则存在不经过x的路径,增大mid我们发现,这个操作可以同时针对所有询问,于是,使用整体二分复杂度O(m logm logn logn) 为什么是三个log? logm是对离散化后的答案区...
0
点赞
评论
收藏
转发
钱逸凡
2020-11-10 22:05
Unity3D客户端
组队__题解
本题的数据规模 从别的oj网址上找的:数据范围: N <= 5000 ,height和speed不大于10000。A、B、C在长整型以内。 吐槽 牛客网的分类简直迷惑,这题竟然归为了堆?而且还是5星?我往堆上靠了半天没想出来,最后换一种思路一下就做出来了 解题思路 一种很容易想到的思路是:先分别对h,v排序,然后枚举min_h,枚举min_v,枚举所有人,这样是O(n^3),明显不行那么怎么优化呢?我们先看看题目的要求,这题的要求简化一下只有三点:1.a * (h>min_h ) + b * ( v-min_v ) ≤ c2. h>min_h3. v>min_v当我们枚...
0
点赞
评论
收藏
转发
钱逸凡
2020-11-08 22:17
Unity3D客户端
有上下界的网络流问题
前置知识 网络流求最大流的算法最少要会一种,安利一下我以前写的博客:通俗易懂的网络流入门:EK简单高效的Dinic算法稍微复杂但效率很高的HLPP和ISAP算法建议按顺序学习,并至少学完Dinic,因为Dinic不难,并且高效 无源汇的有上下界的可行流 名词解释 无源汇:不区分起点和终点的闭合图有上下界:每条边都有一个流量上界和流量下界可行流:此处仅考虑是否存在可行方案 解法 因为要跑网络流,所以我们引入一个起点ss和一个终点tt,接下来,考虑如何加边:对于原图中每条边{s,t,low,up}(分别表示起点,终点,下界,上界),我们在网络流图中加入一条边{s,t,up-low}(分别表示起点,...
0
点赞
评论
收藏
转发
钱逸凡
2020-11-07 19:58
Unity3D客户端
骑士精神__题解
这道题可以作为A*的入门题 什么是A* 这是A* 的定义:A*搜索我的理解是,A*是一种剪枝方式,可以广泛运用于搜索中。A*的思想是定义一个估值函数,表示最理想的情况下还需要多少步才能达到想要的结果(真实情况所需的步数会大于等于估值函数的返回值),如果当前步数(定义为g(x))+估值函数(定义为h(x))已经超出了前面的最理想情况那么就可以直接结束搜索 本题的估值函数 前面说了,估值函数表示最理想的情况,那对于本题来说,我们只需要计算当前的状态与标准状态有几个不一样,那么最理想的情况下就只需要不一样的点的数目-1步,为什么是-1呢?因为最后一次交换会使得两个点变得和标准一样,所以是-1 int...
0
点赞
评论
收藏
转发
钱逸凡
2020-11-05 20:34
Unity3D客户端
魔法猪学院___题解
数据规模 题目里没给出数据规模,我从别的oj网址找的:所有数据满足 2<=n<=5000 1<=m<=200000 1<=E<=1e7, 1<=ei<=E,所有的E和ei都为实数 用到的知识 最短路算法(spfa,dijkstra都可以)+可持久化堆 解题思路 此题可视为k短路题的模板,由于我讲的可能不是很好,这里推荐一个教程:俞鼎力大牛:堆的可持久化和k短路由于该教程已经讲的比较细致了,所以我就简单地概括一下,看不懂的地方可以去看教程 构造最短路径树和边的分类 我们先从n点跑一遍最短路,这样就可以得到n为根的最短路径树,然后,我们就可以将边分为...
0
点赞
评论
收藏
转发
钱逸凡
2020-11-04 13:52
Unity3D客户端
超级钢琴__题解
解题思路 用到的知识点:st表+堆 思维过程 按照题目的要求,我们要求所有长度为[l,r]的子区间中最大的k个,首先,我们不可能遍历所有的子区间,因为那是O(n^2)的,我们考虑贪心 先考虑k==1时: 当k=1,我们只需要找最大的一个子区间,但是,这也要遍历所有子区间,于是考虑如何用较小的时间找出最大的子区间,由于题目的n为500000,所以一般来说,存在O(n)或者O(nlogn)遍历子区间的方法,而且很可能是O(nlogn) 首先,通过预处理前缀和数组sum,我们可以在O(1)的时间得到一段区间[i,i+k]的和,即sum[i+k]-sum[i-1]然后,我们发现以i为起点的所有子区间中...
0
点赞
评论
收藏
转发
钱逸凡
2020-11-02 22:59
Unity3D客户端
Safe Travel__题解
题目大意 给n个点m条无向边,每条边有边权,当点1到点i的最短路的最后一条边被封住时(只有最后一条边,其他边还可以用),求点1到点i的最短路,i取2,3,……,n(被封住边只影响此次的结果,不影响其他点的结果),如果被封住后到达不了i,则输出-1,否则输出被封住边后的最短路 解题思路 思维过程 我们肯定要先跑一遍单源最短路,此时,我们得到了从点1到任意点的最短距离(后文用dist数组表示)设到i的最短路径上除i以外,最后一个点为x,我们考虑另一条经过y的路径,如果i与y有边,那就判断是否更新答案 ,其中val表示i与y的边的边权,那么我们只需要考虑与i相连的除了x以外的所有点即可,但是,直接这...
0
点赞
评论
收藏
转发
钱逸凡
2020-10-30 15:38
Unity3D客户端
菜肴制作___题解
本题坑点 题目没有给数据规模,我去别的oj网站上查了,是 100%的数据满足N,M<=100000,D<=3 解题思路 “看到x要先于y”这类字的时候,第一反应就是拓扑排序(不知道拓扑排序点这里 ),但是有一个问题,如果用拓扑排序,我们只能得到字典序最小的方案, 不能满足题目要求的使得小A能尽量先吃到质量高的菜肴,那怎么解决这个问题呢?我们在做拓扑排序的过程中,会优先考虑路线的起点编号大小,但是我们的目标却是使得每次选取的路线终点的编号最小,那么我们可以通过反向建边,寻找字典序最大的方案,最后反序输出就可以了 注意事项 重边问题 本题存在重边,所以不能在加边的时候就统计入度,去除重...
0
点赞
评论
收藏
转发
钱逸凡
2020-10-29 22:57
Unity3D客户端
火锅盛宴___题解
解题思路 这题一共三个询问,我们可以先从最简单的第三个询问开始分析 第三个询问 我们可以用线段树(树状数组)来维护所有已经熟的食物,每次询问的时间复杂度为O(logn) 第一个询问 由于我们在做第三问时建立一颗线段树(树状数组),所以我们这里可以直接用线段树来解决这一问:若整个区间的和为0,则没有食物。若有食物,则:用二分来找出有值但最小的点(左右端点相同的区间),该点就是所求的食物编号,每次询问的时间复杂度为O((logn)^2),然后将该点减一,复杂度O(1),所以,这步总的复杂度为O((logn)^2) 第二个询问 我们给每一个食物建一个队列(因为同一种食物煮熟花的时间相同,所以越晚入队...
0
点赞
评论
收藏
转发
钱逸凡
2020-10-24 23:27
已编辑
Unity3D客户端
珂朵莉的数列____题解
前言 我看到题解区清一色的离散化+树状数组,所以我就写了一点不一样的,其实逆序对问题用归并排序也是一个很好的解法 题目解释 题目描述中的个子区间指的是n个一个数的子区间,n-1个连续两个数的子区间,n-2个连续3个数的子区间,…… 题目的坑点 本题的数据规模很大(n<=1000000(一百万)),所以,不仅是时间比较紧,答案也超过了longlong(一定要注意,我因为这个浪费了好多时间),我比较懒,用了int128,也可以自己手写高精度 解题思路 归并排序!!! 为什么能用归并排序解决逆序对问题? 归并排序的基本原理我们就不说了,不会的可以去网上搜索,网上有很多。我们知道归并排序在合并...
0
点赞
评论
收藏
转发
钱逸凡
2020-10-23 17:43
Unity3D客户端
0
点赞
评论
收藏
转发
1
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务