程序員基德

03-22 10:50 中國(guó)科學(xué)技術(shù)大學(xué) C++ 發(fā)布于浙江

關(guān)注

【春招筆試】2025.03.15-阿里淘天機(jī)考筆試改編題

? 春招備戰(zhàn)指南 ?

?? 學(xué)習(xí)建議：

先嘗試獨(dú)立解題（建議用時(shí)：90分鐘/套）
對(duì)照解析查漏補(bǔ)缺
配套練習(xí)題庫(kù)

?? 題面描述背景等均已深度改編，做法和題目本質(zhì)基本保持一致。

?? 感謝各位朋友們的訂閱，你們的支持是我們創(chuàng)作的最大動(dòng)力

春秋招合集 -> 互聯(lián)網(wǎng)必備刷題寶典??

淘天2025.03.15題目集

題目一：子數(shù)組MEX值統(tǒng)計(jì)

1??：利用容斥原理，將子數(shù)組按MEX值分類(lèi)統(tǒng)計(jì)

2??：通過(guò)計(jì)算不包含特定數(shù)字的子數(shù)組數(shù)量，避免直接枚舉

3??：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)

難度：中等

題目二：部落聯(lián)盟探索

1??：使用BFS/DFS找出所有連通分量（親密部落）

2??：在遍歷過(guò)程中統(tǒng)計(jì)每個(gè)連通分量相鄰的不同敵對(duì)部落

3??：時(shí)間復(fù)雜度O(n×m)，適用于給定的數(shù)據(jù)范圍

難度：中等

題目三：區(qū)間乘積求和

1??：將數(shù)組按0分段，分別處理每個(gè)不含0的段

2??：對(duì)于全1的段直接計(jì)算，對(duì)于其他段枚舉起點(diǎn)計(jì)算乘積

3??：利用乘積超過(guò)10^9即停止計(jì)算的特性?xún)?yōu)化時(shí)間復(fù)雜度

難度：中等

01. 子數(shù)組MEX值統(tǒng)計(jì)

問(wèn)題描述

小蘭最近在研究一種特殊的數(shù)組統(tǒng)計(jì)方法。對(duì)于一個(gè)整數(shù)數(shù)組，她定義了一個(gè)叫做"MEX"（Minimum EXcluded）的值，即數(shù)組中未出現(xiàn)的最小非負(fù)整數(shù)。例如，數(shù)組 $\{1,2,3\}$ 的MEX值為0，數(shù)組 $\{0,2,5\}$ 的MEX值為1。

現(xiàn)在，小蘭有一個(gè)由 $n$ 個(gè)整數(shù)組成的數(shù)組 $\{a_1, a_2, ..., a_n\}$ ，其中每個(gè)元素的值都在0到2之間（包括0和2）。她想要計(jì)算這個(gè)數(shù)組的所有連續(xù)非空子數(shù)組的MEX值之和。

連續(xù)非空子數(shù)組是指從原數(shù)組中選取連續(xù)的一段元素形成的新數(shù)組，且至少包含一個(gè)元素。

輸入格式

第一行輸入一個(gè)整數(shù) $n$ $(1 \leq n \leq 2 \times 10^5)$ ，表示數(shù)組的長(zhǎng)度。

第二行輸入 $n$ 個(gè)整數(shù) $a_1, a_2, ..., a_n$ $(0 \leq a_i \leq 2)$ ，表示數(shù)組中的元素。

輸出格式

輸出一個(gè)整數(shù)，表示所有連續(xù)非空子數(shù)組的MEX值之和。

樣例輸入

3
1 1 0

樣例輸出

樣例解釋說(shuō)明

樣例1	長(zhǎng)度為1的子數(shù)組：[1]的MEX=0，[1]的MEX=0，[0]的MEX=1，總和為0+0+1=1 長(zhǎng)度為2的子數(shù)組：[1,1]的MEX=0，[1,0]的MEX=2，總和為0+2=2 長(zhǎng)度為3的子數(shù)組：[1,1,0]的MEX=2，總和為2 所有子數(shù)組的MEX值之和為1+2+2=5

數(shù)據(jù)范圍

$1 \leq n \leq 2 \times 10^5$
$0 \leq a_i \leq 2$

題解

這道題目要求計(jì)算數(shù)組所有連續(xù)非空子數(shù)組的MEX值之和。由于數(shù)組中的元素只有0、1、2三種可能，所以子數(shù)組的MEX值只可能是0、1、2或3。

