首页
比赛
题库
课程
竞赛讨论区
登录
/
注册
去牛客
竞赛讨论区
>
【题解】南华大学第16届ACM程序设计大赛(重现赛)
塔子哥学算法
编辑于 2020-06-15 10:58
+ 关注
【题解】南华大学第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:数论,筛法,预处理
通过阅读伪代码发现:函数功能就是求一个数的最小素因子。由于询问比较多且数比较小,可以预处理利用素数筛将所有数的最小质因子筛出来,进行模拟即可。
直接模拟行不通,假设询问的都是质数,那么复杂度会跑到
(2)
(0)
分享
举报
浏览3944
2024最新求职资料大礼包领取
真题
历年笔试真题附答案
哔哩哔哩2021校园招聘移动端方向笔试卷
4399游戏校招游戏开发岗
云从科技2020校招软件测试笔试题
全部 >
面经
面试常考问题整理
腾讯三面已上岸
23届联想面经分享: 秋招上岸
22届-国企上岸经验分享
全部 >
内推
员工内推码获取
拼多多暑期实习
携程内推携程内推码
体验中心实习生招募 - 淘天集团
全部 >
大家都在关注
校招日程表
笔试日历
ai模拟面试
面试宝典
剑指offer
知识点专项练习
已采纳
采纳
精彩回帖
精彩
全部评论
(0)
回帖
加载中...
话题
同步到我的动态
回帖
返回全部帖子
本文相关内容
5982-南华大学第16届ACM程序设计大赛(重现赛)
进入比赛
等你来战
查看全部
牛客练习赛124_PLUS
报名截止时间:2024-04-26 22:00
牛客小白月赛92
报名截止时间:2024-04-28 21:00
武汉工程大学第六届ACM程序设计竞赛(同步赛)
报名截止时间:2024-04-29 16:00
2024牛客五一集训派对day1
报名截止时间:2024-05-01 17:00
2024牛客五一集训派对day2
报名截止时间:2024-05-02 17:00
2024牛客五一集训派对day3
报名截止时间:2024-05-03 17:00
2024牛客五一集训派对day4
报名截止时间:2024-05-04 17:00
2024牛客五一集训派对day5
报名截止时间:2024-05-05 17:00
牛客周赛 Round 41
报名截止时间:2024-05-05 21:00
哈尔滨华德学院第十五届程序设计竞赛(同步赛)
报名截止时间:2024-05-11 16:00
第四届上海理工大学程序设计全国挑战赛
报名截止时间:2024-05-12 17:00
牛客周赛 Round 42
报名截止时间:2024-05-12 21:00
热门推荐
发现好帖子?赶紧
收藏
一下!!精彩内容不错过
扫描二维码,关注牛客
意见反馈
下载牛客APP,随时随地刷题
全部评论
(0) 回帖