首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
课程
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
无名行者zzz
获赞
8
粉丝
6
关注
6
看过 TA
17
男
浙江大学
2024
Java
IP属地:浙江
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑无名行者zzz吗?
发布(6)
刷题
无名行者zzz
2019-09-10 12:04
已编辑
浙江大学 计算机类
9.9训练小结
题意: 给定一个序列(长度<=1e5), 要求从其中任选一段长度为L的子段并删除, 最后问你剩余序列的LIS(严格递增)为多少? 总结: 想到了枚举切割子段的起始点,进而也想到了预处理出以每一个元素为终点的LIS长度(前缀预处理)和以每一个元素为起点的LIS的长度(后缀预处理),进而也想到了从后往前枚举起始断点并维护一棵持久性权值线段树(持久性指在一次遍历过程中维护一颗线段树,每一个新的状态都可以依托现在的状态去构建(例如:D-Query)), 枚举前一段的终点,在线段树中查后一段中大于这个点中的最大LIS,然而总是wa,最后发现还是没注意一些细节。(1)后缀预处理以每一个元素为起点的L...
0
点赞
评论
收藏
转发
无名行者zzz
2019-08-30 11:28
浙江大学 计算机类
线段树上的类二分查找总结
非严格二分查找: 情形一:给定序列a[1]~a[N], 每次询问给定一个数v, 一个位置pos, 从a[pos+1]~a[N]中找到第一个大于v的元素的下标 考虑建立一棵普通的位置线段树, 树上节点维护当前位置区间的最大值; 每次查找时从根递归向下查找, 对于当前区间 [ l,r ]: 0. 若当前节点为叶子结点, 若结点的值满足 > v , 返回下标即可; 1. 若pos <= mid: 若左子树最大值大于v(约束), 则左子树可能存在解, 递归查找左子树; 若左子树查找到解,则直接返回该解(这是一个重要剪枝,可以大幅优化时间, 显然此时即使右子树存在...
0
点赞
评论
收藏
转发
无名行者zzz
2019-08-30 10:10
浙江大学 计算机类
2019-08-30
在牛客打卡4天,今天也很努力鸭!
0
点赞
评论
收藏
转发
无名行者zzz
2020-11-21 14:51
已编辑
浙江大学 计算机类
前缀和与差分总结
一维: 前缀和的建立: sum[i] = sum[i-1] + val[i], 前缀和求解区间和: { val[l] ~ val[r] } = sum[r] - sum[l-1], 差分标记: [l,r]区间每个点增加v , 则tag[l] += v, tag[r+1] -= v, 然后每个点 val[i] 的值的变化量delta即为 tag[]的1~i的一维前缀和 二维: 前缀和的建立: sum[i][j] = val[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]...
0
点赞
评论
收藏
转发
无名行者zzz
2019-08-30 10:13
已编辑
浙江大学 计算机类
判断某边是否在图中给定两点间的最短路径上(结论)
由于图中给定两点(假设为No.1 & No.n)间的最短路径不止一条,但可以确定一定是简单通路,因此存在一个较为标准的方法找出在1->n的最短路径的所有边: 通过对原图跑Dijkstra求出原点到其他所有点的最短距离dis(1,i) (i : 1~n),通过对原图的反图跑Dijkstra求出其他所有点到终点的最短距离dis(i,n) (i : 1~n) 依次扫描图中每条边,对于某条边(u,v)(边权记为w(u,v)),若dis(1,u)+dis(v,n)+w(u,v) = dis(1,n) 或 dis(1,v)+dis(u,n)+w(u,v)...
0
点赞
评论
收藏
转发
无名行者zzz
2019-08-30 10:15
已编辑
浙江大学 计算机类
19牛客多校2-F(DFS,权值计算散步于过程中以优化时间)
输出描述: Output one line containing an integer representing the answer. 示例1 输入 1 0 3 3 0 输出 3 题意: 给定2n个人,每两个人间存在一个竞争值,题目要求将这2n个人划分为人数相同的两组(即每组n人),记分好组的情况下所有的无序对(x,y)(x, y来自不同组) 产生的的和为F,本题即求最小的F为多少。 分析: 自然想到要枚举子集,倘若单纯地考虑每一元素 放/不放 在组1中,并在 组1/组2 放满后进行统计&更新最优值,则复杂度O(C(2N,N...
0
点赞
评论
收藏
转发
1
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务