2021年寒假热身赛2
A.一
常规的进制转换问题。
B.魔数
贪心算法。
如果一个数字由”1″,”14″,”144″构成，那么从前往后或者从后往前都可以，先检查最头上3位是不是“144”，若是就把检测位置移动3位，继续检测剩余的那些位。若不是144，类似地，就检查14，若通过就移动两位，否则检测是不是“1”。直到最后剩下空串，表示检测全通过。或者某个串这三次检测都未通过，则说明它不能由这三个数字组成。
C.幼儿园
给定数列{a}中找一个子数列{s}，使max{s} – min{s}最小。
将a排序，则a[i]是一个子列的开头且是最小值，a[i+M]是子列的结尾且为最大值，对所有可能的i，记录a[i+M]-a[i]的最小值即可。
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)) \)
E.矿工挖宝箱
BFS+DP. 用二维数组acc，记下走到当前步累计最多可能得到的金矿，同时由于矿工奇特的前进方式，需要BFS逐层的走。走完之后如果右下角位置的acc仍为0，说明没能走到右下角，输出-1，否则输出最右下角的acc值即可。题目中同时需要BFS和更新acc，代码稍微长一些。