求助2
  • 板块灌水区
  • 楼主lyc20110701
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/7/26 09:44
  • 上次更新2024/7/26 10:52:18
查看原帖
求助2
1126841
lyc20110701楼主2024/7/26 09:44

各路大神,再帮我看看下面两个代码吧,呜呜呜,实在没找出有什么不同

A

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n;

string w[50]; // 每个单词可以使用两次,本题解认为这两个单词完全不一样 

bool v[50];

int overlap[50][50];

char begin; // 起始字符 

int ma=-0x3f3f3f3f;
// 如何判断当前龙不能再接了? 

// 当然已经接好的龙为dragon,最后一个接上的单词的序号为i 
void dfs(string dragon, int i){
	
//	cout<<dragon<<endl;
	
	bool flag=false; 
	for(int j=1;j<=2*n;j++){
		if(!v[j]){
			int len=overlap[i][j];
			if(len!=0){
				flag=true; // 当前确实可以接龙 
				v[j]=true; // 尝试接龙编号为j的单词
				dfs(dragon+w[j].substr(len),j);
				
//				cout<<dragon<<"====="<<w[j].substr(len)<<endl;
//				cout<<w[i]<<' '<<len<<' '<<w[j]<<endl;
//				cout<<endl;
				
				v[j]=false; // 恢复现场 
			}
		}
	}
	if(!flag){ // 当前没法再接龙了,就可以尝试更新最大值了 
		ma=max(ma,(int)dragon.size()); // 千万记得要强制转换数据类型! 
	}
}

int main(){
	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	for(int i=n+1;i<=2*n;i++){
		w[i]=w[i-n];
	}
	cin>>begin;
	
	// 预处理出重叠部分的最小长度数组
	for(int i=1;i<=n*2;i++){
		for(int j=1;j<=n*2;j++){
			for(int k=1;k<=min(w[i].size(),w[j].size())-1;k++){
				if(w[i].substr(w[i].size()-k)==w[j].substr(0,k)){
					overlap[i][j]=k;
					break;
				}
			}
		}
	}
	
	for(int i=1;i<=n;i++){
		if(w[i][0]==begin){
			v[i]=true;
			dfs(w[i],i);
			v[i]=false;
		}
	} 
	cout<<ma<<endl;

	return 0;
}

B

#include<bits/stdc++.h>
using namespace std;
int n;
string w[50];
char begin;
int overlap[50][50];
bool v[50];
int ma=-0x3f3f3f3f;

void dfs(string tou,int i){
	bool tf=false;
	for(int j=1;j<=n*2;j++){
		if(!v[j]){
			int len=overlap[i][j];
			if(len!=0){
				v[j]=true;
				tf=true;
				dfs(tou+w[j].substr(len),j);
				v[j]=false;
			}
		}		
	}
	if(!tf){
		ma=max(ma,(int)tou.size());
	}
}



int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=n+1;i<=n*2;i++) w[i]=w[i-n];
	cin>>begin;
	for(int i=1;i<=n*2;i++){
		for(int j=1;j<=n*2;j++){
			for(int k=1;k<min(w[i].size(),w[j].size());k++){
				if(w[i].substr(w[i].size()-k)==w[j].substr(0,k))
				overlap[i][j]=k;
				break;
			}
		}
	}	
	for(int i=1;i<=n;i++){
		if(w[i][0]==begin){
			v[i]=true;
			dfs(w[i],i);
			v[i]=false;
		}
	}
	cout<<ma;
	
	return 0;
}
2024/7/26 09:44
加载中...