玄学啊!绝对玄学啊!
  • 板块P1127 词链
  • 楼主卷王慢即快
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/6/27 14:45
  • 上次更新2023/10/28 20:49:12
查看原帖
玄学啊!绝对玄学啊!
494699
卷王慢即快楼主2022/6/27 14:45

我一开始的代码:

#include<bits/stdc++.h>
using namespace std; map<char,int>s1,s2;
#define maxn 100001
string ans[maxn],t[maxn],a[maxn]; bool f=0,vis[maxn];
int len[maxn],cnt=0,n,st=1,end; char t1,t2;
inline void dfs(int l,int step) {
	if(f==1) return;
	if(step==n) { f=1;
		for(int i=1;i<=cnt;i++) ans[i]=t[i]; //赋值给ans[] 
		return ; }
	for(int i=1;i<=n;i++) {
		if(vis[i]) continue; //特判,别忘了 
		if(a[l][len[l]-1]==a[i][0]) {
			vis[i]=1; t[++cnt]=a[i]; //将t数组赋值 
			dfs(i,step+1); cnt--; vis[i]=0; //递归 
		} }
} int main() { cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i]; len[i]=a[i].size();
		s1[a[i][0]]++; s2[a[i][len[i]-1]]++; //记录每个字符串的字母 
	} sort(a+1,a+n+1); //字符串排序 
	for(char ch='a';ch<='z';ch++)
		if(s1[ch]==s2[ch]+1) t1=ch;
		else if(s1[ch]==s2[ch]-1) t2=ch;
	for(int i=1;i<=n;i++)
	if(a[i][0]==t1 && (s2[t2]!=1||a[i][len[i]-1]!=t2))
		{st=i; break;}
	vis[st]=1; t[++cnt]=a[st];
	dfs(st,1); if(f==0) {cout<<"***"<<endl; return 0;} //不符合要求 
	for(int i=1;i<n;i++) cout<<ans[i]<<".";
	cout<<ans[n];
	return 0; }

我把代码改了一点点:

#include<bits/stdc++.h>
using namespace std; map<char,int>s1,s2;
#define maxn 100001
string ans[maxn],t[maxn],a[maxn]; bool f=0,vis[maxn];
int len[maxn],cnt=0,n,st=1,end; char t1,t2;
inline void dfs(int l,int step) {
	if(f==1) return;
	if(step==n) { f=1;
		for(int i=1;i<=cnt;i++) ans[i]=t[i]; //赋值给ans[] 
		return ; }
	for(int i=1;i<=n;i++) {
		if(vis[i]) continue; //特判,别忘了 
		if(a[l][a[l].length()-1]==a[i][0]) { //改在这里
			vis[i]=1; t[++cnt]=a[i]; //将t数组赋值 
			dfs(i,step+1); cnt--; vis[i]=0; //递归 
		} }
} int main() { cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i]; len[i]=a[i].size();
		s1[a[i][0]]++; s2[a[i][len[i]-1]]++; //记录每个字符串的字母 
	} sort(a+1,a+n+1); //字符串排序 
	for(char ch='a';ch<='z';ch++)
		if(s1[ch]==s2[ch]+1) t1=ch;
		else if(s1[ch]==s2[ch]-1) t2=ch;
	for(int i=1;i<=n;i++)
	if(a[i][0]==t1 && (s2[t2]!=1||a[i][len[i]-1]!=t2))
		{st=i; break;}
	vis[st]=1; t[++cnt]=a[st];
	dfs(st,1); if(f==0) {cout<<"***"<<endl; return 0;} //不符合要求 
	for(int i=1;i<n;i++) cout<<ans[i]<<".";
	cout<<ans[n];
	return 0; }

第一个:5555分, 当我改了后本来不抱有希望了,结果……无语啊!) 想问一下为什么?

跪求大佬解答!

2022/6/27 14:45
加载中...