洛谷 P3065 分析（别看）

科技起源

2026-07-16 11:52:28

发布于：河北

4阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：答案和答案序列

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

背景：有 $k$ 个字符串
允许：将 $26$ 个英文字母顺序重排，对于每个字符串，按照重排后的英文字母表字典序排序。如果最终可以使当前这个字符串排在第一个，那么加入答案以及答案序列
禁止：
限制：

1.3 题目数据范围与猜测

$1 \le n \le 30000 \longrightarrow O(n)$

1.4 一句话概括题意

有一些字符串，对于每个字符串，可以将 $26$ 个英文字母顺序重排，按照重排后的英文字母表字典序排序。如果最终可以使当前这个字符串排在第一个，那么加入答案以及答案序列

2 题目破题推导

2.1 将字符串转化为图

建立节点
所有字符串的每种字符都要在图上有一个节点代表
建立边
由于字典序越小，在两个字符串某一部分前缀相同后，当前这一位字符一定在重排（也可能没有重排）后排在另一个字符串相同位置前
也就是例如字符串 $S_1=abce,S_2=abcd$ ，都有相同的前缀 $abc$ ，那么要想要重排字母表后使得 $S_1<S_2$ ，就要让 $e<d$
那么就可以建一条单向边 $e \rightarrow d$

2.2 判断是否矛盾

当这个图建完，如果发现有环，说明矛盾了
举个例子： $a \rightarrow b \rightarrow c \rightarrow d \rightarrow b$ 出现了环，说明矛盾了（因为要把 $b$ 排在 $c$ 前面，把 $c$ 排在 $d$ 前面，又要把 $d$ 排在 $b$ 前面）

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：找同字符串前缀下的不同节点+建图 $\longrightarrow$ $\huge{字典树}$
关键词：图上判环 $\longrightarrow$ $\huge{拓扑排序}$

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

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

const int N = 3e5 + 10, M = 26;
int trie[N][M];
int ed[N];
ll dp[N];
int idx;
int fa[N];
int node_ch[N];
string str[N];
int k;

int get(char c){
	return c - 'a';
}

void insert(string s){
	int now = 0;
	int len = s.size();
	for (int i = 0;i < len;i++){
		int ch = get(s[i]);
		if (trie[now][ch] == 0){
			trie[now][ch] = ++idx;
			fa[trie[now][ch]] = now;
            node_ch[idx] = ch;
		}
		now = trie[now][ch];
	}
	ed[now]++;
}

vector<int> getPath(string s){
    vector<int> path;
    int now = 0;
    path.push_back(now);
    for(char c : s){
        int ch = get(c);
        now = trie[now][ch];
        path.push_back(now);
    }
    return path;
}

vector<int> getBrother(int father, int curNode){
    vector<int> bro;
    for(int i = 0; i < M; i++){
        int child = trie[father][i];
        if(child != 0 && child != curNode)
            bro.push_back(child);
    }
    return bro;
}

vector<int> g[M];
int in[M];
bool vis[M];
bool topo_sort() {
    queue<int> q;
    for (int i = 0; i < M; i++) {
        if (vis[i] && in[i] == 0) {
            q.push(i);
        }
    }
    int cnt = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cnt++;
        for (int v : g[u]) {
            in[v]--;
            if (in[v] == 0) q.push(v);
        }
    }
    int total = 0;
    for (int i = 0; i < M; i++){
         if (vis[i]){
             total++;
         }
    }
    return cnt == total;
}

void reset() {
    for (int i = 0; i < M; i++) {
        g[i].clear();
        in[i] = 0;
        vis[i] = false;
    }
}
    
bool has_pre(string s){
	int now = 0;
	int len = s.size();
	for (int i = 0;i < len;i++){
		int ch = get(s[i]);
		now = trie[now][ch];
        if (ed[now] && i != len - 1){
            return true;
        }
	}
	return false;
}

signed main(){

    cin >> k;
    for (int i = 1;i <= k;i++){
        string temp;
        cin >> temp;
        insert(temp);
        str[i] = temp;
    }
    int ans = 0;
    vector<string> ans_v;
    for (int i = 1;i <= k;i++){
        string temp = str[i];
        if (has_pre(temp)){
            continue;
        }
        reset();
        vector<int> vv = getPath(temp);// 这里的v是有根节点的，但是根节点不能算，因此下标从1到v.size()
        for (int i = 1;i < vv.size();i++){
            int cur = vv[i];
            int father = fa[cur];
            int u = node_ch[cur];
            vector<int> ret = getBrother(father, cur);
            for (int brother : ret){
                int v = node_ch[brother];
                g[u].push_back(v);
                in[v]++;
                vis[u] = vis[v] = true;
            }
        }
        if (topo_sort()){
            ans++;
            ans_v.push_back(temp);
        }
    }
    cout << ans << endl;
    for (string temp : ans_v){
        cout << temp << endl;
    }
	
	return 0;
}