首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
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:数论,筛法,预处理
通过阅读伪代码发现:函数功能就是求一个数的最小素因子。由于询问比较多且数比较小,可以预处理利用素数筛将所有数的最小质因子筛出来,进行模拟即可。
直接模拟行不通,假设询问的都是质数,那么复杂度会跑到
提示
全部评论
推荐
最新
楼层
联想
校招火热招聘中
官网直投
相关推荐
要元气满满鸭
昨天 19:29
阿里巴巴_算法工程师
学弟学妹快来!淘天缺java实习简历!
目前组里java实习hc,有没有没有投递过的同学,或者在其他部门三面挂了/排序的同学啊,我们这边可以直接开始面试,流程很快,一周搞定!!因为之前发了意向被鸽了。。现在还要继续招人。。。真的,我们发意向很快,不排队。。。但希望大家都来实习啊呜呜
投递淘天集团等公司10个岗位 >
点赞
评论
收藏
转发
喜欢后仰跳投的乌龟在对齐目标
04-17 19:42
门头沟学院 计算机类
快手春招一直流程中
二面完就一直流程中,也不挂,还有机会嘛
快手二面67人在聊
点赞
评论
收藏
转发
比奇堡实习员工
今天 14:12
北京理工大学 电子信息类
啊这,特斯拉这波。。。。
九千买走应届生身份,有受害佬吗
点赞
评论
收藏
转发
卜白_
03-21 09:44
Белорусский государственный университет 计算机类
什么意思?🐒
我就问你那两个句号什么意思?😂😂😂#boss直聘# #hr# #牛客在线求职答疑中心#
牛客在线求职答疑中心
点赞
评论
收藏
转发
牛客873446416号
04-19 15:28
西安科技大学 计算机类
java
java今年好找工作吗
点赞
评论
收藏
转发
2
收藏
评论
分享
回复帖子
全站热榜
1
...
盲审出结果了
7063
2
...
离开北京我才发现的事
6875
3
...
机械/制造笔面经第二期,发面经攒人品!周周💸有奖🎁
6626
4
...
腾讯音乐 一面 秒挂
6378
5
...
【暑期观Cpp选手有感 + 安慰帖 】拒绝焦虑 朋友们
5109
6
...
骑手面经
5054
7
...
盲审顺利通过!!!!感谢盲审老师!
4147
8
...
清华毕业,细数自己24年秋招的艰辛与无用功(一)
4003
9
...
讨厌学校里的老登
4003
10
...
4.23校招&实习招聘信息汇总
3338
正在热议
#
牛客帮帮团来啦!有问必答
#
250597次浏览
5690人参与
#
来聊聊机械薪资天花板是哪家
#
6923次浏览
74人参与
#
正在实习的你,有转正机会吗?
#
77875次浏览
824人参与
#
为什么那么多公司毁约
#
29022次浏览
250人参与
#
求职季如何保持心态不崩
#
8584次浏览
169人参与
#
应届生应该先就业还是先择业
#
5287次浏览
71人参与
#
你已经投递多少份简历了
#
231680次浏览
3764人参与
#
机械制造2024笔面经
#
253095次浏览
4112人参与
#
租房前辈的忠告
#
16458次浏览
1206人参与
#
荣耀求职进展汇总
#
52469次浏览
591人参与
#
机械人的薪资开到多少,才适合去?
#
34289次浏览
181人参与
#
秋招开了,你想投哪些公司呢
#
95751次浏览
3055人参与
#
秋招提前批启动你开冲了吗
#
15543次浏览
644人参与
#
数据人的面试交流地
#
158407次浏览
3476人参与
#
比亚迪求职进展汇总
#
127138次浏览
1022人参与
#
没有实习经历,还有机会进大厂吗
#
241771次浏览
4519人参与
#
通信硬件人笔面经互助
#
45206次浏览
1050人参与
#
硬件兄弟们 甩出你的华为奖状
#
22914次浏览
153人参与
#
软件开发2024笔面经
#
953802次浏览
24452人参与
#
0offer互助地
#
30791次浏览
350人参与
牛客网
牛客企业服务