专栏文章

题解五：P1019 [NOIP 2000 提高组] 单词接龙

lliu鲤鱼
P1019题解参与者 11已保存评论 15

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
15 条
当前快照
1 份
快照标识符
@miq6ss9f
此快照首次捕获于
2025/12/03 23:53
3 个月前
此快照最后确认于
2025/12/03 23:53
3 个月前
查看原文
题目传送门：P1019 [NOIP 2000 提高组] 单词接龙。
2025.8.11 第一次修改：调整部分排版；更改、增加一些内容；修改两处笔误。

题意

给出 nn，给出 nn 个单词，给出一个字符 charchar，将单词连接成一个长度为 lenlen 且以字符 charchar 开头的字符串，使得 lenlen 尽可能大，输出 lenlen。
连接时要注意：
  • 每个单词最多使用两次；
  • 第一个单词要以 charchar 开头；
  • 后一个单词的开头部分应与前一个单词的结尾部分相同（也就是题目中所说的“重合部分”）；
  • 应保证重合部分的长度最多必须小于这两个单词的长度。或者说，两个单词不能互相包含（否则连接没有意义）；
  • 连接后，重合的部分会被覆盖。

思路

搜索。
我们依次枚举所有可能的排列情况，每一次都更新最大长度 lenlen，最后输出。
首先，我们需要一个函数，得到已有的总字符串和新加入的单词的重合部分长度大小（有几位是重合的）。如果这个长度为 00，说明这个单词不能被添加（没有重合部分）。显然，为了使总长度尽可能长，这个连接部分要尽可能小，所以我们从小开始枚举。
CPP
ll check(string s1,string s2){
	ll num=min(s1.size(),s2.size());
	for(ll i=1;i<num;i++){//枚举可能的长度
		bool f=true;//用来判断
		for(ll j=0;j<i;j++)//对比每一位
			if(s1[s1.size()-i+j]!=s2[j]){
				f=false;//如果不相同则判断为否
				break;
			}
		if(f==true) return i;//如果判断为正，返回重合部分的长度
	}return 0;//否则说明不能被添加
}
关于高亮行
注意这一行的判断：
CPP
if(s1[s1.size()-i+j]!=s2[j])
这里 s1.size() 是字符串的长度，s1.size()-i 是字符串倒数第 ii 位，也对应新单词的第 00 位，所以字符串的第 s1.size()-i+j 位就对应单词的第 jj 位。我们判断字符串的后 ii 位和单词的前 ii 位是否不同，就要依次判断字符串的倒数第 ii 位至最后一位与单词的第一位至第 ii 位是否不同。即对于 ∀j∈{1,2,…,i}\forall j \in \{1,2,\dots ,i \}，执行上面的语句判断。
对于搜索部分，我们依次枚举单词，判断是否能在总字符串后面添加。如果不行，则直接进行下一次循环；否则添加新单词，递归，回溯，再进行下一次循环。当然，如果这个单词已经使用过两次，也直接进行下一次循环。
CPP
void dfs(string st,ll num){//num 是当前总字符串的长度
	len=max(num,len);//更新最大长度
	for(ll i=0;i<n;i++){//枚举单词
		if(a[i]>=2) continue;//判断这个单词使用次数
		ll m=check(st,str[i]);//记录重合部分长度
		if(m>0){//如果重合长度大于 0，也就是说可以被添加
			a[i]++;//增加单词使用次数
			dfs(str[i],num+str[i].size()-m);//递归
			a[i]--;//回溯
		}//否则代表没有重合，不操作
	}return;
}
关于 stst
要强调的是，stst 是最近添加的单词，而不是总的字符串。我们前面使用函数计算重合部分长度时，应保证该长度小于前后两个单词的长度。而如果使用总字符串，无法确定上一个单词从哪里开始。（当然，你要是不嫌麻烦也可以再开一个变量存储上一个单词的长度。）

代码实现

刚才思路部分已经给出了主要代码，此处只做必要标记。
CPP
// 24ms / 1.04MB / 678B C++98 O2
// 24ms / 816.00KB / 678B C++98
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[20],len,n;//a记录每个单词使用次数
string str[20];//记录每个单词
ll check(string s1,string s2){
	ll num=min(s1.size(),s2.size());
	for(ll i=1;i<num;i++){
		bool f=true;
		for(ll j=0;j<i;j++)
			if(s1[s1.size()-i+j]!=s2[j]){
				f=false;
				break;
			}
		if(f==true) return i;
	}return 0;
}
void dfs(string st,ll num){
	len=max(num,len);
	for(ll i=0;i<n;i++){
		if(a[i]>=2) continue;
		ll m=check(st,str[i]);
		if(m>0){
			a[i]++;
			dfs(str[i],num+str[i].size()-m);
			a[i]--;
		}
	}return;
}
int main(){
	cin>>n;
	for(ll i=0;i<=n;i++)
		cin>>str[i];//特别强调：这里把最后输入的首字母作为单词中的一个输入
	dfs(' '+str[n],1);
	cout<<len;
	return 0;
}

评论

共 15 条评论，欢迎与作者交流。

正在加载评论...