我們可以根據(jù)MEX的定義，將所有子數(shù)組分為四類(lèi)：

MEX=0：子數(shù)組中不包含0
MEX=1：子數(shù)組中包含0但不包含1
MEX=2：子數(shù)組中包含0和1但不包含2
MEX=3：子數(shù)組中同時(shí)包含0、1和2

關(guān)鍵思路是：不直接枚舉所有子數(shù)組（這樣復(fù)雜度會(huì)達(dá)到O(n2)），而是統(tǒng)計(jì)每種MEX值對(duì)應(yīng)的子數(shù)組個(gè)數(shù)，然后乘以對(duì)應(yīng)的MEX值求和。

具體算法步驟：

計(jì)算數(shù)組的所有連續(xù)非空子數(shù)組總數(shù)： $total = \frac{n(n+1)}{2}$
統(tǒng)計(jì)不包含特定數(shù)字的子數(shù)組個(gè)數(shù)：
- 定義函數(shù)countNo(x)：統(tǒng)計(jì)不包含數(shù)字x的子數(shù)組個(gè)數(shù)
- 定義函數(shù)countNoPair(x,y)：統(tǒng)計(jì)不同時(shí)包含數(shù)字x和y的子數(shù)組個(gè)數(shù)
計(jì)算各類(lèi)MEX值的子數(shù)組個(gè)數(shù)：
- MEX=0的子數(shù)組個(gè)數(shù)：cnt_mex0 = countNo(0)
- MEX=1的子數(shù)組個(gè)數(shù)：cnt_mex1 = countNo(1) - countNoPair(0,1)
- MEX=2的子數(shù)組個(gè)數(shù)：cnt_mex2 = countNo(2) - countNoPair(0,2) - countNoPair(1,2)
- MEX=3的子數(shù)組個(gè)數(shù)：cnt_mex3 = total - (cnt0 + cnt1_all + cnt2_all) + (cnt01 + cnt02 + cnt12)
計(jì)算最終答案：ans = 0×cnt_mex0 + 1×cnt_mex1 + 2×cnt_mex2 + 3×cnt_mex3

對(duì)于countNo和countNoPair函數(shù)，我們可以通過(guò)掃描數(shù)組，找出連續(xù)不包含特定數(shù)字的段，然后利用公式 $\frac{L(L+1)}{2}$ 計(jì)算這些段中的子數(shù)組個(gè)數(shù)。

時(shí)間復(fù)雜度：O(n)，我們只需要掃描數(shù)組常數(shù)次。空間復(fù)雜度：O(n)，用于存儲(chǔ)輸入數(shù)組。

參考代碼

Python

import sys
input = lambda:sys.stdin.readline().strip()

def calc_no(arr, x):
    # 統(tǒng)計(jì)不包含數(shù)字x的子數(shù)組數(shù)量
    res = 0
    len_seg = 0
    
    for num in arr:
        if num == x:
            # 計(jì)算當(dāng)前段的子數(shù)組數(shù)量并累加
            res += len_seg * (len_seg + 1) // 2
            len_seg = 0
        else:
            len_seg += 1
    
    # 處理最后一段
    res += len_seg * (len_seg + 1) // 2
    return res

def calc_no_pair(arr, x, y):
    # 統(tǒng)計(jì)不同時(shí)包含x和y的子數(shù)組數(shù)量
    res = 0
    len_seg = 0
    
    for num in arr:
        if num == x or num == y:
            # 計(jì)算當(dāng)前段的子數(shù)組數(shù)量并累加
            res += len_seg * (len_seg + 1) // 2
            len_seg = 0
        else:
            len_seg += 1
    
    # 處理最后一段
    res += len_seg * (len_seg + 1) // 2
    return res

