真正的题解

༺ཌༀ⚡☢WA君☢⚡ༀད༻

2026-08-22 11:20:11

发布于：广东

5阅读

0回复

0点赞

WA君の私房题：版本号校验题解

题目概述

本题给定 $n$ 个版本号字符串，要求判断它们是否全部合法，且按自定义顺序严格递增。版本号格式涵盖 Minecraft 历史上的多种命名方式，并包含若干愚人节特殊版本。

核心难点

本题看似是一道简单的字符串模拟题，但存在以下几个容易忽视的关键点：

版本号格式种类多：远古版、正式版、传统快照、预发布/候选版、语义化快照，每种格式的判定规则不同。
语义化快照有版本号限制：-snapshot- 格式的版本号必须 $\ge 26.1$ 。
愚人节版本为白名单精确匹配，不经过任何格式检查。
版本间的顺序规则不是纯字典序：远古版（以 a/b 开头）必须排在所有数字开头的版本之前。
愚人节版本之间不要求递增：它们可以任意排列。

解题思路

第一步：合法性判断

将版本号分为几类，按优先级依次检查：

1. 愚人节版本（最高优先级）

使用 unordered_set 存储白名单，精确匹配。命中则直接返回合法，不进行任何后续格式检查。

2. 远古版（Alpha / Beta）

格式：a1.2.3 或 b1.7.3。
判定方法：

正则匹配 ^[ab][0-9]+\.[0-9]+(\.[0-9]+)?$
去掉首字母后，按 . 分割，检查每段是否为合法数字（无前导零，纯数字，范围 $[0, 10^9]$ ）

3. 正式版

格式：26.1 或 26.1.2。
判定方法：

正则匹配 ^[0-9]+\.[0-9]+(\.[0-9]+)?$
分割后检查每段数字合法性

4. 传统快照

格式：23w18a（两位数年份 + w + 两位数周数 + 小写字母）。
判定方法：

正则匹配 ^[0-9]{2}w[0-9]{2}[a-z]$
无需额外检查年份和周数范围（题目未要求，简化处理）

5. 预发布版 / 候选版

格式：26.2-pre1、26.2-pre-2、26.2-rc1、26.2-rc-2。
判定方法：

正则匹配 ^[0-9]+\.[0-9]+(\.[0-9]+)?-(pre|rc)-?[0-9]+$
提取版本号部分检查数字合法性
提取后缀中的数字部分检查合法性

6. 语义化快照

格式：26.1-snapshot-1 或 26.1.2-snapshot-1。
判定方法：

正则匹配 ^[0-9]+\.[0-9]+(\.[0-9]+)?-snapshot-[0-9]+$
提取版本号部分，检查主版本号和次版本号
限制条件：必须满足 $主版本号 > 26$ 或 $(主版本号 = 26$ 且 $次版本号 \ge 1)$
检查 snapshot- 后面的数字合法性

第二步：顺序判断

比较规则

远古版（以 a 或 b 开头）始终排在非远古版（数字开头）之前。
同类版本之间按字典序比较。
愚人节版本之间不要求递增，但愚人节版本与非愚人节版本之间仍需按上述规则比较。

实现方法

定义比较函数 less(a, b)，判断 a 是否应排在 b 前面：

less(a, b):
    aIsAncient = (a[0] == 'a' || a[0] == 'b')
    bIsAncient = (b[0] == 'a' || b[0] == 'b')
    if aIsAncient && !bIsAncient: return true
    if !aIsAncient && bIsAncient: return false
    return a < b   // 字典序

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

// 愚人节白名单
bool isFoolVersion(const string& s) {
    static const unordered_set<string> fools = {
        "26w14a",
        "25w14craftmine",
        "23w13a_or_b",
        "22w13oneblockatatime",
        "20w14∞",
        "2.0",
        "1.RV-Pre1",
        "22w13oneBlockAtATime",
        "23w13AOrB"
    };
    return fools.count(s) > 0;
}

