求助
  • 板块P1127 词链
  • 楼主UncleEric
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/17 17:22
  • 上次更新2024/3/17 17:31:38
查看原帖
求助
1163457
UncleEric楼主2024/3/17 17:22

初学者只会用STL


以下代码,使用Dev-C++可以通过样例以及评论区里给出的数据,但提交到洛谷全RE,本题也没有给出让我尝试的官方数据,所以我想问一下这段代码中有什么导致洛谷出现RE。(洛谷在线IDE运行样例时显示:超出内存限制)


#include<bits/stdc++.h>
using namespace std;

int n,used[1005],sum[1005];
vector<vector<int> > data;//二维数组

bool cmp(vector<int> a,vector<int> b){
	for(int i=0;i<min(a.size(),b.size());i++){
		if(a[i]==b[i]) continue;
		return a[i]<b[i];
	}
	return a.size()<b.size();
}

void dfs(int x,int now){
	if(x>n){//如main函数,走出第一条通路可以直接作为结果进行输出,下为在Dev-C++检测过正确性的输出模块
		for(int i=0;i<n;i++){
			for(int l=0;l<data[sum[i]].size();l++){
				cout<<(char)data[sum[i]][l];
			}
			if(i!=n-1)cout<<'.';
		}
		exit(0);
	}
	for(int i=1;i<data.size();i++){//dfs过程,由于已经进行升序排列,只需找到符合尾接头的序号较小的一项
		if(used[i]||(i==now)){
			continue;
		}
		if(data[now][data[now].size()-1]==data[i][0]){
			used[i]=1;//used存储经过的单词,sum存储输出单词的顺序(从0开始)
			sum[x-1]=i;
			dfs(x+1,i);
			used[i]=0;
			sum[x-1]=0;
		}
	}
}

int main(){
	cin>>n;
	char c;
	scanf("%c",&c);//为了输入第一个回车
	for(int i=0;i<n;i++){		
		vector<int> word;//记录当前单词,并最终记录到总的二维数组
		scanf("%c",&c);
		while((int)c>96&&(int)c<123){
			word.push_back((int)c);
			scanf("%c",&c);
		}
		data.push_back(word);
	}
	sort(data.begin(),data.end(),cmp);//对其升序排列后,使得dfs效率变高,走通的第一条路径就是需要的结果
	used[0]=1;
	sum[0]=0;
	dfs(2,0);
	cout<<"***";
	return 0;
}
2024/3/17 17:22
加载中...