解题思路

给定整数集合 $D\subseteq\{1,\dots,25\}$（允许的“邻差”）与总和 $n$，在 1..26（a..z）中找三元组 $(w_1,w_2,w_3)$ 满足：

1. $w_1+w_2+w_3=n$
2. $|w_1-w_2|\in D$ 且 $|w_2-w_3|\in D$

并输出按字典序最小的字符串 $w_1w_2w_3$（1→a,…,26→z）。若不存在输出 NO。

核心思路（枚举 + 贪心/字典序）：

• 用布尔数组 allow[d] 记录 $|d|\in D$ 是否允许，O(1) 判定。
• 依次枚举 $w_1\in[1,26]$（由小到大），再枚举 $w_2\in[1,26]$（由小到大）。 若 allow[abs(w1-w2)] 成立，则由和约束唯一确定 $w_3=n-w_1-w_2$。检查 $1\le w_3\le 26$ 且 allow[abs(w2-w3)]。 第一个满足的三元组即为字典序最小结果（先按 $w_1$ 小，再按 $w_2$ 小，$w_3$ 被唯一确定）。
• 将数字映射到字母输出。

该做法等价于在 26 个点上按边条件寻找长度为 2 的路径，并用字典序顺序枚举前两点以保证最小性。

复杂度分析

• 外层两重枚举固定为 $26\times 26=676$ 次检查；每次 O(1)。
• 单测时间复杂度：$O(26^2)$；空间复杂度：$O(1)$（常数级布尔数组）。
• 在 $t\le 10^4$ 时，总操作量约 $6.76\times10^6$，可轻松通过。

代码实现

Python

# -*- coding: utf-8 -*-
# 功能函数：根据 n 和允许差集 D，返回字典序最小的三字母或 "NO"
def solve_one(n, Dset):
    allow = [False] * 27  # allow[d] 表示差值 d 是否允许（1..26）
    for d in Dset:
        if 1 <= d <= 26:
            allow[d] = True
    # 按字典序枚举 w1, w2
    for w1 in range(1, 27):
        for w2 in range(1, 27):
            if not allow[abs(w1 - w2)]:
                continue
            w3 = n - w1 - w2
            if 1 <= w3 <= 26 and allow[abs(w2 - w3)]:
                # 数字转字母并返回
                return chr(ord('a') + w1 - 1) + chr(ord('a') + w2 - 1) + chr(ord('a') + w3 - 1)
    return "NO"

def main():
    import sys
    data = sys.stdin.read().strip().split()
    it = iter(data)
    t = int(next(it))
    out_lines = []
    for _ in range(t):
        n = int(next(it)); k = int(next(it))
        D = [int(next(it)) for _ in range(k)]
        out_lines.append(solve_one(n, D))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// Main.java  ACM 风格
// 逻辑：枚举 w1,w2（升序），由和确定 w3，并检查两条边差值是否在集合 D 中
import java.io.*;
import java.util.*;

public class Main {
    // 功能函数：返回答案字符串或 "NO"
    static String solveOne(int n, boolean[] allow) {
        for (int w1 = 1; w1 <= 26; w1++) {
            for (int w2 = 1; w2 <= 26; w2++) {
                int d12 = Math.abs(w1 - w2);
                if (d12 < 1 || d12 > 26 || !allow[d12]) continue;
                int w3 = n - w1 - w2; // 唯一确定 w3
                if (w3 >= 1 && w3 <= 26) {
                    int d23 = Math.abs(w2 - w3);
                    if (d23 >= 1 && d23 <= 26 && allow[d23]) {
                        char c1 = (char)('a' + w1 - 1);
                        char c2 = (char)('a' + w2 - 1);
                        char c3 = (char)('a' + w3 - 1);
                        return "" + c1 + c2 + c3;
                    }
                }
            }
        }
        return "NO";
    }

