首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
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:数论,筛法,预处理
通过阅读伪代码发现:函数功能就是求一个数的最小素因子。由于询问比较多且数比较小,可以预处理利用素数筛将所有数的最小质因子筛出来,进行模拟即可。
直接模拟行不通,假设询问的都是质数,那么复杂度会跑到
提示
全部评论
推荐
最新
楼层
小红书
校招火热招聘中
官网直投
相关推荐
突尼斯海怪0
04-19 14:44
已编辑
上海理工大学 计算机类
还得是大公司啊,见世面了
真的见世面了。。太太太太太太太太幸运了,真的收获满满,开心到飞起,赶紧发帖留念!再次感慨找工作真的要找大公司,资源都是顶配,你能接触到的项目级别、人脉级别、技术栈都是小公司无法比的。我是今年报名参加了欧莱雅BRANDSTORM大赛,遗憾的是没有进全国总决赛,但是好处是被抽中邀请来观赛总决赛了,我想的是长长见识,而且名额机会都非常宝贵,加上我又刚好在上海,没有不来的道理!!!欧莱雅BRANDSTORM大家应该都知道了,前段时间牛客上各种美发黑科技的话题讨论,就是今年的赛题,看科技怎么赋能美发黑科技,我看现场介绍好像是有7500多个队伍参赛,现在是全国18强进入全国总决赛,选出中国冠亚,到时候可以...
点赞
评论
收藏
转发
谁是托尼
04-24 15:11
Java
入职蚂蚁,谈谈感受
我在蚂蚁的技术部门工作已经有一段时间了,从最初的兴奋到现在的适应,我对这家公司有了更深的了解。蚂蚁的技术体系非常庞大和深奥,能够支撑起规模庞大的用户流量。在学习公司的研发流程时,我发现每一个环节都充满挑战,需要编写详尽的系统分析文档并通过评审才能启动研发工作,这种严谨的工作流程让我从中学到很多。薪资待遇方面,公司提供全额五险一金、稳定月收入过万,周末也有双休。
投递蚂蚁集团等公司10个岗位 >
点赞
评论
收藏
转发
被普调的熊猫很想去毕业旅行
03-14 15:34
算法工程师
985本硕,这样的简历能不能找一家暑期算
点赞
评论
收藏
转发
纠结的牛牛在看面经
昨天 14:43
电子科技大学 电子信息类
soul一面
鼠鼠开头多说一句,面试官人巨好,很耐心的跟我讲不要紧张,直接治好了上周面试造成的的ptsd 1.自我介绍 2.问项目 延展问八股 2.1Lora的参数除了秩大小有哪些 2.2ptuning V2具体实现过程,以一个attention layer举例,描述tensor前后形状变化 2.3lora、ptuning v2以及fine tuning的区别 2.4past_key_value在传统的transformer中的作用 3.问论文 cv和nlp两篇论文中,表示对cv的更感兴趣一点,就论文问了一些问题 4.反问部门业务
投递APP Annie Ltd等公司7个岗位 >
点赞
评论
收藏
转发
2
收藏
评论
分享
回复帖子
全站热榜
1
...
(全时间段)暑期租房攻略来啦!全是干货!
4.8W
2
...
HR面试面经问题汇总(共计30+问题,2500+字数)
2.1W
3
...
机械/制造笔面经第二期,发面经攒人品!周周💸有奖🎁
1.6W
4
...
【软件开发专场】2024笔面经第二期!发面经攒人品赢奖励💴
9750
5
...
面试阿里云,遇到了找实习最逆天的一次拷打
9671
6
...
阿里国际 1个小时40分钟
6728
7
...
除了有个爱我的漂亮女朋友,什么都没了
5633
8
...
当下面试现状
4845
9
...
【奖💰】通信硬件薪资爆料②
4703
10
...
盲审出结果了
4232
正在热议
#
牛客帮帮团来啦!有问必答
#
293873次浏览
6383人参与
#
我在牛爱网找对象
#
46071次浏览
292人参与
#
应届生应该先就业还是先择业
#
8903次浏览
96人参与
#
非技术岗薪资爆料
#
1615次浏览
72人参与
#
华为求职进展汇总
#
423216次浏览
4241人参与
#
来聊聊机械薪资天花板是哪家
#
13132次浏览
103人参与
#
第一次面试
#
7900次浏览
121人参与
#
为什么那么多公司毁约
#
30915次浏览
262人参与
#
数据人的面试交流地
#
161109次浏览
3533人参与
#
你觉得比亚迪今年还有春招吗?
#
34302次浏览
238人参与
#
找工作,你会甘心进小厂还是猛冲大厂
#
20177次浏览
194人参与
#
硬件兄弟们 甩出你的华为奖状
#
23932次浏览
163人参与
#
如果再来一次,你还会学硬件吗
#
16049次浏览
325人参与
#
租房前辈的忠告
#
19078次浏览
1544人参与
#
字节跳动工作体验
#
46117次浏览
1211人参与
#
机械人的薪资开到多少,才适合去?
#
36516次浏览
207人参与
#
机械人怎么评价今年的华为
#
45384次浏览
359人参与
#
你觉得通信/硬件有必要实习吗?
#
19386次浏览
393人参与
#
聊聊这家公司值得去吗
#
57002次浏览
955人参与
#
你已经投递多少份简历了
#
236611次浏览
3829人参与
牛客网
牛客企业服务