讨论详情 - XMJY

题解
1220：单词接龙
yangyu LV 6 @ 2026-4-18 9:14:23

/*********************************************************************
    $PROGRAM$: 
    $DATETIME$: 2026/3/21 13:55:42
    $DESCRIPTION$: 
*********************************************************************/
#include <bits/stdc++.h>
using namespace std;

int n;
string a[24];
int v[24];
int ans=0;

int canjie(string x,string y){
	int lenx=x.length();
	int leny=y.length();
	int len=min(lenx,leny);
	bool flag;
	for(int i=1;i<len;i++){
		flag=1;
		for(int j=0;j<i;j++){
			if(x[lenx-i+j]!=y[j]){
				flag=0;
				break;
			}
		}
		if(!flag)continue;
		return leny-i;
	}
	return 0;
}

void dfs(string now,int len){
	if(len>ans)ans=len;
	int t;
	for(int i=1;i<=n;i++){
		if(v[i]>1)continue;
		t=canjie(now,a[i]);
		if(!t)continue;
		v[i]++;
		dfs(a[i],len+t);
		v[i]--;
	}
}

int main() {
    //
//    string x,y;
//    for(;;){
//    	cin>>x>>y;
//    	cout<<canjie(x,y)<<endl;
//	}
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	char ch;
	cin>>ch;
	for(int i=1;i<=n;i++){
		if(a[i][0]==ch){
			v[i]=1;
			dfs(a[i],a[i].length());
			v[i]=0;
		}
	}
	cout<<ans;
	return 0;
}

cjzm LV 1 SU @ 2026-4-18 10:19:06

/*********************************************************************
    $PROGRAM$:1220：单词接龙
    $DATETIME$: 2026/3/21 13:55:42
    $DESCRIPTION$:
*********************************************************************/
#include <bits/stdc++.h>
using namespace std;

int n;
string word[24], ss, s1;
int v[24];
int ans = 0;

int check(string x, string y) {
	int lenx = x.size();
	int leny = y.size();
	for (int i = 1; i < min(lenx, leny); i++) { // 不能完全重叠
		string a = x.substr(lenx - i); // 从后面截取长度为i的片段
		string b = y.substr(0, i); //从前面截取长度为i的片段
		// i
		if (a == b) {
			return i;
		}
	}
	return 0;
}

void dfs(string now) {
	int len = now.size();
	if (len > ans) {
		ans = len;
		ss = now;
	}
	for (int i = 1; i <= n; i++) {
		int k = check( now, word[i]);
		if (v[i] <= 1 && k != 0) {
			v[i]++;
			dfs(now + word[i].substr(k));
			v[i]--; //
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> word[i];
	char ch;
	cin >> ch;
	s1 = "#";
	s1 += ch;
	dfs(s1); //"a"
	cout << ans - 1;
	return 0;
}

1220：单词接龙

1 条评论

登录