0
已解决
中级守护
麻烦个位大佬解答！！
0
已采纳
高级光能
此题乍一看，似乎并不是很难，但需要处理以下一些情况：
1.单词不能包含。
2.每个单词可以用2次。
3.重合部分长度需减去。
4.重合长度是不确定的。
现在谈谈大体思路：
首先此题一定用深搜。
其次存单词时，从f[1]开始存，而最后一个表示开头的字母存f[0]。
why?我们接龙时就直接从f[0]开始便不需要处理开头的单词。
接下来处理问题：
1.关于包含，只需查到长度len-1即可，如果还不符合便不符合。
2.我们可以定义一个v数组，判断单词使用次数，在使用前判断if(v[i]<2)每使用一次变v[i]++，注意递归完后v[i]--。
然后先看4.在判断单词是否可以连接时，我们从i=0,循环到i=n，即所有单词查完，如果单词可用便接着循环，查待连接单词，如果某一位与可连接单词相同，便再循环，定义一个临时变量t，从后一位开始，查，如果不同，直接t=0,break,出循环后if(t)便代表可连接，开始递归下一个，别忘了v[i]++。（此部分便是核心算法）
关于3.在判断可连接时，总长度L便加上两个单词长度，然后前面的最后盘点是否完全符合的循环计数变量定义在外面，L直接减去它便是接龙长度了。
不知道是否听懂……
void jl(int x,int len)//两个参数分别代表待连接单词的结构体下标和长度
{
for(int i=1;i<=n;i++)
if(c[i].v<2)//判断访问次数
for(int j=0;j<c[x].len;j++)//查待连接单词的每一个字母
if(c[x].s[j]==c[i].s[0])
{
int k=1;//将循环变量定义在外面，方便以后相减
int t=1;//临时变量（其实bool就行）
for(int l=j+1;l<c[x].len&&k<c[i].len;k++,l++)//l表示待连接单词下标，k是可连接单词下标，所以在循环条件中需满足它们小于（因为不能包含，所以不能等于）单词长度
if(c[x].s[l]!=c[i].s[k])
{
t=0;
break;
}
if(t)
{
c[i].v++;
jl(i,len+c[i].len-k);//更新长度和下标后递归
c[i].v--;//完成后一定记得--
}
}
if(len>maxn)
maxn=len;//不解释
}
0
初级天翼
function pd(s1,s2:string):longint;//两个字符串连接的长度计算
var
max,i:longint;
s:string;
begin
max:=10000000;
for i:=1 to length(s1) do
begin
s:=copy(s1,i,length(s1)-i+1);
if(pos(s,s2)=1)and(length(s)<max) then max:=length(s);
end;
if(max=10000000) then exit(-1);
exit(length(s2)-max);
end;
procedure search(t,sum:longint;ss,s1:string);//搜索回溯核心代码
var
i:longint;
begin
if(sum>ans) then ans:=sum;
for i:=1 to n do
if(b[i]<2)and(pos(s[i],s1)=0)and(pd(s1,s[i])<>-1)or(t=1)and(s[i][1]=ss[1]) then
begin
inc(b[i]);
if(t<>1) then search(t+1,sum+pd(s1,s[i]),ss+s[i],s[i])
else search(t+1,length(s[i]),ss+s[i],s[i]);
dec(b[i]);
end;
end;
0
初级天翼
先定义一个结构体，然后进行一系列操作
函数代码如下:
struct sentence{
string sen;
int len;
int mark;
}a[21];
int sum,lenth=1,maxn=0;
int judge(string u,string i)
{
int m=min(u.length(),i.length());
for(int w=1;w<m;w++)
{
if(u.substr(u.length()-w)==i.substr(0,w)) return w;
}
return 0;
}
void dfs(string b)
{
maxn=maxn<lenth?lenth:maxn;
for(int i=1;i<=sum;i++)
{
if(a[i].mark<2)
{
a[i].mark++;
if(judge(b,a[i].sen)>0)
{
int res=judge(b,a[i].sen);
lenth=lenth+a[i].len-res;
dfs(a[i].sen);
lenth=lenth-a[i].len+res;
res=0;
}
a[i].mark--;
}
}
}
0
缔造者
w
0
初级光能
核心代码
void get_ready(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=s[i].size()-1;k++){
string tmp1,tmp2;
tmp1.assign(s[i],s[i].size()-k,k);
if(s[j].size()<=k) break;
tmp2.assign(s[j],0,k);
if(tmp1==tmp2){
vec[i].push_back(j);
length[i][j]=k;
break;
}
}
}
}
}
void dfs(int pos,int len){
int flag=0;
for(int i=0;i<vec[pos].size();i++){
if(v[vec[pos][i]]<2){
v[vec[pos][i]]++;
flag=1;
dfs(vec[pos][i],len+s[vec[pos][i]].size()-length[pos][vec[pos][i]]);
v[vec[pos][i]]--;
}
}
if(flag==0){
ans=max(ans,len);
return ;
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>s[i];
}
cin>>head;
get_ready();
for(int i=1;i<=n;i++){
if(head[0]==s[i][0]){
v[i]++;
dfs(i,s[i].size());
v[i]--;
}
}
cout<<ans<<endl;
0
缔造者之神
1
