题解 | #车辆限行#

题目链接

车辆限行

题目描述

根据输入的车牌号（取后五位）和星期几，判断哪些车辆在该日限行。

输入格式：

第一行包含一个或多个车牌号，以逗号 , 分割。
第二行包含一个数字，代表周几（1-7）。

规则：

车牌号校验：
- 每个车牌号必须恰好为 5 位。
- 车牌号不能全是字母。
- 如果任何一个车牌号格式错误，或未使用逗号分割，程序应输出 error。
尾号定义：
- 从车牌的第 5 位（末位）向前查找，找到的第一个数字即为该车牌的“尾号”。
限行规则：
- 周一 (1): 尾号为 1 或 9
- 周二 (2): 尾号为 2 或 8
- 周三 (3): 尾号为 3 或 7
- 周四 (4): 尾号为 4 或 6
- 周五 (5): 尾号为 5 或 0
- 周六 (6)、周日 (7): 不限行

输出格式：

若有车辆限行，输出所有限行车牌号，以逗号 , 分割。
若当天不限行或没有符合限行条件的车牌，输出 none。
若输入格式有误，输出 error。

解题思路

这是一个严谨的字符串处理和模拟问题，核心在于对输入进行严格的校验，并准确应用尾号查找和限行规则。

算法流程：

读取与分割输入：
- 读取包含所有车牌的字符串，以及代表星期的数字 day。
- 使用逗号 , 作为分隔符，将车牌字符串分割成一个车牌列表。
输入校验 (Error Handling)：
- 遍历分割后的车牌列表。
- 对列表中的每一个车牌 plate： a. 检查其长度是否等于 5。如果不等于，立即打印 error 并终止程序。 b. 检查其是否完全由字母组成。如果是，也立即打印 error 并终止程序。
- 如果所有车牌都通过了校验，则程序继续。
判断限行：
- 首先判断 day。如果 day 是 6 或 7，说明是周末不限行，直接打印 none 并结束。
- 如果 day 是 1 到 5，创建一个空列表 restricted_plates 用于存放限行的车牌号。
- 再次遍历车牌列表： a. 对于每个车牌 plate，调用一个辅助函数 get_tail_number(plate) 来获取其尾号。这个函数从字符串末尾向前遍历，返回第一个遇到的数字字符。 b. 根据 day 和获取到的尾号，使用 switch 或 if-else 结构判断该车牌是否在当天限行。 c. 如果限行，就将该车牌 plate 添加到 restricted_plates 列表中。
输出结果：
- 遍历结束后，检查 restricted_plates 列表： a. 如果列表为空，说明没有车牌限行，打印 none。 b. 如果列表不为空，使用逗号 , 将列表中的所有车牌号连接成一个字符串，并打印输出。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <cctype>

using namespace std;

// 校验单个车牌是否全为字母
bool is_all_alpha(const string& s) {
    for (char c : s) {
        if (!isalpha(c)) {
            return false;
        }
    }
    return true;
}