def main():
    n = int(input())
    arr = list(map(int, input().split()))
    
    # 計(jì)算所有子數(shù)組的總數(shù)
    total = n * (n + 1) // 2
    
    # 統(tǒng)計(jì)不包含特定數(shù)字的子數(shù)組數(shù)量
    cnt0 = calc_no(arr, 0)  # 不包含0的子數(shù)組
    cnt1 = calc_no(arr, 1)  # 不包含1的子數(shù)組
    cnt2 = calc_no(arr, 2)  # 不包含2的子數(shù)組
    
    # 統(tǒng)計(jì)不同時(shí)包含兩個(gè)特定數(shù)字的子數(shù)組數(shù)量
    cnt01 = calc_no_pair(arr, 0, 1)  # 不同時(shí)包含0和1的子數(shù)組
    cnt02 = calc_no_pair(arr, 0, 2)  # 不同時(shí)包含0和2的子數(shù)組
    cnt12 = calc_no_pair(arr, 1, 2)  # 不同時(shí)包含1和2的子數(shù)組
    
    # 計(jì)算各類(lèi)MEX值的子數(shù)組個(gè)數(shù)
    cnt_mex0 = cnt0  # MEX=0：不包含0
    cnt_mex1 = cnt1 - cnt01  # MEX=1：包含0但不包含1
    cnt_mex2 = cnt2 - cnt02 - cnt12  # MEX=2：包含0和1但不包含2
    
    # 使用容斥原理計(jì)算MEX=3的子數(shù)組個(gè)數(shù)
    cnt_mex3 = total - (cnt0 + cnt1 + cnt2) + (cnt01 + cnt02 + cnt12)
    
    # 計(jì)算最終答案
    ans = 1 * cnt_mex1 + 2 * cnt_mex2 + 3 * cnt_mex3
    print(ans)

if __name__ == "__main__":
    main()

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

// 統(tǒng)計(jì)不包含數(shù)字x的子數(shù)組數(shù)量
ll count_no(const vector<int>& arr, int x) {
    ll res = 0;
    ll seg_len = 0;
    
    for (int val : arr) {
        if (val == x) {
            // 計(jì)算當(dāng)前段的子數(shù)組數(shù)量并累加
            res += seg_len * (seg_len + 1) / 2;
            seg_len = 0;
        } else {
            seg_len++;
        }
    }
    
    // 處理最后一段
    res += seg_len * (seg_len + 1) / 2;
    return res;
}

// 統(tǒng)計(jì)不同時(shí)包含x和y的子數(shù)組數(shù)量
ll count_pair(const vector<int>& arr, int x, int y) {
    ll res = 0;
    ll seg_len = 0;
    
    for (int val : arr) {
        if (val == x || val == y) {
            // 計(jì)算當(dāng)前段的子數(shù)組數(shù)量并累加
            res += seg_len * (seg_len + 1) / 2;
            seg_len = 0;
        } else {
            seg_len++;
        }
    }
    
    // 處理最后一段
    res += seg_len * (seg_len + 1) / 2;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> arr(n);
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    // 計(jì)算所有子數(shù)組的總數(shù)
    ll total = (ll)n * (n + 1) / 2;
    
    // 統(tǒng)計(jì)不包含特定數(shù)字的子數(shù)組數(shù)量
    ll cnt0 = count_no(arr, 0);  // 不包含0的子數(shù)組
    ll cnt1 = count_no(arr, 1);  // 不包含1的子數(shù)組
    ll cnt2 = count_no(arr, 2);  // 不包含2的子數(shù)組
    
    // 統(tǒng)計(jì)不同時(shí)包含兩個(gè)特定數(shù)字的子數(shù)組數(shù)量
    ll cnt01 = count_pair(arr, 0, 1);  // 不同時(shí)包含0和1的子數(shù)組
    ll cnt02 = count_pair(arr, 0, 2);  // 不同時(shí)包含0和2的子數(shù)組
    ll cnt12 = count_pair(arr, 1, 2);  // 不同時(shí)包含1和2的子數(shù)組
    
    // 計(jì)算各類(lèi)MEX值的子數(shù)組個(gè)數(shù)
    ll mex0 = cnt0;  // MEX=0：不包含0
    ll mex1 = cnt1 - cnt01;  // MEX=1：包含0但不包含1
    ll mex2 = cnt2 - cnt02 - cnt12;  // MEX=2：包含0和1但不包含2
    
    // 使用容斥原理計(jì)算MEX=3的子數(shù)組個(gè)數(shù)
    ll mex3 = total - (cnt0 + cnt1 + cnt2) + (cnt01 + cnt02 + cnt12);
    
    // 計(jì)算最終答案
    ll ans = 1 * mex1 + 2 * mex2 + 3 * mex3;
    cout << ans << "\n";
    
    return 0;
}

Java

import java.util.*;

public class Main {
    // 統(tǒng)計(jì)不包含數(shù)字x的子數(shù)組數(shù)量
    public static long countNo(int[] arr, int x) {
        long res = 0;
        long segLen = 0;
        
        for (int val : arr) {
            if (val == x) {
                // 計(jì)算當(dāng)前段的子數(shù)組數(shù)量并累加
                res += segLen * (segLen + 1) / 2;
                segLen = 0;
            } else {
                segLen++;
            }
        }
        
        // 處理最后一段
        res += segLen * (segLen + 1) / 2;
        return res;
    }
    
