MCC 近期批量发放 OA中，题目难度适中，大概用时90分钟，我们一起来看看题目内容吧。

Array Reduction 1

There is an array of n integers called num. The array can be reduced by 1 element by performing a move. Each move consists of the following three steps:

1. Pick two different elements num[i] and num[j], where i ≠ j.
2. Remove the two selected elements from the array.
3. Add the sum of the two selected elements to the end of the array.

Each move has a cost associated with it: the sum of the two elements removed from the array during the move. Calculate the minimum total cost of reducing the array to one element.

Example

num = [4, 6, 8]
Remove 4 and 6 in the first move at a cost of 4 + 6 = 10, and the resultant array is num' = [8, 10].
Remove 8 and 10 in the second move at a cost of 8 + 10 = 18, and the resultant array is num" = [18].
The total cost of reducing this array to one element using this sequence of moves is 10 + 18 = 28.

Function Description

Complete the function reductionCost in the editor below.

reductionCost has the following parameter(s):

• int num[]: an array of integers

Return:

• int: the minimum total cost of reducing the input array to one element

Complete the function reductionCost in the editor below.

reductionCost has the following parameter(s):

• int num[]: an array of integers

Return:

• int: the minimum total cost of reducing the input array to one element

数组归约 1

有一个包含 n 个整数的数组 num。可以通过执行一次移动来将数组归约一个元素。每次移动包含以下三个步骤：

1. 选择两个不同的元素 num[i] 和 num[j]，其中 i ≠ j。
2. 从数组中移除这两个选定的元素。
3. 将这两个选定元素的和添加到数组的末尾。

每次移动都有一个与之关联的成本：在移动过程中从数组中移除的两个元素的和。计算将数组归约到一个元素所需的最小总成本。

示例

num = [4, 6, 8]  
  
在第一次移动中，移除 4 和 6，成本为 4 + 6 = 10，结果数组为 num' = [8, 10]。  
在第二次移动中，移除 8 和 10，成本为 8 + 10 = 18，结果数组为 num" = [18]。  
  
使用这种移动序列将数组归约到一个元素所需的总成本为 10 + 18 = 28。

函数描述

在以下编辑器中完成函数 reductionCost。

reductionCost 的参数：

• int num[]：一个整数数组

返回值：

• int：将输入数组归约到一个元素所需的最小总成本

解决方案

为了有效地解决这个问题，我们可以使用贪心算法配合堆（例如最小堆）来跟踪数组中的最小元素。但是，使用动态规划（DP）或递归加记忆化的方法对于较小的 n 也是有效的。

2. Connected Groups

Relationships between people may be represented in a matrix as a series of binary digits. For example, the direct relationships for person 0 with persons 0 through 5 might be shown as 101100. This means that person 0 knows persons 0, 2, and 3, the indices of each of the 1 values.

A relationship is transitive. In other words, if person 0 knows person 2 and person 2 knows person 3, then person 0 knows person 3 through person 2. A group is composed of all the people who know one another, whether directly or transitively.

Example

Consider the following relationships matrix:

• Persons 0 and 1 are connected, while person 2 is not.
• There are 2 groups.

Task

Determine the number of groups represented in a matrix.

Note

• The method signatures may vary slightly depending on the requirements of the chosen language. For example, C language will have an argument that represents the number of rows and columns in the matrix. Also, Java will receive a list rather than an array.

Function Description

Complete the function countGroups in the editor below.

countGroups has the following parameter(s):

• A matrix representing the relationships between people.

Return an integer representing the number of groups in the matrix.

2. 连通群组

人与人之间的关系可以用矩阵中的二进制数字来表示。例如，对于人员0与人员0到5的直接关系，可以表示为101100。这意味着人员0认识人员0、2和3，这些数字1的索引表示他们之间存在关系。

关系是传递的。换句话说，如果人员0认识人员2，且人员2认识人员3，那么人员0就通过人员2认识人员3。一个群组由所有相互认识的人员组成，无论这种认识是直接的还是通过传递的。

示例

考虑以下关系矩阵：

• 人员0和人员1是连通的，而人员2不是。
• 总共有2个群组。

任务

确定矩阵中表示的群组数量。

注意

• 方法签名可能会因所选语言的要求而略有不同。例如，C语言将有一个表示矩阵行数和列数的参数。而Java将接收一个列表而不是数组。

函数描述

在下面的编辑器中完成countGroups函数。

countGroups函数具有以下参数：

• 一个表示人员之间关系的矩阵。

返回一个整数，表示矩阵中的群组数量。

3. Build a Wall

Problem Statement

A brick is defined as a rectangle with a height of 1 and a width of either 2 units or 3 units. You are provided with an infinite supply of bricks. Each brick can have one of two possible widths: 2 units or 3 units. Your task is to build a wall of a specified width and height. The wall should be constructed in such a way that it consists of horizontal rows of bricks. However, the bricks must be arranged in a way that the right edge of a brick in one row does not align vertically with the right edge of a brick in the row directly above or below it. This is to ensure the stability of the wall.

Write a Python function that takes two arguments: the width and the height of the wall. The function should return the count of all possible ways to build the wall that meet the criteria.

For example, if the width is 5 and the height is 1, the function would compute that there are 2 possible ways to build the wall: (3,2) and (2,3), representing the two valid ways to arrange the bricks, and would return 2.

(23)  (23)

is not allowed, but

(23)  (32)

is valid.

Constraints

If it is not possible to build the wall with the given width and height, the function should return zero.

3. 建造一堵墙

题目描述

定义砖块为一个矩形，其高度为1，宽度可以为2个单位或3个单位。给定无限数量的砖块，每种砖块有两种可能的宽度：2个单位或3个单位。你的任务是建造一个指定宽度和高度的墙。墙应由水平排列的砖块行组成，但砖块必须按照以下方式排列：一行中砖块的右边缘不能与直接上方或下方的砖块的右边缘垂直对齐，以确保墙的稳定性。

编写一个Python函数，该函数接受两个参数：墙的宽度和高度。该函数应返回满足条件的所有可能建造墙的方式的数量。

示例

如果宽度为5且高度为1，函数将计算有两种可能的建造方式，并返回2。

约束条件

• 如果无法用给定的宽度和高度建造墙，则函数应返回零。

We successfully tackled these two questions in just over ten minutes. If you require assistance with completing Online Assessments (OA), please do not hesitate to contact us. Additionally, we offer services such as interview proxying and interview coaching. Our goal is to provide you with comprehensive support to ensure you excel in your career endeavors.

我们仅用十几分钟就成功解决了这两道题目。如果您需要帮助完成O），请随时联系我们。此外，我们还提供面试代面和面试辅导等服务。我们的目标是为您提供全面的支持，确保您在职业生涯中取得成功。