题解：CF1424M Ancient Language

一眼题。

首先把

n

页书排到一个 vector 里面。

考虑两个字符串的比较过程：

逐位比较字符。如果相等，那么继续比较，否则按照字典的顺序排。
如果一直比较到了其中一个字符串的结尾，那么短的字符串排在前面。

按照这样的方法，我们可以得出一些字符之间的大小关系。

考虑建图。假设字符

x

比

y

小，那么连一条

x\to y

的边。容易知道这肯定是一个 DAG。那么就可以用拓扑排序判断这个图是否为 DAG。

代码中需要注意的细节：

字符串的长度也要判断。
在字典中没有出现的字符不需要在结果中输出。
如果最后有字典中的字符在答案中没有出现，那么也是不可能的。

CPP

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define ls(p) ((p)<<1)
#define rs(p) ((p)<<1|1)
#define lowbit(x) ((x)&(-(x)))
#define abs(x) ((x)>0?(x):(-(x)))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define gc getchar
#define pc putchar
#define sz(v) ((int)(v.size()))
using namespace std;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
inline int read(){
	int x=0,f=1;
	char ch=gc();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=gc();}
	return x*f;
}
inline void print(int x){
	if (x<0) pc('-'),x*=-1;
	if (x<10) pc(x+'0');
    else print(x/10),pc(x%10+'0');
}
const int N=1005;
vector<string> v[N];
vector<int> p[27];
int deg[N];
bool f[N];
void sol(){
	int n,k;
	cin>>n>>k;
	for (int i=1;i<=n;i++){
		int x;
		cin>>x;
		x++;
		for (int j=1;j<=k;j++){
			string s;
			cin>>s;
			v[x].pb(s);
			for (int _=0;_<sz(s);_++) f[s[_]-'a']=1;
		}
	}
	vector<string> vv;
	for (int i=1;i<=n;i++) for (auto kk:v[i]) vv.pb(kk);
	for (int i=0;i+1<sz(vv);i++){
		string x=vv[i];
		string y=vv[i+1];
		bool ff=0;
		for (int j=0;j<min(sz(x),sz(y));j++){
			if (x[j]!=y[j]){
				p[x[j]-'a'].pb(y[j]-'a');
				deg[y[j]-'a']++;
				ff=1;
				break;
			}
		}
		if (!ff){
			if (sz(x)>sz(y)) return cout<<"IMPOSSIBLE",void();
		}
	}
	vector<int> Ans;
	queue<int> q;
	for (int i=0;i<26;i++){
		if (!f[i]) continue;
		if (!deg[i]) q.push(i);
	}
	int cnt=0;
	for (int i=0;i<26;i++) cnt+=f[i];
	while (!q.empty()){
		int u=q.front();
		q.pop();
		Ans.pb(u);
		for (int v:p[u]){
			if (!(--deg[v])) q.push(v);
		}
	}
	set<int> ss;
	for (int x:Ans){
		ss.insert(x);
	} 
	if (sz(ss)!=sz(Ans)||sz(Ans)!=cnt) return cout<<"IMPOSSIBLE",void();
	else for (int x:Ans) cout<<(char)(x+'a');
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1;
	while (t--) sol();
	return 0;
}

题解：CF1424M Ancient Language

文章操作

相关推荐

评论

题解：CF1424M Ancient Language