问个问题:(玄2关)
  • 板块P1127 词链
  • 楼主XP3301_Pipi
  • 当前回复2
  • 已保存回复3
  • 发布时间2024/3/2 10:43
  • 上次更新2024/3/2 13:58:08
查看原帖
问个问题:(玄2关)
1066579
XP3301_Pipi楼主2024/3/2 10:43

我把所有的字符串按照首尾字符作为下标存储起来,然后再分别对每个下标排序
评测结果中显示输出的链字典序不是最小的
这是什么原因
有没有大犇可以解答,或者hack一下
悬2关
只要对代码有帮助都会关注

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
const int N=2e5+15;
const long long INF=0x3f3f3f3f3f3f3f3fll;

inline void FileIO(){
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}

template<typename Type>
inline void read(Type& res){
	int f=1,x=0; char c=' '; while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
	res=x*f;
}

int n,head[35],in[35],out[35],h[705],fa[35],num;
vector<string> mp[705];
vector<int> edge[35];
vector<int> path;

int Letterval(char x,char y){
	return (x-1)*26+y;
}

void dfs(int x){
	for(int i=head[x];i<(signed)edge[x].size();i=head[x]){
		head[x]=i+1;
		dfs(edge[x][i]);
		num++;
		path.push_back(Letterval(x,edge[x][i]));
	}
}

int Find(int x){
	if(fa[x]==x) return x;
	return Find(fa[x]);
}

signed main(){
	//不开longlong见祖宗!全开longlong见祖宗!
	//检查数组大小!
	//注意输出格式!
	read(n);
	int minn=114514;
	for(int i=1;i<=26;i++) fa[i]=i;
	for(int i=1;i<=n;i++){
		string str;
		cin>>str;
		int u=str[0]-'a'+1,v=str[str.length()-1]-'a'+1;
		edge[u].push_back(v);
		out[u]++,in[v]++;
		mp[Letterval(u,v)].push_back(str);
		minn=min(minn,min(u,v));
	}
	bool flag=1;
	int cs=0,ct=0,s=-1;
	for(int i=1;i<=26;i++){
		if(in[i]==out[i]) continue;
		flag=0;
		if(in[i]+1==out[i]&&s==-1) cs++,s=i;
		else if(out[i]+1==in[i]) ct++;
		else{
			puts("***");
			return 0;
		}
	}
	if(!flag&&(ct>1||cs>1)) return puts("***"),0;
	if(flag) s=minn;
	for(int i=1;i<=700;i++) sort(mp[i].begin(),mp[i].end());
	dfs(s);
	if(num<n) return puts("***"),0;
	for(int i=path.size()-1;~i;i--){
		if(i!=path.size()-1) printf(".");
		cout<<mp[path[i]][h[path[i]]];
		h[path[i]]++;
	}
	return 0;
}








2024/3/2 10:43
加载中...