// 获取车牌的“尾号”
int get_tail_number(const string& plate) {
    for (int i = plate.length() - 1; i >= 0; --i) {
        if (isdigit(plate[i])) {
            return plate[i] - '0';
        }
    }
    return -1; // 根据题意，不会发生
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string line;
    if (!getline(cin, line)) {
        cout << "error" << endl;
        return 0;
    }
    
    string day_line;
    if (!getline(cin, day_line) || day_line.empty()) {
        cout << "error" << endl;
        return 0;
    }

    for (char c : day_line) {
        if (!isdigit(c)) {
            cout << "error" << endl;
            return 0;
        }
    }
    stringstream day_stream(day_line);
    int day;
    day_stream >> day;
    
    if (day < 1 || day > 7) {
        cout << "error" << endl;
        return 0;
    }

    stringstream ss(line);
    string segment;
    vector<string> plates;
    while (getline(ss, segment, ',')) {
        plates.push_back(segment);
    }

    // 校验
    for (const auto& plate : plates) {
        if (plate.length() != 5 || is_all_alpha(plate)) {
            cout << "error" << endl;
            return 0;
        }
    }

    if (day == 6 || day == 7) {
        cout << "none" << endl;
        return 0;
    }
    
    bool has_restriction_rule = (day >= 1 && day <= 5);
    if (!has_restriction_rule) { // Double check, though covered by validation
        cout << "none" << endl;
        return 0;
    }

    vector<string> restricted_plates;
    for (const auto& plate : plates) {
        int tail_num = get_tail_number(plate);
        bool restricted = false;
        switch (day) {
            case 1: if (tail_num == 1 || tail_num == 9) restricted = true; break;
            case 2: if (tail_num == 2 || tail_num == 8) restricted = true; break;
            case 3: if (tail_num == 3 || tail_num == 7) restricted = true; break;
            case 4: if (tail_num == 4 || tail_num == 6) restricted = true; break;
            case 5: if (tail_num == 5 || tail_num == 0) restricted = true; break;
        }
        if (restricted) {
            restricted_plates.push_back(plate);
        }
    }

    if (restricted_plates.empty()) {
        cout << "none" << endl;
    } else {
        for (size_t i = 0; i < restricted_plates.size(); ++i) {
            cout << restricted_plates[i] << (i == restricted_plates.size() - 1 ? "" : ",");
        }
        cout << endl;
    }

    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        if (!sc.hasNextLine()) { System.out.println("error"); return; }
        String line = sc.nextLine();
        
        if (!sc.hasNextLine()) { System.out.println("error"); return; }
        String dayLine = sc.nextLine();
        
        // 校验日期输入
        if (dayLine.isEmpty()) {
             System.out.println("error");
             return;
        }
        for (char c : dayLine.toCharArray()) {
            if (!Character.isDigit(c)) {
                System.out.println("error");
                return;
            }
        }
        int day = Integer.parseInt(dayLine);
        
        if (day < 1 || day > 7) {
            System.out.println("error");
            return;
        }
        
        String[] plates = line.split(",");
        
        // 校验
        for (String plate : plates) {
            if (plate.length() != 5 || isAllAlpha(plate)) {
                System.out.println("error");
                return;
            }
        }
        
        if (day == 6 || day == 7) {
            System.out.println("none");
            return;
        }
        
        List<String> restrictedPlates = new ArrayList<>();
        for (String plate : plates) {
            int tailNum = getTailNumber(plate);
            boolean restricted = false;
            switch (day) {
                case 1: if (tailNum == 1 || tailNum == 9) restricted = true; break;
                case 2: if (tailNum == 2 || tailNum == 8) restricted = true; break;
                case 3: if (tailNum == 3 || tailNum == 7) restricted = true; break;
                case 4: if (tailNum == 4 || tailNum == 6) restricted = true; break;
                case 5: if (tailNum == 5 || tailNum == 0) restricted = true; break;
            }
            if (restricted) {
                restrictedPlates.add(plate);
            }
        }
        
        if (restrictedPlates.isEmpty()) {
            System.out.println("none");
        } else {
            System.out.println(String.join(",", restrictedPlates));
        }
    }

    private static boolean isAllAlpha(String s) {
        for (char c : s.toCharArray()) {
            if (!Character.isLetter(c)) {
                return false;
            }
        }
        return true;
    }
    
    private static int getTailNumber(String plate) {
        for (int i = plate.length() - 1; i >= 0; i--) {
            if (Character.isDigit(plate.charAt(i))) {
                return Character.getNumericValue(plate.charAt(i));
            }
        }
        return -1; // Should not happen based on problem description
    }
}

import sys

def get_tail_number(plate):
    """从后向前查找第一个数字作为尾号"""
    for char in reversed(plate):
        if char.isdigit():
            return int(char)
    return -1 # 根据题意不会发生

def solve():
    try:
        line = sys.stdin.readline().strip()
        day_str = sys.stdin.readline().strip()
        
        # 严格校验输入行是否存在
        if not line or not day_str:
            print("error")
            return

        # 校验day_str是否为纯数字且在范围内
        if not day_str.isdigit():
            print("error")
            return
            
        day = int(day_str)
        if not (1 <= day <= 7):
            print("error")
            return

        plates = line.split(',')

        # 校验
        for plate in plates:
            if len(plate) != 5 or plate.isalpha():
                print("error")
                return
        
        if day in [6, 7]:
            print("none")
            return

        restriction_map = {
            1: {1, 9},
            2: {2, 8},
            3: {3, 7},
            4: {4, 6},
            5: {5, 0}
        }

        restricted_plates = []
        if day in restriction_map:
            restricted_nums = restriction_map[day]
            for plate in plates:
                tail_num = get_tail_number(plate)
                if tail_num in restricted_nums:
                    restricted_plates.append(plate)

        if not restricted_plates:
            print("none")
        else:
            print(",".join(restricted_plates))

    except (IOError, ValueError):
        # 异常输入也视为 error
        # ValueError会由isdigit检查提前捕获，这里主要处理IOError
        print("error")

solve()

算法及复杂度

算法：模拟、字符串处理
时间复杂度： $\mathcal{O}(L)$ ，其中 $L$ 是输入的第一行字符串的总长度。我们需要分割字符串（ $\mathcal{O}(L)$ ），然后遍历每个分割出的车牌进行校验和尾号查找。由于每个车牌长度固定为5，所以后续处理每个车牌的时间是常数。
空间复杂度： $\mathcal{O}(N)$ ，其中 $N$ 是车牌号的数量。需要一个列表来存储分割后的所有车牌号。