    // 統(tǒng)計(jì)不同時(shí)包含x和y的子數(shù)組數(shù)量
    public static long countPair(int[] arr, int x, int y) {
        long res = 0;
        long segLen = 0;
        
        for (int val : arr) {
            if (val == x || val == y) {
                // 計(jì)算當(dāng)前段的子數(shù)組數(shù)量并累加
                res += segLen * (segLen + 1) / 2;
                segLen = 0;
            } else {
                segLen++;
            }
        }
        
        // 處理最后一段
        res += segLen * (segLen + 1) / 2;
        return res;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        // 計(jì)算所有子數(shù)組的總數(shù)
        long total = (long)n * (n + 1) / 2;
        
        // 統(tǒng)計(jì)不包含特定數(shù)字的子數(shù)組數(shù)量
        long cnt0 = countNo(arr, 0);  // 不包含0的子數(shù)組
        long cnt1 = countNo(arr, 1);  // 不包含1的子數(shù)組
        long cnt2 = countNo(arr, 2);  // 不包含2的子數(shù)組
        
        // 統(tǒng)計(jì)不同時(shí)包含兩個(gè)特定數(shù)字的子數(shù)組數(shù)量
        long cnt01 = countPair(arr, 0, 1);  // 不同時(shí)包含0和1的子數(shù)組
        long cnt02 = countPair(arr, 0, 2);  // 不同時(shí)包含0和2的子數(shù)組
        long cnt12 = countPair(arr, 1, 2);  // 不同時(shí)包含1和2的子數(shù)組
        
        // 計(jì)算各類(lèi)MEX值的子數(shù)組個(gè)數(shù)
        long mex0 = cnt0;  // MEX=0：不包含0
        long mex1 = cnt1 - cnt01;  // MEX=1：包含0但不包含1
        long mex2 = cnt2 - cnt02 - cnt12;  // MEX=2：包含0和1但不包含2
        
        // 使用容斥原理計(jì)算MEX=3的子數(shù)組個(gè)數(shù)
        long mex3 = total - (cnt0 + cnt1 + cnt2) + (cnt01 + cnt02 + cnt12);
        
        // 計(jì)算最終答案
        long ans = 1 * mex1 + 2 * mex2 + 3 * mex3;
        System.out.println(ans);
        
        sc.close();
    }
}

02. 部落聯(lián)盟探索

問(wèn)題描述

小基是一位人類(lèi)學(xué)家，正在研究一個(gè)古老國(guó)家的部落分布。這個(gè)國(guó)家的領(lǐng)土可以看作一個(gè) $n$ 行 $m$ 列的矩陣，每個(gè)單元格中都居住著一個(gè)部落，用小寫(xiě)字母表示。

小基發(fā)現(xiàn)，同一個(gè)部族的成員如果居住在相鄰的單元格中，他們會(huì)形成一個(gè)"親密部落"。具體來(lái)說(shuō)，如果兩個(gè)單元格 $(x,y)$ 和 $(p,q)$ 滿(mǎn)足以下條件：

它們包含相同的部族字母（ $s_{x,y} = s_{p,q}$ ）
它們?cè)诘乩砩舷噜彛?span id="npdgxvi1zkhb" class="math math-inline"> $|x-p| + |y-q| = 1$ ，即上下左右四個(gè)方向）

那么這兩個(gè)單元格屬于同一個(gè)親密部落。

現(xiàn)在，小基想要分析每個(gè)單元格所在的親密部落與多少個(gè)不同的敵對(duì)部落（非本部族的部落）相鄰。兩個(gè)部落相鄰是指存在一個(gè)單元格屬于第一個(gè)部落，另一個(gè)單元格屬于第二個(gè)部落，且這兩個(gè)單元格在地理上相鄰。

請(qǐng)幫助小基完成這項(xiàng)研究。

輸入格式

第一行輸入兩個(gè)整數(shù) $n, m$ $(1 \leq n, m \leq 500)$ ，表示矩陣的行數(shù)和列數(shù)。

接下來(lái) $n$ 行，每行包含一個(gè)長(zhǎng)度為 $m$ 的字符串，由小寫(xiě)字母組成，表示每個(gè)單元格中的部落。

輸出格式

輸出 $n$ 行，每行 $m$ 個(gè)整數(shù)，用空格分隔。第 $i$ 行第 $j$ 個(gè)整數(shù)表示位于 $(i,j)$ 的單元格所在的親密部落與多少個(gè)不同的敵對(duì)部落相鄰。

