第15届湖南大学ACM校赛题解

A题: Oshino Shinobu loves Mr.Donut

题意:每一回合有几种甜甜圈分配方式可以选择,求最后在拿的甜甜圈数量不大于忍野忍的情况下最多可以拿多少甜甜圈。

题解:dp(i,j)代表第i回合和忍野忍差距为j的时候最多可以拿多少甜甜圈,然后n^2递推。


B题:Kuangyeye's Resistance

题目大意:计算图中n级网络的等效电阻
图片说明
解题思路:
图片说明


C题: One Piece

题目大意:给出一个32位的整数n,求该整数二进制数表达式中1的个数。
解题思路:

假设二进制表示n=01000100,则n-1 = 01000011
我们可以发现n&(n-1) = 01000000

所以,每次进行 n&(n-1) 的操作实质就是抹掉n最右边的1

或者可以将n转化为无符号整数后,直接调用C/C++自带的函数__builtin_popcount()得出


D题:Kth hright

题意:两个队伍,每个队伍有n个人,每个队伍都按身高升序.有m次操作,每次操作讲某个队伍的某个人替换,且替换后该队伍依然是升序的,求每次替换后两个队伍中第k高的人,输出身高。

题解:
本问题等价于求两个有序序列第k大,一般很容易想到的做法是遍历O(n)但本题有m次询问故会超时。注意本题的k是小于等于n的,那么结果必定在1号数组1
n和2号数组1n之间。
设当前A数组有效范围从l1(初始为1)到r1(初始为k),B数组有效范围从l2(初始为1)到r2(初始为k),要取这两个范围内的第k大的值,
可以采取以下方法: **
**①:当k为1时,取两个A[l1]和B[l2]较小的结果范围答案,否则进行②操作

②:比较A[l1–k/2 + 1]和B[l2–k/2+1]的大小,删除较小部分的前k/2个元素,同时更新k,跳回操作①
m次操作,每次操作至多log2(n)次,故时间复杂度为mlog(n)


E题:Just calculat

图片说明

图片说明
图片说明


F题:Cards With Numbers

题意:
起始有一个空的序列,有两种操作:
0 x表示向序列中插入数字x
1 x表示查询序列中是否有数据x

对于每个查询输出yes或者no分别表示有和没有
操作数规模1e6,x范围0~1e9,时限1s,空间256M

解题思路:
(1) 1e6的输入规模,需要读入优化,这个不会的自行百度“读入挂”即可。
(2) 对于一个数字x,我们只需判断它存在或者不存在,也就是说这是个非0即1的问题。
对于这个非0即1的问题,考虑以下三种思路:

(1)STL里的map(或者手写AVL树),这个的时间复杂度是O(nlog n),1s会TLE

(2)用bool数组,O(n)的时间复杂度是可以了,但是O(max{x})的空间复杂度是不行的。由于x的数据范围是0~1e9,那么bool数组的size就有可能需要达到1e9,也就是需要1G的内存,显然会MLE

(3)对于(2)进行优化,计算机里能够表示0或者1的最小单位不是bool,而应该是bit,1个字节是8个bit,如果可以用bit来表示0或1,则一个字节就可以表示8个数,1e9个bit占用空间也就是1e9/8字节,也就是大约125M。时间复杂度也是O(n)的,O(1)的插入,O(1)的查询。虽然这是最初设想的正解,但是呢,实际上这题用哈希也能AC。。。
图片说明


G题:Longest Palindrome Substring

题意:判断给定字符串的最长回文子串的长度是否大于1

做法1:用manacher算法在O(n)的时间内求出所给字符串的最长回文子串,看长度是否大于1

做法2:观察易知,长的回文串中间必然包含短的回文串。
例如回文串abccba中间包含回文串bccb和cc,回文串abcba中间包含长度大于一的回文串bcb。
所以字符串的最长回文子串长度是1等价于不存在长度为2和为3的回文子串(如果长度>=2,那么必然包含为2 的或者为3的)。
不存在长度为2的回文子串→s[i]!=s[i+1]
不存在长度为3的回文子串→s[i]!=s[i+2]
循环所有的合法的i,都满足上述两条则最长回文子串长度为1,否则大于1.


