【DG 特长生2019】模拟赛赛后总结（2024.1.24）

打了330pt,订正后350pt

T1 签到

T2 dfs+剪枝（虽然我写挂了）?

T3 NOIP原题

T4 floyd

主要是想分享一下T4。

写了一种基于floyd的做法。

感觉好像和大部分人的写法不太一样。

因为看到大小关系，我就想到了传递性。

floyd是可以维护传递性的。

至此，此题的一种写法诞生了。

因为比较板子，所以比拓扑排序的要好写一点。

#include<bits/stdc++.h>
using namespace std;
int n,k;
string a[500005];
int f[30][30];//表示i是否小于j
bool vis[31];
bool know[31];
void add(string a,string b){
	int la = a.size(),lb = b.size();
	for(int i = 0;i < la;i++)vis[a[i]-'a'+1] = 1;
	for(int i = 0;i < lb;i++)vis[b[i]-'a'+1] = 1;
	for(int i = 0;i < la&&i < lb;i++){
		int aa = a[i]-'a'+1,bb = b[i]-'a'+1;
		if(aa != bb){
		//	cout<<a[i]<<" "<<b[i]<<" "<<aa<<" "<<bb<<endl;
		    f[aa][bb] = 1;
			break;
		}
	}
}
void floyd(){
	for(int k = 1;k <= 26;k++){
		for(int i = 1;i <= 26;i++){
			for(int j = 1;j <= 26;j++){
				if(f[i][k] == 1&&f[k][j] == 1){
					f[i][j] = 1;
				}
				
			}
		}
	}
}
string p;
char pr[31]; 
int tot;
int kth[31];
int main(){
	freopen("resume.in", "r", stdin);
	freopen("resume.out", "w", stdout);
	//ios::sync_with_stdio(0); 
    cin>>n>>k;
    for(int i = 1;i <= 26;i++){
    	for(int j = 1;j <= 26;j++){
    	    f[i][j] = -1;
	    }
	    
	}
    for(int i = 1;i <= k;i++){
    	cin>>a[i];
    	if(i > 1){
    		add(a[i-1],a[i]);
		}
	}
	cin>>p;
    floyd();
    //cout<<f[1][5]<<endl;
    for(int i = 1;i <= 26;i++){
    	if(vis[i]){
    		pr[++tot] = char(i+'a'-1);
		}
	}
    for(int i = 1;i <= 26;i++){
    	if(vis[i]){
    //	cout<<(char)('a'+i-1)<<":";
    	int res = 0;
    	for(int j = 1;j <= 26;j++){
    	    if(f[i][j] == 1){
    	    //	cout<<(char)('a'+j-1)<<" ";
    	    	res++;
			}
	    }
	    if(know[n-res]!=0){
	    	cout<<0;
	    	return 0;
		}
		know[n-res] = 1;
	    kth[i+'a'-1] = n-res;
	    //cout<<n-res<<endl;
	}
	}
	for(int i = 0;i < p.size();i++){
		if(kth[p[i]] == 0){
			cout<<0;
			return 0;
		}
	}
	for(int i = 0;i < p.size();i++){
	    cout<<pr[kth[p[i]]];
	}
	return 0;
}