[数据结构与算法]NENU 蓝桥杯训练赛（简单模拟+思维）题解

NENU 蓝桥杯训练赛（简单模拟+思维）题解

A Chocolate Thief

题意：

有 $n$ 个学生，每个学生有一块巧克力， $x,y,z$ 为巧克力的长、宽、高 。每个学生的巧克力长、宽、高可能不同，但体积是相同的。假设学生里最多有一个小偷，如果有小偷，他从另一个学生那里拿走了一部分巧克力。问是否有小偷？

思路：

找到体积的最大值 $Max$ 和最小值 $Min$ 。如果 $Max==Min$ ，则没有小偷；否则， 体积为 $Max$ 的学生偷了体积为 $Min$ 的学生的巧克力。

B Hidden Secret!

题意：

给定两个字符串，问对这两个字符串进行如下操作后，其是否相同？

• 可以把一些大写字母改成小写，反之亦然。
• 可以自由添加/删除空格。
• 可以排列字母。

思路：

对字符串进行如下操作，然后进行判断。

• 删除字符串中的空格 。
• 所有字母都变为小写。
• 对字符串按字典序升序排序。

C Scarecrow

题意：

有 $1\times N$ 的格子， $.$ 是有作物的格子， $\#$ 是没有作物格子，为了保护作物要在格子上放稻草人，每个稻草人可以保护它当前格和相邻格的作物。问至少需要多少个稻草人去保护作物？

思路：

用最少的稻草人去覆盖 $.$ 的格子，每个稻草人可以连续覆盖三个格子，贪心考虑在 $.$ 的格子上放稻草人一定不会比在 $\#$ 的格子上放稻草人差。从前往后遍历格子，判断当前格子是不是 $.$ ，如果是则往跳后三格。

D Again Array Queries

题意：

给定 $n$ 个数， $q$ 次询问，每次给两个数 $i,j$ ，问区间 $[i,j]$ 任意两数的最小差值是多少？

思路：

考虑到 $n$ 个数的范围为 $[1,1000]$ ，根据鸽巢原理可知，如果 $j?i+1>1000$ ，最小差值为 $0$ ；否则，可以利用桶排序去暴力判断 $[i,j]$ 的最小差值。

E Scenes From a Memory

题意：

给定一个 $k$ 位数，问可不可以删除一些位，让得到的数是一个非素数？

思路：

猜测这样的数不会超过 $3$ 位，暴力判断$[1,3]$位数。打表验证，这样的数不会超过 $2$ 位。

F Maximum Product

题意：

给定 $n$ 个数，任意取 $5$ 个数其乘积最大是多少？

思路：

把 $0$ 剔除后按升序排序得到数组 $a[1...k]$，如果少于 $5$ 个数，直接输出 $0$ 。
否则，取如下值的最大值：

• $a[k?4]\times a[k?3]\times a[k?2]\times a[k?1]\times a[k]$
• $a[1]\times a[2]\times a[k?2]\times a[k?1]\times a[k]$
• $a[1]\times a[2]\times a[3]\times a[4]\times a[k]$

G Sifid and Strange Subsequences

题意：

给定 $a[1...n]$ ，从中选出一些数 $b[1...m]$ ，$b[i]\in a[1...n]$ ，满足对于任意的 $i,j$ 有 $|b[i]?b[j]|\ge max(b[1...n])$ , 求 $m$ 的最大值？

思路：

把 $a[1...n]$ 按升序排序后，贪心考虑先把负数和 $0$ 取出来，然后求出 $min(|b[i]?b[j]|)$ ,再取满足条件的正数，同时不断更新 $min(|b[i]?b[j]|)$ 。

H Nastia and Nearly Good Numbers

题意：

给定两个正整数 $A,B$ ，问是否能找到三个不同的数 $x,y,z$ ，使得 $x+y=z$ ？ $x,y,z$ 满足以下条件：

• 如果一个整数能够整除 $A\times B$ ，那么它是好的。
• 否则，如果一个整数能够整除 $A$ ，那么它是几乎好的。
  $x,y,z$ 中要有一个数是好的，另外两个数是几乎好的。

思路：

• $B=1$ ，无解。
• $B=2$ ， $x=A,y=A\times 3,z=A\times 4$ 。
• $B>2$ ， $x=A,y=A\times (B?1),z=A\times B$ 。

I A-B Palindrome

题意：

给定一个由 $0,1,?$ 构成的字符串和 $a$ 个 $0$ ， $b$ 个 $1$ ，你可以在 $?$ 的位置填 $0,1$ ，问使得填完之后的字符串是否是回文串。

思路：

• 判断给定的字符串是否回文，即 $0$ 对 $0$ ，$1$ 对 $1$ 。
• 根据回文的性质暴力填 $0,1$ ,与 $0$ 对应的 $?$ 填 $0$ ，与 $1$ 对应的 $?$ 填 $1$ 。填完之后看 $0,1$ 是否用超了。
• 最后再把 $?$ 对应 $?$ 的位置填完。

J Repainting Street

题意：

有 $n$ 个有颜色的房子，第 $i$ 个房子的颜色为 $c_i$ 。Tom每天可以把连续 $k$ 个房子涂成同一种颜色，问最少多少天可以把所有房子涂成同一种颜色？

思路：

$c_i\in [1,100]$ ，可以暴力把所有房子涂成100种颜色分别需要多少时间算出来，然后取最小值。（该题跟C稻草人那题差不多，模改一下代码即可）