竞赛讨论区 > 【题解】牛客小白月赛36

【题解】牛客小白月赛36

头像
hx073269
发布于 2021-07-16 22:33:44 APP内打开
赞 7 | 收藏 0 | 回复3 | 浏览1646

前言

出题人:(ABC)Flash_plus、(DEFG)沙烬、(HIJ)hx073269
三毒瘤一拍即合,于是这场小白赛就孕育而出啦,希望大家玩的还算开心。
B题数据弱了,赛后已加强。

正文

A-好哥哥

考点:贪心
我们可以对括号序列进行建树操作,即:对于每对括号向他的好哥哥连边。你会发现,对于每对括号,我们可以走的其实就是他的祖先以及他的儿子,代价都是一样的。那么题目就可以转化成:在一颗树上,我们从根节点出发,规定步数内,最多可以遍历多少节点。
考虑最后的整个路径是一段重复的边,再加上一条从根开始的链。那么这个可以贪心,把两边的贡献分开考虑:对于那些需要重复的路径,代价是2(节点数 - 1);对于最后那条链,代价就是链的长度 - 1。那么贪心策略很明显,找出最长链,其他随意遍历,最后跑完最长链就行了。
时间复杂度:图片说明

B-最短串

考点:字符串匹配
首先判断一个字符串是否为另一个字符串的子串,如果是则答案为这两个字符串长度的较大值,否则进行以下操作:
设字符串a的前缀与字符串b的后缀的最大匹配长度为len1,字符串a的后缀与字符串b的前缀的最大匹配长度为len2,那么不难发现答案就是。所以我们可以暴力枚举这个最大匹配长度,然后再判断相应长度的前缀和后缀是否匹配即可。
时间复杂度:

C-杨辉三角

考点:组合数学
题目可以转化成这个样子:

那么推一波柿子:

注意本题是从0 n-1,所以就是相当于求该柿子 的值就可以了。
时间复杂度:O(log(n))

D-哥三好

考点:动态规划
总共三个人,每次三个人都有可能请客,对于该次请客我们只需要记录三个人未请客之前的情况方法数,加起来即可。所以最朴素的思想便是建立一个三维的DP,然后采用数字三角形模型递推即可。由于最低消费都是300/450/750,可以看到都是150的倍数,所以我们可以提前除掉150减少数组的大小。由于最后剩下150也请不了客,所以我们还需要加上人剩下钱的数目。
时间复杂度:

E-皇城PK

考点:签到
简单来说就是有人输过,就会发生实力和别人相等或者比别人低的情况,所以只需要记录没有输过的人即可,这里我们可以用桶纪录输过的人。
时间复杂度:

F-象棋

考点:思维
首先炮的攻击方式能保证结束的时候每一行最多不超过两个炮,这样我们可以先选取两行的跑,利用这两行去消灭其他行所有的炮(虽然炮消灭敌人会到敌人的位置,但是我们也可以反过来,让需要被消灭的跑打过来,这样该位置的炮就被消灭了)。然后在这两行里选取两列,重复上述操作,最后只会剩下两行两列,最多四个。
时间复杂度:O(T)

G-永不言弃

考点:拓扑排序+优先队列
首先一定要从第一个关卡开始打,如果第一个关卡都打不过去一定无法通过。其次每次通过一个关卡,都会获得一个道具,这个道具可以帮助我们通过其他关卡,所以我们可以将其他关卡的通关属性变成0,这样遇到该关卡时就一定能通过。我们每次保证先打当前解锁关卡中关卡属性需求最小的,这样如果打不过我们肯定无法通关,如果能打过,则将能解锁关卡打完。打完后由于游戏需要通过全部关卡,所以我们检验一遍是否通过了全部关卡即可。
可以用优先队列解决本题。
时间复杂度:

H-卷王之王

考点:暴力
首先我们得发现,每个数被加一次,至少倍增,因此每个数最多进行O(log(x))次加法。所以我们可以使用一个优先队列去暴力模拟这个过程,把所有小于等于x的数弹出来,对他们加上x后再加入优先队列。注意数据范围是非负整数,因此对于x0的情况我们直接跳过不处理,否则会导致超时的情况出现。
另外还有其他解法也可通过此题,但是从内测情况来看该题错误率较高,主要是因为数据中0的情况导致的。对于无法通过此题的选手,可以思考一下是否是含0的情况导致了程序错误。
时间复杂度:图片说明

I-四面楚歌

考点:搜索
简单的搜索题。我们使用DFS可以判断一个连通块是否是能够移动出边界的连通块,如果是我们则对这块连通块染色,最后统计所有染色的联通块内0的个数即可。
时间复杂度:

J-科学幻想

考点:线段树+字符串hash+二分
首先思考一下不带修改的版本如何做。对于判断两个字符串相等,我们可以使用字符串hash算法实现。但是题目要求的勉强相等,允许有一个字符不同。我们二分字符串的长度,对于每次的mid来说:
1.如果区间的hash值不等于区间的hash值且区间的hash值不等于区间的hash值,则证明两个字符串左区间和右区间都至少存在一个字符不同,即两个字符串不算勉强相等。
2.若只有区间的hash值不等于区间的hash值,则证明不同字符在左区间,令
3.若只有区间的hash值不等于区间的hash值,则证明不同字符在右区间,令
通过字符串hash+二分的做法即可判断两个字符串是否勉强相等。至于带修改的版本,使用线段树维护区间hash值即可实现。
时间复杂度:

标程:

A:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48148692
B:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48148708
C:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48148717
D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48148734
E:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48148756
F:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48148781
G:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48148785
H:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48148805
I:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48148825
J:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48148832

3条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