樣例輸入

3 3
baa
aab
cac

樣例輸出

1 2 2
2 2 2
1 2 2

樣例解釋說(shuō)明

樣例1	以位置(1,2)的'a'部落為例，它所在的親密部落包含5個(gè)單元格：(1,2)、(1,3)、(2,1)、(2,2)和(3,2)。這個(gè)親密部落與'b'和'c'兩個(gè)不同的敵對(duì)部落相鄰，所以答案是2。

數(shù)據(jù)范圍

$1 \leq n, m \leq 500$
輸入中的字符均為小寫(xiě)字母

題解

這道題目要求我們找出每個(gè)單元格所在的親密部落與多少個(gè)不同的敵對(duì)部落相鄰。

首先，我們需要理解什么是"親密部落"：同一個(gè)字母（部族）的相鄰單元格組成一個(gè)親密部落。這實(shí)際上就是圖論中的連通分量概念。

解題思路如下：

使用廣度優(yōu)先搜索(BFS)或深度優(yōu)先搜索(DFS)找出所有的連通分量（親密部落）
對(duì)于每個(gè)連通分量，統(tǒng)計(jì)與之相鄰的不同敵對(duì)部落（不同字母）的數(shù)量
將每個(gè)單元格映射到其所在的連通分量，輸出相應(yīng)的敵對(duì)部落數(shù)量

具體實(shí)現(xiàn)步驟：

創(chuàng)建一個(gè)二維數(shù)組comp，用于標(biāo)記每個(gè)單元格所屬的連通分量編號(hào)
創(chuàng)建一個(gè)數(shù)組enemyCount，記錄每個(gè)連通分量相鄰的不同敵對(duì)部落數(shù)量
使用BFS遍歷矩陣：
- 對(duì)于每個(gè)未訪(fǎng)問(wèn)的單元格，以它為起點(diǎn)進(jìn)行BFS
- 將同一部族且相鄰的單元格標(biāo)記為同一個(gè)連通分量
- 在BFS過(guò)程中，記錄與當(dāng)前連通分量相鄰的不同部族
最后，輸出每個(gè)單元格所在連通分量的敵對(duì)部落數(shù)量

時(shí)間復(fù)雜度分析：

每個(gè)單元格最多被訪(fǎng)問(wèn)一次，所以BFS的時(shí)間復(fù)雜度是O(n*m)
對(duì)于每個(gè)單元格，我們需要檢查其四個(gè)相鄰位置，這是常數(shù)時(shí)間
總體時(shí)間復(fù)雜度為O(n*m)

空間復(fù)雜度：

需要O(n*m)的空間來(lái)存儲(chǔ)連通分量標(biāo)記和隊(duì)列
總體空間復(fù)雜度為O(n*m)

這個(gè)解法在給定的數(shù)據(jù)范圍(n,m≤500)下是高效的。

參考代碼

Python

import sys
input = lambda:sys.stdin.readline().strip()
from collections import deque

def main():
    # 讀取輸入
    n, m = map(int, input().split())
    grid = [input() for _ in range(n)]
    
    # 初始化連通分量標(biāo)記數(shù)組，-1表示未訪(fǎng)問(wèn)
    comp = [[-1 for _ in range(m)] for _ in range(n)]
    # 存儲(chǔ)每個(gè)連通分量的敵對(duì)部落數(shù)量
    enemy_cnt = []
    
    # 四個(gè)方向：上、下、左、右
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    comp_id = 0
    # 使用BFS找出所有連通分量
    for i in range(n):
        for j in range(m):
            if comp[i][j] == -1:  # 未訪(fǎng)問(wèn)過(guò)的單元格
                tribe = grid[i][j]  # 當(dāng)前部族
                enemies = set()  # 存儲(chǔ)相鄰的敵對(duì)部落
                
                # BFS
                q = deque([(i, j)])
                comp[i][j] = comp_id
                
                while q:
                    x, y = q.popleft()
                    
                    # 檢查四個(gè)方向
                    for dx, dy in dirs:

剩余60%內(nèi)容，訂閱專(zhuān)欄后可繼續(xù)查看/也可單篇購(gòu)買(mǎi)

互聯(lián)網(wǎng)刷題筆試寶典文章被收錄于專(zhuān)欄

互聯(lián)網(wǎng)刷題筆試寶典，這里涵蓋了市面上大部分的筆試題合集，希望助大家春秋招一臂之力