CF510C Fox And Names 题解

huangqixuan / 2024-02-29 / 原文

CF510C Fox And Names 题解

https://www.luogu.com.cn/problem/CF510C

思路

题意就是：确定一个小写字母的比较规则，使得给定的所有字符串在一开始就是按你确定的比较规则排序了的。
可以发现：对于前后一对字符串，找到第一对不同的字符，是要这两个字符有合法的大小关系，就能满足题意。
由于很显然：一个字母有多个字母在要比它小或者大。
所以：建图 —> 拓扑排序 —> 模拟。

如何判断 Impossible

分一下几种情况：

$s_i$	$s_{i + 1}$
hh	hh
hh	hhb
hhb	hh

第一种情况题目的输入已经帮我们解决了：所有字符串两两不同。
剩下的分类特判即可。

Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
  
using namespace std;

const int MAXN = 100 + 10;

int n;
int ans[MAXN], len_ans = 0;
int b[MAXN], top = 0;
int cen[MAXN], pre[50];
int s[MAXN][MAXN];
string SSS;
vector<int> c[50];

int main(){
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> SSS;
    for(int j = 0; j < SSS.size(); j++){
      s[i][j] = int(SSS[j] - 'a' + 1);
    }
  }
  for(int i = 1; i < n; i++){
    for(int j = 0; j < 100; j++){
      if(s[i][j] == 0 || s[i + 1][j] == 0){
        if(s[i][j] != 0 && s[i + 1][j] == 0){
          cout << "Impossible";
          return 0;
        }
        break;
      }
      if(s[i][j] != s[i + 1][j]){
        c[s[i][j]].push_back(s[i + 1][j]);
        pre[s[i + 1][j]]++;
        break;
      }
    }
  }
  for(int i = 1; i <= 26; i++){
    if(pre[i] == 0){
      b[++top] = i;
    }
  }
  while(top > 0){
    int i = b[top];
    top--;
    for(int j : c[i]){
      if(pre[j] > 0){
        pre[j]--;
        if(pre[j] == 0){
          b[++top] = j;
        }
      }
    }
    ans[++len_ans] = i;
  }
  if(len_ans != 26){
    cout << "Impossible";
    return 0;
  }
  for(int i = 1; i <= len_ans; i++){
    cout << char(ans[i] + 'a' - 1);
  }
  return 0;
}