    public static void main(String[] args) throws Exception {
        // 使用 BufferedReader + StringTokenizer 读取输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        for (int cas = 0; cas < t; cas++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            boolean[] allow = new boolean[27]; // 1..26
            for (int i = 0; i < k; i++) {
                int d = Integer.parseInt(st.nextToken());
                if (1 <= d && d <= 26) allow[d] = true;
            }
            sb.append(solveOne(n, allow)).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

// ACM 风格程序：字典序枚举 w1,w2，计算 w3 并校验邻差
#include <bits/stdc++.h>
using namespace std;

// 功能函数：求解一组数据
string solve_one(int n, const vector<int>& D) {
    vector<bool> allow(27, false); // allow[d] 表示差值 d 是否允许
    for (int d : D) if (1 <= d && d <= 26) allow[d] = true;

    for (int w1 = 1; w1 <= 26; ++w1) {
        for (int w2 = 1; w2 <= 26; ++w2) {
            int d12 = abs(w1 - w2);
            if (d12 < 1 || d12 > 26 || !allow[d12]) continue;
            int w3 = n - w1 - w2; // 由和唯一确定
            if (1 <= w3 && w3 <= 26) {
                int d23 = abs(w2 - w3);
                if (d23 >= 1 && d23 <= 26 && allow[d23]) {
                    string s;
                    s.push_back(char('a' + w1 - 1));
                    s.push_back(char('a' + w2 - 1));
                    s.push_back(char('a' + w3 - 1));
                    return s; // 第一个即为字典序最小
                }
            }
        }
    }
    return "NO";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; 
    if (!(cin >> t)) return 0;
    while (t--) {
        int n, k; 
        cin >> n >> k;
        vector<int> D(k);
        for (int i = 0; i < k; ++i) cin >> D[i];
        cout << solve_one(n, D) << "\n";
    }
    return 0;
}

题目内容

有一仅由 $3$ 个小写字母组成的单词，将字母按字母表位置编导为 $1$~$26(a=1,b=2,...,z=26)$，定义单词

$w_1w_2w_3$ 的“编码和”为 $w_1+w_2+w_3$ 。

现在给定一个整数，与个允许的邻差集合 $D=${$d_1,...,d_k$}。当且仅当同时满足：

• $w_1+w_2+w_3=n$ ;

• $丨w_1-w_2丨∈D 且 丨w_2-w_3丨∈D$ ;

我们称 $w_1w_2w_3$ 为"合法"的三字母单词。请在所有合法单词中，输出字典序最小的那个；若不存在合法单词，输出 $NO$ 。

【名词解释】

小写字母与编号的对应关系如下：

$a↔1,b↔2,...,z↔26$ 。

字符串的字典序比较：从左到右逐个比较两个字符串的字符。如果在某个位置上字符不同，比较这两个字符的 $ASCII$ 码顺序，$ASCII$ 码小的字符串字典序也小。如果一直比较到其中一个字符串结束，则较短的字符串字典序更小。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $t(1≤t≤10^4)$ ，代表数据组数，每组测试数据描述如下：

• 第一行输入两个整数 $n,k(3≤n≤78;1≤k≤25)$ ；

• 第二行输入 $k$ 个两两不同的整数 $d_1,d_2,...,d_k(1≤d_i≤25)$ ，表示集合 $D=${$d_1,...,d_k$}。

输出描述

对于每一组测试数据，新起一行输出：

• 若存在合法单词，输出由 $3$ 个小写字母组成的字符串(例如"$abc$")；

• 否则输出 $NO$ 。

样例1

输入

2
6 1
1
4 1
2

输出

abc
NO

说明

• 第 $1$ 组：$n=6,D=${$1$}。取 $w_1=1,w_2=2,w_3=3$ ,有 $w_1+w_2+w_3 =6$ 且 $∣1-2∣=1∈D,∣2-3∣=1∈D$，对应 "$abc$"，且为字典序最小；

• 第 $2$ 组：$n=4,D=${$2$}。不存在合法三元组，输出 $NO$ 。