📝 题目大意

题目 ID 按字典序分配：先所有长度为 1 的大写字符串（A-Z），再所有长度为 2 的（AA-ZZ），长度为 3 的（AAA-ZZZ），以此类推。给定一个合法的 ID 字符串 $S$，求它是第几题。

💡 解题思路

1. 题目分析：

   • $S$ 长度最大为 $12$（因为 $26^{12} \approx 10^{17}$，而题目总数是 $10^{16}$，样例 3 中的 "BRUTMHYHIIZP" 长度为 12 且恰好是第 $10^{16}$ 题）。
   • 本质上是一个类 26 进制计数问题，但有一个关键区别：更短的字符串全部排在更长的字符串之前。

2. 算法推导：

   • 设 $n = |S|$，即输入字符串的长度。
   • 第一步：用 res 累加所有长度 $< n$ 的字符串总数。
     • 长度为 $1$ 的有 $26$ 个，长度为 $2$ 的有 $26^2$ 个，...，长度为 $n-1$ 的有 $26^{n-1}$ 个。
     • 代码中 add 从 $26$ 开始，每次循环 res += add，然后 add *= 26，循环 $n-1$ 次。
     • 即 $res = 26 + 26^2 + \cdots + 26^{n-1}$。
   • 第二步：用 num 计算 $S$ 在长度为 $n$ 的所有字符串中的排名（从 0 开始）。
     • 将 $S$ 视为一个 26 进制数，其中 A=0, B=1, ..., Z=25。
     • 遍历 $S$ 的每个字符，num = num * 26 + (s[i] - 'A')。
     • 例如："AA" → num = 0 × 26 + 0 = 0（排在长度为 2 的第 1 个）；"AB" → num = 0 × 26 + 1 = 1（第 2 个）；"ZZ" → num = 25 × 26 + 25 = 675（最后一个）。
   • 第三步：最终答案 = res + num + 1。+1 是因为题目从 1 开始编号，而 num 是从 0 开始的排名。

3. 边界与细节：

   • 当 $|S| = 1$ 时，第一个循环 i=1 到 0 不执行，res = 0，正确。
   • 使用 long long（64 位有符号整数），最大值约 $9 \times 10^{18}$，足以容纳 $10^{16}$ 的答案，不会溢出。
   • 注意 add *= 26 在循环中可能达到 $26^{12} \approx 9.5 \times 10^{16}$，仍在 long long 范围内。
   • 不要忘记最后的 +1，否则会得到 0-based 的结果。

⏱️ 复杂度分析

• 时间复杂度：$O(n)$，其中 $n = |S| \leq 12$，两次遍历字符串。
• 空间复杂度：$O(1)$，只使用了常数级别的额外变量。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    long long res = 0, add = 26, num = 0;
    // 第一步：累加所有长度小于 |S| 的字符串总数
    // 长度 1: 26, 长度 2: 26^2, ..., 长度 |S|-1: 26^{|S|-1}
    for(int i = 1; i <= (int)s.size() - 1; i++){
        res += add;
        add *= 26;
    }
    // 第二步：将 S 视为 26 进制数，计算其在同长度字符串中的排名（0-based）
    for(int i = 0; i < (int)s.size(); i++){
        num = num * 26 + (s[i] - 'A');  // A=0, B=1, ..., Z=25
    }
    // 第三步：res（短串总数）+ num（同长度排名）+ 1（转为 1-based）
    cout << res + num + 1 << "\n";
    return 0;
}