洛谷 P6286 分析（别看）

科技起源的小号1

2026-09-08 20:34:26

发布于：天津

2阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个合法方案

1.2 题目背景、允许、禁止与限制

背景：
现在有 $n$ 个单词
允许：
重排字母表，排完之后将每个单词的 $a$ 替换为当前字母表中的第一个单词，将每个单词的 $b$ 替换为当前字母表中的第二个单词，以此类推...
给出 $n$ 个不重复的数字 $a_i$ ，第 $i$ 个表示希望单词 $i$ 按照重排字母表后“字典序”排序能够被排到第 $a_i$ 个
求存不存在一种重排字母表的方案使得将所有单词替换完毕后能够按给定要求排序成功

1.3 题目数据范围与猜测

$1 \le n \le 100, 每个字符串长度 \le 100\longrightarrow O(n^2 \times |s|)$

1.4 一句话概括题意

现在有一些字符串
求一种字母表排列方案使得按该字母表对应的字典序排序后它们都能被排到期望位置上

2 题目破题推导

2.1 第一步：建模

因为题目要求字母表重排后单词按照 $a_1,a_2,\cdots,a_n$ 的顺序排列
那么就会得到一些约束条件：
考虑字典序的比较方式：找到第一位不同的字母并按照字母表的顺序排列
那么就代表 $s[a_1]$ 与 $s[a_2]$ 的第一位不同字符在字母表中的顺序应该是 $s[a_1]$ 的那一位在先
现在就可以把字母当做图上的节点，将 $<$ 的关系当做图上的边，也就是建一条 $s[a_1]对应位置字符 \rightarrow s[a_2]对应位置字符$ 的有向边

2.2 第二步：分情况讨论

经过建模，这道问题已经变成了“能否给 $26$ 个英文字母排序，使得图中所有 $u\rightarrow v$ 的边都在字母表中体现为 $u$ 排在 $v$ 前面？”

那么如果发现这张图上有环，说明出现 $u\rightarrow v \rightarrow w \rightarrow u$ （或者更长），也就是 $u < v,v < w但w < u$
这样根本没法排
那么如果没环呢
说明存在这样的一个顺序
这个字母表的顺序中，不受影响的字母不变
其他的字母有一个映射的关系：
我们按拓扑序排序字母后得到序列ans $ans_1,ans_2,\cdots,ans_n$
将拓扑排序后的字母再进行一次正常排序（也就是没有改动之前的顺序），得到数组anssort
那么替换最终答案（用 answer 表示）： $answer[ans_i] = anssort_i$

2.3 第三步：边界意识

考虑所有会导致合理字母表不存在的地方：

当两个单词 $a$ 和 $b$ 出现 $|a| < |b| 且 a是b的前缀，且a对应a数组要求位置a_i>b对应a数组要求位置a_j$ ，那么这种情况是不存在的，因为 $|a| < |b| 同时a是b的前缀$ ，所以 $a$ 无论怎么样都一定排在 $b$ 前面（因为字典序是全部相同比长度）
当图上出现环（拓扑序遍历失败），则也不可能出现，就像刚刚2.2部分说的那样
当一个字符 $a$ 需要变换位置（也就是被图包含），但是拓扑序没有遍历到，说明拓扑序中出现了问题，也不可能有正确方案

其他都可能出现正确方案

3 模型匹配

拓扑排序查看合法性

4 最终代码（禁止抄袭，仅用于参考）

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

int n;
const int N = 111, M = 30;
int anssort[N], ans[N], answer[N];
bool vis[N];
string s[N];
int a[N];
vector<int> g[M];
int in[N];
bool vist[N];
int topo(){
    int ret = 0;
    queue<int> q;
    for (int i = 0;i <= 25;i++){
        if (in[i] == 0 && vis[i] == true){
            q.push(i);
        }
    }
    if (q.size() == 0){
        return -1;
    }
    while(!q.empty()){
        int f = q.front();
        q.pop();
        if (vist[f]){
            return -1;
        }
        vist[f] = true;
        anssort[++ret] = f;
        ans[ret] = f;
        for (int v : g[f]){
            if (--in[v] == 0){
                q.push(v);
            }
        }
    }
    return ret;
}
int different = 0;
void add(int u, int v){
    g[u].push_back(v);
    in[v]++;
    if (!vis[u]){
        vis[u] = true;
        different++;
    }
    if (!vis[v]){
        vis[v] = true;
        different++;
    }
}

int main(){

    cin >> n;
    for (int i = 1;i <= n;i++){
        cin >> s[i];
    }
    for (int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for (int i = 2;i <= n;i++){
        int idx1 = 0, idx2 = 0;
        while(idx1 < s[a[i - 1]].size() && idx2 < s[a[i]].size()){
            if (s[a[i - 1]][idx1] != s[a[i]][idx2]){
                add(s[a[i - 1]][idx1] - 'a', s[a[i]][idx2] - 'a');
                break;// 只需要第一位不同的前面比后面大即可
            }
            idx1++, idx2++;
        }
        if (different == 0 && s[a[i - 1]].size() > s[a[i]].size()){
            cout << "NE";
            return 0;
        }
    }
    if (different == 0){
        cout << "DA\n";
        for (int i = 0;i <= 25;i++){
            cout << char(i + 'a');
        }
        return 0;
    }
    int t = topo();
    if (t == -1){
        cout << "NE";
        return 0;
    }
    sort(anssort + 1, anssort + 1 + t);
    for (int i = 1;i <= t;i++){
        answer[ans[i]] = anssort[i];
    }
    for (int i = 0;i <= 25;i++){
        if (vis[i] && !vist[i]){
            cout << "NE";
            return 0;
        }
        if (!vist[i]){
            answer[i] = i;
        }
    }
    cout << "DA\n";
    for (int i = 0;i <= 25;i++){
        cout << char(answer[i] + 'a');
    }
    
    return 0;
}