2021年寒假热身赛2

2021年寒假热身赛2

A.一

常规的进制转换问题。

参考代码(C++)

B.魔数

贪心算法。
如果一个数字由”1″,”14″,”144″构成,那么从前往后或者从后往前都可以,先检查最头上3位是不是“144”,若是就把检测位置移动3位,继续检测剩余的那些位。若不是144,类似地,就检查14,若通过就移动两位,否则检测是不是“1”。直到最后剩下空串,表示检测全通过。或者某个串这三次检测都未通过,则说明它不能由这三个数字组成。

参考代码(C++)

C.幼儿园

给定数列{a}中找一个子数列{s},使max{s} – min{s}最小。

将a排序,则a[i]是一个子列的开头且是最小值,a[i+M]是子列的结尾且为最大值,对所有可能的i,记录a[i+M]-a[i]的最小值即可。

参考代码(C++)

D.卧底探案

要求 有多少(i,j)使 \( j-i=A_i+A_j \),即求 \( j-A_j = i+A_i \),令\(L_k = k-A_k, R_k=k+A_k\),就变成一个搜索问题:对于每个\( \{L\} \)中的元素\( L_k \),查找在\( \{R\} \)中出现多少次。这样对R排序后用二分搜,时间复杂度\( O(N \log(N)) \)

参考代码(C++)

E.矿工挖宝箱

BFS+DP. 用二维数组acc,记下走到当前步累计最多可能得到的金矿,同时由于矿工奇特的前进方式,需要BFS逐层的走。走完之后如果右下角位置的acc仍为0,说明没能走到右下角,输出-1,否则输出最右下角的acc值即可。题目中同时需要BFS和更新acc,代码稍微长一些。

参考代码(C++)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注