bool isNumberValid(const string& t) {
    if (t.empty()) return false;
    if (t.size() > 1 && t[0] == '0') return false;
    for (char c : t) {
        if (!isdigit(c)) return false;
    }
    long long v = stoll(t);
    return v >= 0 && v <= 1000000000LL;
}

bool isValid(const string& s) {
    if (isFoolVersion(s)) return true;

    regex ancient(R"(^[ab][0-9]+\.[0-9]+(\.[0-9]+)?$)");
    if (regex_match(s, ancient)) {
        string copy = s.substr(1);
        vector<string> parts;
        stringstream ss(copy);
        string part;
        while (getline(ss, part, '.')) {
            if (!isNumberValid(part)) return false;
        }
        return true;
    }

    regex formal(R"(^[0-9]+\.[0-9]+(\.[0-9]+)?$)");
    if (regex_match(s, formal)) {
        vector<string> parts;
        stringstream ss(s);
        string part;
        while (getline(ss, part, '.')) {
            if (!isNumberValid(part)) return false;
        }
        return true;
    }

    regex snapshot1(R"(^[0-9]{2}w[0-9]{2}[a-z]$)");
    if (regex_match(s, snapshot1)) return true;

    regex pre_rc(R"(^[0-9]+\.[0-9]+(\.[0-9]+)?-(pre|rc)-?[0-9]+$)");
    if (regex_match(s, pre_rc)) {
        size_t dash = s.find('-');
        string ver = s.substr(0, dash);
        string suffix = s.substr(dash + 1);
        vector<string> parts;
        stringstream ss(ver);
        string part;
        while (getline(ss, part, '.')) {
            if (!isNumberValid(part)) return false;
        }
        string numPart;
        for (char c : suffix) {
            if (isdigit(c)) numPart += c;
        }
        if (numPart.empty() || !isNumberValid(numPart)) return false;
        return true;
    }

    regex snapshot2(R"(^[0-9]+\.[0-9]+(\.[0-9]+)?-snapshot-[0-9]+$)");
    if (regex_match(s, snapshot2)) {
        size_t pos = s.find('-');
        string versionPart = s.substr(0, pos);
        vector<string> parts;
        stringstream ss(versionPart);
        string part;
        while (getline(ss, part, '.')) parts.push_back(part);
        if (parts.size() < 2) return false;
        if (!isNumberValid(parts[0]) || !isNumberValid(parts[1])) return false;
        int major = stoi(parts[0]);
        int minor = stoi(parts[1]);
        if (!(major > 26 || (major == 26 && minor >= 1))) return false;
        size_t snapPos = s.find("snapshot-") + 9;
        string numStr = s.substr(snapPos);
        if (!isNumberValid(numStr)) return false;
        return true;
    }

    return false;
}

// 自定义版本比较：远古版（a/b开头）< 数字开头，同类按字典序
bool versionLess(const string& a, const string& b) {
    bool aIsAncient = (a[0] == 'a' || a[0] == 'b');
    bool bIsAncient = (b[0] == 'a' || b[0] == 'b');
    if (aIsAncient && !bIsAncient) return true;
    if (!aIsAncient && bIsAncient) return false;
    return a < b;
}

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

    int n;
    if (!(cin >> n)) return 0;

    string last = "";
    bool lastIsFool = false;

    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;

        if (!isValid(s)) {
            cout << "Line " << i << ": Invalid format\n";
            return 0;
        }

        bool curIsFool = isFoolVersion(s);

        // 只有当 不是（上一行和当前行都是愚人节版本）时，才检查顺序
        if (i > 1 && !(lastIsFool && curIsFool)) {
            if (!versionLess(last, s)) {
                cout << "Line " << i << ": Out of order\n";
                return 0;
            }
        }

        last = s;
        lastIsFool = curIsFool;
    }

    cout << "OK\n";
    return 0;
}