首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
塔子哥学算法
2020-06-15 10:58
已编辑
Fleet AntiSubmarine Warfare Training Center (San Diego) 计算机类
关注
已关注
取消关注
【题解】南华大学第16届ACM程序设计大赛(重现赛)
A.地理学带师:模拟,签到
n比较小,
模拟即可.
B.Matrix multiplication: dp
在某些情况下,矩阵乘法的方案比较多(比如 所有矩阵行列全等的情况,这将是一个阶乘级别的大小),但是n比较小,而且需要所有矩阵都要能连乘起来。考虑状态压缩dp。
输出字典序最小的方案就逆着全集贪心输出即可。
另一种思考方式。将每个矩阵抽象成一个点,两点之间连一条边当且仅当两个矩阵能够相乘。那么问题转化为在一张图上统计哈密顿通路个数。也是经典状压dp。
C.拦截导弹:数据结构
核心在于:快速找到序列中从左至右第一个小于导弹高度h的位置。n比较大,暴力行不通。考虑引入高级数据结构维护。
①建立线段树,在维护区间最大值,线段树上二分的查找一下即可。复杂度
②分块。暴力按块找即可。复杂度可以证明为
D.只不过是另一个高斯罢了:组合数学,数学定理优化
①通过打表找规律或者从定义式出发化简式子可以发现递推式g(h,n)=g(h–1,n)+g(h,n–1)
②熟悉组合数学/dp 的朋友不难发现这样的递推式的一种实际含义为:在二维网格上求起点到终点的非降路径和方案。存在一种组合数的求法。所以问题转化为求解组合数。
③观察到h,n十分大,但是模数很小,考虑使用Lucas定理进行优化。
E.吃豆豆:前缀和,STL优化。
比赛的时候发现很多人用尺取,二分去写。其实题目中说明了数据可能是负的,故不符合单调性,需要引入STL去给前缀和排序,再二分。
题目条件转化为:sum[R] – sum[L] <= Max ,要使得不等式左边尽量大,枚举右端点.转换为让sum[L]尽量小。又需要Sum[L]>=sum[R] – Max. 显然用Map记录下每一个前缀和,形如二元组(前缀和,出现次数).然后Map上二分一下求出Sum[L]对于R符合上述条件(注:Sum[L]的值可以保证是唯一的,但出现次数是不一定的,所以要用二元组去保存它们),这个过程中维护最优解Ans。
很容易发现对于每个右端点,它不一定有确定的左端点,但是会有确定的前缀和的值。所以对于每个右端点,存一个二元组(sum[R] – sum[L] , 对应sum[L]个数). 最后O(n)扫一遍,当 二元组的第一维 == 最优解Ans就将二元组的第二维统计进答案就好.
F.Strang multiset:数论,筛法,预处理
通过阅读伪代码发现:函数功能就是求一个数的最小素因子。由于询问比较多且数比较小,可以预处理利用素数筛将所有数的最小质因子筛出来,进行模拟即可。
直接模拟行不通,假设询问的都是质数,那么复杂度会跑到
提示
全部评论
推荐
最新
楼层
小红书
校招火热招聘中
官网直投
相关推荐
我不饿也吃
04-24 20:45
模拟IC设计
比特大陆开除曝光拖欠工资的员工
去年10月,比特大陆被曝开除三名发布公司工资发放信息的员工,比特大陆称这三位员工给公司造成严重的负面影响,违反了公司的《对外信息披露管理规范》、《保密、不竞争及知识产权协议》、《劳动合同》、《员工手册》等规定。因此对该三名员工立即开除,永不录用,同时,公司已通报其处分意见给涉事实习生的所在学校,并保留追究所有涉事人员其他法律责任的权利。从法律的角度来看,比特大陆的公司内部规定俨然已经凌驾于《劳动法》之上,不但不反思自身停发、克扣员工工资的行为,反而不允许员工有一丝一毫的抱怨,甚至对实习生实行追责至其学校的恫吓行径,权利和义务的不对等在这家公司身上体现得淋漓尽致。
点赞
评论
收藏
转发
许愿wangye
昨天 20:54
已编辑
重庆邮电大学 计算机类
携程一面 4.7
1.架构2.分库分表怎么设计的?如何分库分表的?hash取模 数据均匀性3.列举一些常见的集合类 和它的数据结构和简单的实现原理4.hashmap和currentMap有什么区别5.线程池6.线程数怎么设置7.jvm内存模型8.对象的生命周期在JVM的运行空间中,对象的生命周期大概可以分为7各阶段:创建阶段(creation)应用阶段(Using)不可见阶段(invisible)不可到达阶段(Unreachable)可收集阶段(Collected)终结阶段(Finalized)释放阶段(Free)创建阶段(creation)在创建对象阶段,系统要通过下面步骤,完成对象的创建过程:1).为对象分...
软件开发2024笔面经
点赞
评论
收藏
转发
给个offer吧______
03-11 20:03
天津城建大学 计算机类
在群里看到的
点赞
评论
收藏
转发
拼多多交易内推
昨天 11:48
拼多多_研发_研发工程师
拼多多内推码拼多多内推码拼多多内推码 25届实习\24届校招
关于部门:我们是拼多多基础电商团队,负责用户、订单、履约、售后、评价等最重要最核心的领域,挑战大,上升空间高技术挑战:流量大,可用性要求高,迭代快内推对象:海内外2025\2024届应届毕业生截止时间:2024.6.13面试形式:可在线面试( 可在线远程面试哈!!!)2025届实习内推链接:https://careers.pinduoduo.com/campus/intern?t=uJIzwEj4vW,内推码:uJIzwEj4vW。请本链接投递简历,优先到我们部门实习。 也可以通过扫描下图二维码投递: 2024届校招内推:可以微信扫描以下牛客岗位投递,或者直接私信 ...
投递拼多多等公司10个岗位 >
点赞
评论
收藏
转发
2
收藏
评论
分享
回复帖子
全站热榜
1
...
HR面试面经问题汇总(共计30+问题,2500+字数)
4.0W
2
...
中科大软件工程研二,字节实习一年多,是时候了...
1.2W
3
...
机械/制造笔面经第二期,发面经攒人品!周周💸有奖🎁
1.1W
4
...
一个CS人在字节升级打怪(实习转正版)
1.0W
5
...
面试阿里云,遇到了找实习最逆天的一次拷打
9300
6
...
配不上自己的野心,也辜负了所受的苦难
7143
7
...
阿里国际 1个小时40分钟
6399
8
...
腾讯音乐-QQ音乐前端一面(秒过)
6373
9
...
盲审
5968
10
...
五一不敢回家
5816
正在热议
#
牛客帮帮团来啦!有问必答
#
314601次浏览
6766人参与
#
机械制造薪资爆料
#
247618次浏览
2986人参与
#
华为求职进展汇总
#
426983次浏览
4283人参与
#
非技术岗薪资爆料
#
3015次浏览
87人参与
#
第一次面试
#
11443次浏览
172人参与
#
除了offer,现在你还缺点啥?
#
1484次浏览
37人参与
#
应届生应该先就业还是先择业
#
9991次浏览
102人参与
#
找工作,你会甘心进小厂还是猛冲大厂
#
21046次浏览
203人参与
#
来聊聊机械薪资天花板是哪家
#
15329次浏览
118人参与
#
如果校招重来我最想改变的是
#
67998次浏览
1348人参与
#
为什么那么多公司毁约
#
31580次浏览
266人参与
#
毕业租房也有小确幸
#
18720次浏览
1205人参与
#
面试被问第一学历差时该怎么回答
#
13089次浏览
147人参与
#
通信硬件2024笔试面试经验
#
76486次浏览
855人参与
#
百度工作体验
#
18664次浏览
204人参与
#
实习工作,你找得还顺利吗?
#
4324次浏览
66人参与
#
机械人的薪资开到多少,才适合去?
#
39631次浏览
234人参与
#
通信硬件人笔面经互助
#
53526次浏览
1228人参与
#
租房前辈的忠告
#
19325次浏览
1558人参与
#
晒一晒我的offer
#
2725486次浏览
49197人参与
牛客网
牛客企业服务