题目详细题解

问题重述

给定一个整数 $n$（$3 \leq n \leq 78$），表示三个小写字母在字母表中位置编号（'a' = $1$，'z' = $26$）之和。
要求输出字典序最小的由三个字母组成的单词，使得其字母位置之和等于 $n$。

解题思路

方法一：直接枚举（标程使用的方法）

由于只有三个字母，每个字母有 $26$ 种可能，总组合数为：

对于每组测试数据，枚举所有组合是可行的（$t \leq 100$，总计算量约 $1.7 \times 10^6$ 次，完全在时间限制内）。

具体步骤：

1. 用三重循环枚举第一个字母 $i$、第二个字母 $j$、第三个字母 $k$，取值范围均为 $0$ 到 $25$（$0$ 对应 'a'，$25$ 对应 'z'）。
2. 检查是否满足：$$(i + 1) + (j + 1) + (k + 1) = n$$ 即：$$i + j + k + 3 = n$$
3. 如果满足，将对应的三个字符拼接成字符串 cur。
4. 维护一个字典序最小的字符串 mins，初始设为 "zzz"。
5. 每次用 min(cur, mins) 更新 mins。
6. 输出 mins。

代码逐行解释

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

void solve(){
    int n, sz = 26;        // sz 表示字母表大小
    cin >> n;
    string mins = "zzz", cur;   // 初始最小值设为最大可能字符串
    for(int i = 0; i < sz; i++){          // 枚举第一个字母
        for(int j = 0; j < sz; j++){      // 枚举第二个字母
            for(int k = 0; k < sz; k++){  // 枚举第三个字母
                if(i + j + k + 3 == n){   // 判断总和是否等于 n
                    cur += char(i + 'a'); // 将数字转换为字符
                    cur += char(j + 'a');
                    cur += char(k + 'a');
                    mins = min(cur, mins); // 更新字典序最小
                }
            }
        }
    }
    cout << mins << "\n";
}

int main(){
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
}

示例验证

以输入 n = 24 为例：

• 字母 'a' 对应 $1$，'b' 对应 $2$，……，'z' 对应 $26$。
• 我们需要 $i + j + k + 3 = 24$，即 $i + j + k = 21$。
• 字典序最小 → 第一个字母尽可能小 → 第一个字母取 'a'（$i = 0$），则 $j + k = 21$。
• 第二个字母尽可能小 → 取 'a'（$j = 0$），则 $k = 21$，对应 'v'（因为 'a' 对应 $0$，'v' 对应 $21$）。
• 得到 "aav"，与输出一致。

方法二：贪心构造（更优解法）

不需要枚举所有组合，可以直接贪心构造：

1. 初始设三个字母均为 'a'，总和为 $3$。
2. 从第三个字母（最右边）开始，尽可能将其增大到 'z'，同时从 $n$ 中减去增加的数值。
3. 若第三个字母已达 'z' 仍有剩余，则调整第二个字母，依此类推。

贪心正确性：
为了得到字典序最小，应该让左边的字母尽可能小，因此优先把“增量”分配到右边的字母上。

贪心代码示例

void solve_greedy() {
    int n;
    cin >> n;
    string s = "aaa";           // 初始全为 'a'
    n -= 3;                     // 减去基础的 3
    for (int i = 2; i >= 0; i--) {  // 从最后一个字母往前调整
        int add = min(n, 25);   // 最多增加到 'z'（增加 25）
        s[i] += add;
        n -= add;
    }
    cout << s << "\n";
}

复杂度分析

• 方法一（枚举）：时间复杂度 $O(26^3 \cdot t) = O(17576 \cdot t)$，$t \leq 100$，约 $1.7 \times 10^6$ 次操作，空间复杂度 $O(1)$。
• 方法二（贪心）：时间复杂度 $O(t)$，空间复杂度 $O(1)$，更优。

总结

本题是 Codeforces 入门级题目（难度约 800 分），核心在于：

• 理解字典序的定义；
• 掌握暴力枚举或贪心构造的方法；
• 注意字母编号从 $1$ 开始，但数组索引从 $0$ 开始的转换关系。

对于初学者，标程的枚举方法直观易懂，是学习多重循环和字符串比较的好例子。