阿里笔试阿里秋招大文娱笔试 1016

笔试时间：2025年10月16日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

小红有一个n×m的矩阵，矩阵第i行第j列的元素为i×j。小红想知道矩阵中第k小的元素是多少。

输入描述

第一行三个整数n, m, k。

数据范围：1 ≤ n, m ≤ 10^5，1 ≤ k ≤ n×m

输出描述

输出一个整数表示答案。

样例输入

3 3 4

样例输出

3

参考题解

解题思路：

使用二分查找，在1到n×m范围内寻找第k小的数。对于每个中间值mid，统计矩阵中小于等于mid的元素个数：

对于第i行，小于等于mid的元素个数为min(mid/i, m)
如果总数<k，说明答案在右半部分，否则在左半部分

C++：

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long long n, m, k;
    cin >> n >> m >> k;
    
    long long l = 1, r = n * m;
    while (l < r) {
        long long mid = (l + r) / 2;
        long long cnt = 0;
        for (int i = 1; i <= n; i++) {
            cnt += min(mid / i, m);
        }
        if (cnt < k) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    
    cout << l << endl;
    return 0;
}

Java：

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long m = sc.nextLong();
        long k = sc.nextLong();
        
        long l = 1, r = n * m;
        while (l < r) {
            long mid = (l + r) / 2;
            long cnt = 0;
            for (int i = 1; i <= n; i++) {
                cnt += Math.min(mid / i, m);
            }
            if (cnt < k) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        
        System.out.println(l);
    }
}

Python：

n, m, k = map(int, input().split())
l, r = 1, n * m
while l < r:
    mid = (l + r) // 2
    cnt = 0
    for i in range(1, n + 1):
        cnt += min(mid // i, m)
    if cnt < k:
        l = mid + 1
    else:
        r = mid
print(l)

第二题

牛牛所在的学校进行了期末考试，一共有n个人参加考试，考试共有m门科目。老师想给在至少一门考试中成绩超过该科目平均成绩的学生发祝福消息。请你计算需要发送祝福消息的学生人数。

输入描述

第一行输入两个整数n, m (1 ≤ n, m ≤ 1000)

此后m行，每行输入n个整数a_ij (0 ≤ a_ij ≤ 100)，表示第i门考试中第j个学生的成绩。

输出描述

输出一个整数，表示需要发送祝福消息的学生人数。

样例输入

2 2

3 2

2 3

样例输出

2

样例说明

在该样例中，两位学生在至少一个科目中成绩超过各自科目的平均分，因此答案为2。

参考题解

解题思路：

题目比较简单，模拟题目即可。计算每门科目的平均分，然后标记成绩超过平均分的学生，最后统计被标记的学生数量。

C++：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> scores(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> scores[i][j];
        }
    }
    
    vector<bool> stu(n, false);
    for (int j = 0; j < m; j++) {
        double course_avg = 0;
        for (int i = 0; i < n; i++) {
            course_avg += scores[j][i];
        }
        course_avg /= n;
        
        for (int i = 0; i < n; i++) {
            if (scores[j][i] > course_avg) {
                stu[i] = true;
            }
        }
    }
    
    int count = 0;
    for (bool s : stu) {
        if (s) count++;
    }
    
    cout << count << endl;
    return 0;
}

Java：

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int[][] scores = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                scores[i][j] = sc.nextInt();
            }
        }
        
        boolean[] stu = new boolean[n];
        for (int j = 0; j < m; j++) {
            double courseAvg = 0;
            for (int i = 0; i < n; i++) {
                courseAvg += scores[j][i];
            }
            courseAvg /= n;
            
            for (int i = 0; i < n; i++) {
                if (scores[j][i] > courseAvg) {
                    stu[i] = true;
                }
            }
        }
        
        int count = 0;
        for (boolean s : stu) {
            if (s) count++;
        }
        
        System.out.println(count);
    }
}

Python：

n, m = map(int, input().split())
scores = []
for _ in range(m):
    scores.append(list(map(int, input().split())))

stu = [False] * n
for j in range(m):
    course_avg = sum(scores[j]) / n
    for i in range(n):
        if scores[j][i] > course_avg:
            stu[i] = True

print(sum(stu))

第三题

小红有一个n行m列的数字矩阵，矩阵中全部是正整数。小红有q次操作，每次操作将矩阵中所有等于x的数染红。若之前已经对x染红过了，那么x将保持红色。每次操作结束后，小红想知道当前矩阵中红色连通块的数量。我们定义，若两个红色数字上下相邻或者左右相邻，则它们是连通的。

输入描述

第一行输入两个正整数n和m，用空格隔开，代表矩阵的行数和列数。接下来的n行，每行输入m个正整数a_ij，用来表示矩阵。接下来一行输入一个正整数q，代表操作次数。接下来的一行输入q个正整数x_i，代表小红每次操作将要染红的数字。数据范围： - 对于30%的数据，n, m ≤ 100 - 对于100%的数据，n, m ≤ 500，q ≤ 10^5，1 ≤ a_ij, x_i ≤ 10^6