题目分析

我们有 N 台服务器的物料编码，每个编码中分别包含一段代表 CPU 型号的子串（格式为C后跟两位数字）、一段代表内存型号的子串（M+两位数字）、一段代表主板型号的子串（B+两位数字）。每个编码中，这三类备件可能出现多次，但我们只取各自第一次出现的型号；然后统计所有服务器下线后，可回收的不同型号及对应数量，按型号字典序输出。

核心问题是：如何从字符串中高效提取固定格式子串，并统计。

解题思路

1. 模式匹配

   • 对于每个物料编码字符串，使用正则表达式或手动扫描：
     • CPU 型号：C\d{2}
     • 内存型号：M\d{2}
     • 主板型号：B\d{2}
   • 从左到右找第一个匹配，分别得到三个型号。

2. 计数统计

   • 使用字典（或哈希表、map）记录每种型号出现的次数。
   • 处理完所有编码后，字典中键为型号，值为数量。

3. 结果输出

   • 对每类备件，将型号按字符串升序排序后输出，格式为：

     型号1,数量1;型号2,数量2;...
     

   • 若只有一个型号，则不加分号。

相关算法

• 正则匹配：时间复杂度与字符串长度成线性关系。
• 哈希统计：插入与查找均摊 O(1)。
• 排序：对 K 种型号排序需 O(K log K)。

复杂度分析

• 对每个编码（长度 L）进行三次正则查找：O(L)。共 N 台服务器，总时间 O(N L)。
• 最后对每类备件假设有 K 种型号排序：O(K log K)。通常 K ≪ N × L。
• 总体时间复杂度：O(N L + K log K)。
• 空间复杂度：O(N L) 用于存储输入，O(K) 用于统计字典。

代码实现

Python

import re
import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    codes = data[1:]
    
    cntCpu = {}
    cntMem = {}
    cntBoa = {}
    
    # 预编译正则
    pCpu = re.compile(r'C\d{2}')
    pMem = re.compile(r'M\d{2}')
    pBoa = re.compile(r'B\d{2}')
    
    for s in codes:
        # 提取第一次匹配
        m = pCpu.search(s)
        cpu = m.group() if m else ''
        m = pMem.search(s)
        mem = m.group() if m else ''
        m = pBoa.search(s)
        boa = m.group() if m else ''
        
        cntCpu[cpu] = cntCpu.get(cpu, 0) + 1
        cntMem[mem] = cntMem.get(mem, 0) + 1
        cntBoa[boa] = cntBoa.get(boa, 0) + 1
    
    # 按型号字典序输出
    def fmt(d):
        items = sorted(d.items())
        return ';'.join(f"{k},{v}" for k, v in items)
    
    print(fmt(cntCpu))
    print(fmt(cntMem))
    print(fmt(cntBoa))

if __name__ == '__main__':
    main()

Java

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine().trim());
        String[] codes = in.readLine().trim().split("\\s+");
        
        // TreeMap 保持键有序
        Map<String, Integer> cpuMap = new TreeMap<>();
        Map<String, Integer> memMap = new TreeMap<>();
        Map<String, Integer> boaMap = new TreeMap<>();
        
        Pattern pCpu = Pattern.compile("C\\d{2}");
        Pattern pMem = Pattern.compile("M\\d{2}");
        Pattern pBoa = Pattern.compile("B\\d{2}");
        
        for (String s : codes) {
            Matcher m = pCpu.matcher(s);
            String cpu = m.find() ? m.group() : "";
            m = pMem.matcher(s);
            String mem = m.find() ? m.group() : "";
            m = pBoa.matcher(s);
            String boa = m.find() ? m.group() : "";
            
            cpuMap.put(cpu, cpuMap.getOrDefault(cpu, 0) + 1);
            memMap.put(mem, memMap.getOrDefault(mem, 0) + 1);
            boaMap.put(boa, boaMap.getOrDefault(boa, 0) + 1);
        }
        
        // 输出格式化
        printMap(cpuMap);
        printMap(memMap);
        printMap(boaMap);
    }
    
    // 按要求格式化输出
    static void printMap(Map<String, Integer> map) {
        boolean first = true;
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<String, Integer> e : map.entrySet()) {
            if (!first) sb.append(";");
            sb.append(e.getKey()).append(",").append(e.getValue());
            first = false;
        }
        System.out.println(sb.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<string> codes(n);
    for (int i = 0; i < n; i++) {
        cin >> codes[i];
    }

    map<string, int> cpuMap, memMap, boaMap;
    // 正则模式
    regex rc("C\\d{2}");
    regex rm("M\\d{2}");
    regex rb("B\\d{2}");

    for (auto &s : codes) {
        smatch m;
        // CPU
        regex_search(s, m, rc);
        string cpu = m.size() ? m.str(0) : "";
        // Memory
        regex_search(s, m, rm);
        string mem = m.size() ? m.str(0) : "";
        // Board
        regex_search(s, m, rb);
        string boa = m.size() ? m.str(0) : "";

        cpuMap[cpu]++;
        memMap[mem]++;
        boaMap[boa]++;
    }

    // 输出函数
    auto printMap = [](const map<string,int>& M) {
        bool first = true;
        for (auto &p : M) {
            if (!first) cout << ";";
            cout << p.first << "," << p.second;
            first = false;
        }
        cout << "\n";
    };

    printMap(cpuMap);
    printMap(memMap);
    printMap(boaMap);

    return 0;
}

题目内容

某云站点有一批服务器待下线，已知这些服务器所对应的物料编码(代表不同服务器型号的标识字符串)，特定物料编码本身已包含$CPU$/内存/主板等备件型号，请计算出这批服务器下线后可回收不同的CPU/内存/主板型号和数量。物科编码只包含大写英文字母和数字，其中一定包含三类备件型号，它的固定格式是一个大写字母$+$两个数字。字母$C$代表$CPU$，$M$代表内存$Memory$，$B$代表主板$Board$。其他字母和数字可忽略，同类备件存在多个型号时取第一个。

输入描述

第一行为服务器个数 $N$ ，范围是 $[1,1000]$；

第二行为 $N$ 个物料编码字符串，依次用空格隔开。

输出描述

统一按照型号$1$,数量$1$；型号$2$,数量$2$；型号$3$,数量$3...$的格式输出：

第一行为$CPU$的型号和对应数量；

第二行为内存的型号和对应数量；

第三行为主板的型号和对应数量。

同类备件存在多个型号时按照字典序输出。

样例1

输入

2
C01M23B050130 C01M23B060130

输出

C01,2
M23,2
B05,1;B06,1

样例2

输入

3
C0CM23B05C130X11 C01M23B050130Y22 C01M24B05C130Z33

输出

C01,2;C13,1
M23,2;M24,1
B05,3