2023-12-15 21:19 已编辑浙江理工大学 C++

关注

牛客小白月赛 83 出题人题解

A. 小天的金银铜铁

按题意模拟，判断 $A\times a+B\times b+C\times c-D\times d>e$ 即可。

B. 小天的魔法 Ⅰ

$a\ b$ 不等长。按照排序不等式，降序排序后，取短的长度。若 $a$ 不足长，可以在后面补 $1$ 。

考虑最小操作次数。

对于当前决策是否使用魔法 $2$ 时，使用两个魔法 $2$ 的伤害为 $b_i+b_{i+1}$ ，因为 $b_i\geq b_{i+1}$ ，若 $a_i>1$ ，那么使用一个魔法 $2$ 和一个魔法 $1$ 的伤害为 $a_i\times b_i\geq b_i+b_{i+1}$ 。所以从前往后贪心地使用魔法，如果当前 $a_i>1$ ，则先用魔法 $1$ 再用魔法 $2$ ，反之就一直使用魔法 $2$ 。

一个小细节是：如果当前直接使用魔法 $2$ 就能击败，那么就不用使用魔法 $1$ 了。

时间复杂度： $O(n\log n)$

验题过程中发现的一个做法是， $a,b$ 降序后，直接枚举用多少魔法 1 即可。

时间复杂度： $O(nm)$

C.小天的 Minecraft

按题意分析，只有：

16 个铜粒
12 个铜粒，4 个银粒
12 个铜粒，4 个金粒

三种情况是可以做出铜镐的。

那么计算这三种情况的概率之和即可。

$(\frac{a}{16})^{16}+\tbinom{16}{12}(\frac{a}{16})^{12}\times(\frac{b}{16})^{4}+\tbinom{16}{12}(\frac{a}{16})^{12}\times (\frac{c}{16})^4$ 。

$\tbinom{16}{12}$ 直接算也可以（很小不会爆 int），杨辉三角递推也行。

D.小天的子序列

因为题目不要求本质不同，所以要考虑 $ch_1$ 和 $ch_2$ 的所有位置。因为开头和结尾确定了，那么子序列可以选择的范围也就确定了。所以，假设 $s_i=ch_1,s_j=ch_2\ (i<j)$ 。那么 $(i,j)$ 对答案的贡献即为： $\binom{j-i}{len-2}$ 。

虽然 $(i,j)$ 是 $n^2$ 基本的，但是 $j-i$ 是 $O(n)$ 级别的，所以对每一对字符 $(s_i,s_j)$ $j-i$ 计个数，询问时枚举 $[0,n-2]$ 的长度计算总贡献即可。

组合数使用杨辉三角递推预处理即可。

预处理： $O(n^2)$ ，单组询问 $O(n)$ 。

还有一些 $O(n^2|c|^2)$ 或者 $O(n^3)$ 之类的 $dp$ 这里不赘述了。

这里提一下出题人的另一个做法，每次暴力枚举 $ch_1$ 和 $ch_2$ 的位置集合，计算答案，然后记忆化。理论上单次询问貌似： $O(n^2)$ 但是出题人认为均摊之后卡不掉。

E.小天的贪吃蛇

对于两种路线，可以预处理成序列。

转换成序列后，那么就是在一个序列上，带修维护从某一个位置开始，连续相同字符的长度。

一个经典的直接的做法是：线段树维护 position，查询使用线段树上二分。

但是没有必要。在此题的范围下，只要维护每种字符的 position 集合。支持增删改查。询问时，枚举所有字符，二分找到出现位置在 $(x,y)$ 之后的最小位置，减 $1$ 即可。使用 set 维护 position。

时间复杂度： $O(n\log n\sum |c|)$ 。

F.小天的 A+B

$a\oplus b=2\max\{a,b\}$ 。将 $2$ 放入 $\max$ 内，且将 $\max$ 展开后，对于一般形式可以发现：

$a_1\oplus a_2\oplus ...\oplus a_n=\max\{2^{n-1}a_1,2^{n-1}a_2,2^{n-2}a_3,...,2^1a_n\}$ 。

同时： $2^{30}>10^9$ 。所以实际上系数才是影响结果的核心因素。

若区间长度不超过 30 ，直接枚举即可。
若区间长度超过 30 ，则需要继续分类讨论：
若区间内有正数，那么应该从中最靠近的一个正数开始，往后暴力找个位置。（同时，因为 2^n 过大，所以先提出一个公因式，找到最值后乘回去）
若区间内有零且没有正数，答案即为 0 。
若区间内全是负数，则从往前找 30 个位置即可（处理同上）。

判断区间内是否有正数、0 同时支持修改，使用 set 分别维护正数、0 的 position 集合即可。

全部评论

推荐最新楼层

07-11 14:24

中南大学 C++

985计算机考研失败，无实习无项目，华为OD能要我吗？华为OD真的毁简历吗？

今天给大家分享的是一位粉丝的提问，985计算机考研失败，无实习无项目，华为OD能要我吗？华为OD真的毁简历吗？接下来把粉丝的具体提问和我的回复分享给大家，希望也能给一些类似情况的小伙伴一些启发和帮助。同学提问：基本背景：考研失败的985毕业生，计算机专业，刚刚本科毕业没有就业/升学去向。无实习经历和项目经历。自身情况：目前在gap，计划明年秋天去留学，主申计算机/高性能计算/机器人/人工智能专业。11月份大概能把申请等事情完成。性格内向，社交能力较差。学校期间没接触过java, 408基础薄弱。目标方向：想去华为od，在明年入学前从实践中去学习技术，体验一下职场环境。需求与问题：需求：不打算润...

投递华为等公司10个岗位

点赞评论收藏

不愿透露姓名的神秘牛友

07-11 12:31

我从来没想过我会出轨

以前小时候我最痛恨出轨、偷情的人，无论男女，为什么会出轨？现在我成了自己最讨厌的人，没想到分享的东西在牛客会被这么多人看，大家的评价都很中肯，我也认同，想过一一回复，但我还是收声了，我想我应该说说这件事，这件事一直压在我心里，是个很大的心结，上面说了人为什么出轨，我大概能明白了。我们大一下半年开始恋爱，开始恋爱，我给出了我铭记3年的承诺，我对她好一辈子，我永远不会背叛，我责任心太重，我觉得跟了我，我就要照顾她一辈子，我们在一起3年我都没有碰过她，她说往东我就往东，她说什么我做什么，她要我干什么，我就干什么！在学校很美好，中途也出过一些小插曲，比如男闺蜜、男闺蜜2号等等等。但我都强迫她改掉了，我...

牛客刘北：两个缺爱的人是没有办法好好在一起的，但世界上哪有什么是非对错？你后悔你们在一起了，但是刚刚在一起的美好也是真的呀，因为其他人的出现，你开始想要了最开始的自己，你的确对不起自己，21岁的你望高物远，你完全可以不谈恋爱，去过你想要的生活，你向往自由，在一起之后，你要想的不是一个人，而是两个人，你不是变心了，就像你说的，你受够了，你不想包容了，冷静几天是你最优的选择，爱人先爱己。

社会教会你的第一课

点赞评论收藏