竞赛讨论区 > 【题解】2020牛客寒假算法基础集训营第四场

【题解】2020牛客寒假算法基础集训营第四场

头像
nocriz
编辑于 2020-02-12 14:40:08 APP内打开
赞 21 | 收藏 18 | 回复54 | 浏览9478

这场比赛码量小,思维难度适中,不涉及任何高级算法,相信选手们能够顺利体会到AK AC的快乐:)

不知道由于什么原因,过了J的人都没有过I,难道是为了不AK吗?

欢迎在CF上friend出题人

注意:B题和I题数据已加强,且B题已rejudge。

A、欧几里得

考虑如果a>b,那么gcd(a,b)转移到的gcd(b,a%b)也满足b>a%b。于是我们相当于要从次数少一的一组a,b,将b加上一个或更多个a,就变成次数加一的了。可以观察出每次加一个a是最佳的,就是斐波那契数列。找规律水平高的选手,也可以使用找规律通过此题。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930010

B、括号序列

使用栈,从左到右处理每一个括号:

  • 如果是左括号,那么入栈,然后继续读下一个括号
  • 如果是右括号,那么就要看这个右括号和栈顶的括号是否匹配
  • 如果匹配,那么弹出栈顶的括号,继续读下一个括号,否则说明不合法
  • 最后,如果栈为空,说明此括号序列是合法的。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930024

C、子段乘积

本题可以使用线段树,也可以分治,还可以使用尺取法,维护当前区间中有几个0,同时维护不是0的数字的乘积,这种方法需要使用乘法逆元。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930034

D、子段异或

如果[l,r]是合法的子段,说明前缀和中xorsum[r]^xorsum[l-1] = 0, xorsum[l-1] = xorsum[r]。
求出异或前缀和,然后使用map计数每一个数字有多少个前缀和等于那个数字即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930043

E、最小表达式

我们拥有的可以放数字的数位的权值分别是1,1,1,1,1,...,1,10,10,10,10,...,10,100,...(每种各加号个数加一个),于是只需要贪心的将大的数字放到小权值的数位上即可。

考虑题目中的第四个样例:23984692+238752+2+34+
这个样例的数字排序后为['2', '2', '2', '2', '2', '3', '3', '3', '4', '4', '5', '6', '7', '8', '8', '9', '9'],加号有四个,则意味着我们要建立五个数字。每个数字从后向前添加数位,则先添加个位数,十位数,再添加百位数,等等等等。并且我们一定是按照顺序添加,不可能在个位数尚有未填写的情况去填另一个数字的百位数,因为不优。答案为
2369+2359+248+248+237=5461

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930064

F、树上博弈

首先,注意到输掉的唯一方法是自己的唯一一条边有另一个人,那么自己一定是在叶子上。
令两个人之间的距离为D。请注意,每人行动后D增加1或减少1。 因此,每有人走一步D的奇偶性都会改变。
假设最初,在牛牛移动之前,D是偶数。 那么当牛牛移动时D将始终为偶数,而当牛妹移动时D将始终为奇数。
请注意,只要牛牛和牛妹的令牌位于相邻的节点中,D=1。因此,如果D为偶数,则他们不在相邻的单元格中,并且牛牛始终可以移动。
另一方面,由于牛牛总是可以移动,因此他可以向牛妹的方向移动,将牛妹必然会最终移动到叶子上。同样,如果最初D是奇数,则牛妹获胜。
因此,答案取决于距离的奇偶性:如果是偶数,则牛牛获胜,否则牛妹获胜。
可以发现,只有牛牛的初始位置和牛妹的初始位置距离为偶数时,牛牛获胜。只需要分别求出深度为奇数的点和深度为偶数的点的数量即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930091

G、音乐鉴赏

如果随机占比为 ,一个人分数为 ,那么他优秀的概率为

这个概率可以这么计算:首先把分数减90,大于0就优秀,那么就变成,其中y是一个随机的0到90之间的数字。,这个概率就是上面所写的概率。

,解方程可知答案为

也可以使用二分求解。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930115

H、坐火车

从左向右遍历,使用树状数组维护每种颜色的该车厢左右的对数即可。

如下一个颜色是,应当先减去下一个颜色作为右边的匹配数,再加上当前颜色作为左边的匹配数,注意不要爆long long。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930143

I、匹配星星

这道题目可以使用贪心算法求解。先按照X坐标从小到大排序,然后对于每一个点

  • 如果Z = 1,查询比他X坐标小的Y坐标最大的Z= 0的点,进行配对,如果配对成功则将那个点都从候选点中排除。
  • 如果Z = 0,将该点加入候选点。

证明

假设最优方案中排序的第 1 个没有按贪心策略匹配的点 ,在设 中它能匹配的 最大的点为 ,如果 被点 匹配了,有两种情况:

  • 原先 没有和任何匹配,则直接去掉 的匹配,将 匹配。
  • 原先 匹配,则将 改成和 匹配,将 匹配,由于, 这样的匹配一定是成立的。并且修改后的匹配数不会变少,因此按照该贪心策略可以得到最优解。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930163

J、二维跑步

首先观察得到所有x坐标相同的位置无论y坐标如何是等价的,然后看出每走一步,如果x坐标增加1则有3种方案,x坐标不变有1种方案,x坐标减小1就有2种方案。

枚举x坐标不变了次,那么就有步x坐标改变。如果有次x坐标增加,则知道,那么就有

那么这种情况下的仅仅走路的方案数就是

考虑这个东西怎么求呢?首先,我们设,则显然有,这是由于。那么我们考虑如何做到地从推出了:我们考虑,如果错位相加,那么就能够正确的得出中的大多数项,而错误的项只在区间的一边,我们只需要消除这些错误影响即可。

而我们又知道当,那么这道题就解决掉了,复杂度为

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930188

被NTT卡过去了,早就该出1e7 QwQ。

54条回帖

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

等你来战

查看全部

热门推荐