H题:

题意:给定两个长度不超过1e5的字符串,求这两个字符串的最长公共回文串。

时限1s,空间256M
解题思路

首先将两个字符串拼接起来,中间用特殊符号进行分隔。

然后构建这个新的字符串的回文树以及它的fail树。

根据fail树的性质,问题就转化为树上是否存在某个节点,该节点的right集合同时包含两个字符串,而该节点的right集合为其子节点的right集合并。

因此对该fail树dfs递归遍历一遍即可求出每个节点的right集合。

时间复杂度为o(n)。
(二分+hash也可过,甚至比正解跑的快)


I题:Algorithm Choosing Mashrooms

图片说明

图片说明
图片说明
图片说明


J题:Simple Problem

图片说明
图片说明
图片说明
图片说明
图片说明
图片说明
图片说明

图片说明

K题:Water Problem

图片说明

图片说明
图片说明
图片说明
图片说明
图片说明

全部评论
懂了,但是没完全懂
点赞 回复 分享
发布于 2021-05-18 20:33
题解很详细,赞😁
点赞 回复 分享
发布于 2019-06-02 09:57

相关推荐

程序员花海:实习和校招简历正确格式应该是教育背景+实习+项目经历+个人评价 其中项目经历注意要体现业务 实习经历里面的业务更是要自圆其说 简历模板尽可能保持干净整洁 不要太花哨的
点赞 评论 收藏
分享
2025-12-16 22:19
已编辑
南昌市第三中学 Java
个人背景:27届本科 江西普通一本院校个人经历:小厂->用友->蔚来->美团->腾讯不知不觉已经有了五段实习经历,也快在外面漂泊一年半了,在今年也完成了两年前自己想进大厂的目标,可能在别人看来确实就是一段比较传奇的过程,一步一步都在向上走,也会有很多人来问我相关学习实习的一些问题,我看到了也会尽量去回复,但现在我想给大家说的并不是千篇一律的学习路线,而是我认为更为重要的——勇气与抉择。下面我来分享一下这些年的心路历程最初学习背景:我跟很多人一样,都是刚进入大学才开始接触计算机,也刚刚拥有自己的电脑,在刚开始学习的过程没有任何人来帮助我,给予我相关的指导,完全是自己摸索出来的一条学习路线,不会有如今这样有很多完善好的速成路线,而家里人都在想让我考研,似乎本科以我的学历就业是不现实的。我也很早意识到了学历对于我的限制,所以萌生出了大一就开始实习的想法,但这个想法在当时基本上是不存在。所有人都在抨击我(这里感兴趣的话可以看我最早发的帖子),有的人说本科想进大厂痴人说梦,有的人劝我以我的学历考研才是上策,有的人说我屁都不懂就来卷,总之我很难说去看到有支持的。我大一的时候还没卷成如今这样很多大一实习,当我想找到是否有跟我一样下定决心一步一步往上走的人,我当时是没有找到的,要么是秋招的哀嚎,要么就直接是零实习进大厂(现在我知道,这里所谓的普通学历0实习进大厂的水分有很多,排除真正意义上的运气和实力,其他基本上全是造假作弊,大家自己心知肚明,也要放平心态)这就导致了一个没有先例的情况,很多人也都是拿没有先例来抨击我,包括家里人也不支持我去实习,可能很多人的积极性就会下降,但我从来不会信所谓的不可能,如果没有先例,那我就会是第一个,他们不行,是因为他们没能力,他们坚持不下去。勇气是很重要的,当你发现你身边没有人像你一样,就很少会有人相信你,看好你,但好在,我不在乎。最初实习阶段:在最初3000沟通只有零星几个面试的时候,那感觉确实很不好受,沉没成本太大,得到的正反馈却太少,当时基本上都是一天学八个小时从来不间断,没有周末没有节假日,甚至过年我都在学习,这就导致我现在都会因为我周末偶尔休息的时候会有负罪感,我感觉已经是种病了,我也知道我也可以休息会但控制不了。当时我出去实习口袋里有1w块(这是我高中三年加大一一年存下来的,基本上是很抠很抠,一个月生活费有时候有一千多有时候就五六百,但也算得上是成功攒了一点钱)但第一次总会是很害怕,担心租房被骗,担心工作能力不行,担心被公司坑,担心学校原因导致不能实习等等,基本上在前面几段实习是根本不攒钱的,代课已经花了一万多,加上租房来回,基本上只能说堪堪不负支出,后来远赴北京,作为一个南方人,有很多不适应的地方,但现在回过头来一想,已经在北京呆了一年多了。我知道很多人要么担心学校因素,要么担心赚的还没花的多,种种因素导致了实习的困难,我也很害怕,我的钱会不会最终全部打水漂,学校会不会爆雷,我以后还能顺利实习吗等等。但对于我来说,我能对自己狠下心,我能接受通勤时间一个半小时只为节省那么几百块的房租钱,我能控制自己的消费的欲望,我能每个月大把大把把钱给代课,这可能就是我能够初期实习顺利的原因,这需要勇气,也需要对自己狠。实习中的抉择:在有了两段实习经历后,我的目标就朝着大厂进发,在去蔚来的中途,我oc了七八家中小厂公司,这里面不乏一些待遇极其优越的公司(有一家我真的差点就去了),但我最终还是都拒了,因为我清楚的明白想往上走的,只有公司title会帮你说话,没有人有义务理解你的困难你的坚持,好在最后去了蔚来,也算如愿以偿。从蔚来到美团倒是没有过多纠结,因为在最开始的梦中情厂就是美团,但从美团去腾讯这个决定或许是我人生中的转折点。美团多次挽留我,帮我沟通问hr,基本上就是一定能转暑期然后成功转正,仿佛这年薪40w的工作已经触手可得,所以在拿到腾讯offer的那一刻并没有多高兴,因为我意识到这可能是我此生最接近大厂的一次机会,可能大部分人都会选择留在美团,我也认为这一定是一个好的选择。我能够走到如今,是永远相信自己的判断,我的每一步都是在赌一个好的未来,只不过,这次赌注大了点而已,或许未来我再也进不了这些所谓的大厂,但我赌的不是选择错对,我赌我不后悔。所谓信念支撑:都说人要为自己而活,但我或许做不到,毕竟我身处人情社会,有许多爱我的人在等着我成长,我也不能接受因为能力而再次放弃一段感情,最近喜欢一段歌词:爱我的人相信我我一直在努力改变所有失败为你们而存在爱我的人感谢你你们的爱就算人生不是精彩我也要勇敢的姿态最后的最后,我想给大家传递的从来都不是一个普通学历进入大厂的意气风发,我想给大家传递的,是一股相信自己能够向上的信念和可能性。在没有打比赛能力,没有开源能力,没有学历等各个限制下,我帮大家试出了一条能够向上的路。如果没有先例,那我会是第一个。我们不需要弄虚作假,只靠自己一步一步脚踏实地,哪怕慢一点,不赌自己是否成功,只赌自己不后悔,问心无愧。最后送给大家,也送给自己一段话结束2025:生活可能没你想的那么好,也不会像你想的那么糟,人的脆弱和坚强,都超乎了你的想象,有时候可能脆弱的一句话就泪流满面,有时候你发现自己咬咬牙已经走了很长的路了
等闲_:感觉咱们双非的同学都有一个共性,想证明双非也是能进大厂的,我之前所有的标签都喜欢带着双非,仿佛这样可以像别人证明自己的实力,现在我却不再想证明双非到底能不能进大厂,我的生活的所有者是我自己,享受生活,接受结果
2025年终总结
点赞 评论 收藏
分享
评论
3
5
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务