单词接龙
链接：https://www.nowcoder.com/acm/contest/153/1072
来源：牛客网
来源：牛客网
2000普及组-单词接龙
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。
输入描述:
输入的第一行为一个单独的整数n(n ≤ 20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出描述:
只需输出以此字母开头的最长的“龙”的长度
代码过不了
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int n;
string str[30];
int len_str,sum=0;
int times[30]={0};
void dfs(int x)
{
int i,j;
int p,q;
int num;
int work;
for(i=1;i<str[x].length();i++)
{
num=0;
for(j=1;j<=n;j++)
{
if(times[j]<2)
{
if(str[x][i]==str[j][0])
{
p=i,q=0,work=0;
while(p<=str[x].length()-1)
{
if(str[x][p]!=str[j][q])
{
num++;
work++;
break;
}
p++;
q++;
}
if(!work&&q!=str[j].length())
{
len_str+=str[j].length()-q;
times[j]++;
dfs(j);
len_str-=str[j].length()-q;
times[j]--;
}
}
else num++;
}
else num++;
}
if(num==n&&i==str[x].length()-1)
{
if(sum<len_str) sum=len_str;
return;
}
}
}
int main()
{
int i;
cin>>n;
for(i=1;i<=n+1;i++)
cin>>str[i];
for(i=1;i<=n;i++)
if(str[i][0]==str[n+1][0])
{
times[i]++;
len_str=str[i].length();
dfs(i);
}
cout<<sum<<endl;
return 0;
}
#include<cstdio>
#include<string>
using namespace std;
int n;
string str[30];
int len_str,sum=0;
int times[30]={0};
void dfs(int x)
{
int i,j;
int p,q;
int num;
int work;
for(i=1;i<str[x].length();i++)
{
num=0;
for(j=1;j<=n;j++)
{
if(times[j]<2)
{
if(str[x][i]==str[j][0])
{
p=i,q=0,work=0;
while(p<=str[x].length()-1)
{
if(str[x][p]!=str[j][q])
{
num++;
work++;
break;
}
p++;
q++;
}
if(!work&&q!=str[j].length())
{
len_str+=str[j].length()-q;
times[j]++;
dfs(j);
len_str-=str[j].length()-q;
times[j]--;
}
}
else num++;
}
else num++;
}
if(num==n&&i==str[x].length()-1)
{
if(sum<len_str) sum=len_str;
return;
}
}
}
int main()
{
int i;
cin>>n;
for(i=1;i<=n+1;i++)
cin>>str[i];
for(i=1;i<=n;i++)
if(str[i][0]==str[n+1][0])
{
times[i]++;
len_str=str[i].length();
dfs(i);
}
cout<<sum<<endl;
return 0;
}
和
#include<bits/stdc++.h>
using namespace std;
int n;
char a[22] [22],b[20],c[22] [22];
int flag[22];
char s;
int maxx=0,ans=0;
int cmp(char a[],char b[])
{
int m=0;
int lena=strlen(a);
int lenb=strlen(b);
int j=0;
do
{
j++;
int i=0;
for(i=0;i<=j-1;i++)
{
if(b[i]!=a[lena-j+i]) break;
}
if(i==j) return lenb-j;
else continue;
}
while(j<lena&&j<lenb);
return 0;
}
int dfs(int k)
{
int q=0;
for(int i=1;i<=n;i++)
{
if(flag[i])
{
int y=cmp(c[k-1],a[i]);
if(k==1&&c[0][0]==a[i][0])
{
strcpy(c[k],a[i]);
flag[i]--;
ans=strlen(a[i]);
q++;
dfs(k+1);
flag[i]++;
}
else if(y&&k!=1)
{
strcpy(c[k],a[i]);
flag[i]--;
ans+=y;
q++;
dfs(k+1);
ans-=y;
flag[i]++;
}
}
}
if(q==0) maxx=max(maxx,ans);
}
int main()
{
for(int i=0;i<=21;i++)
flag[i]=2;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
cin>>s;
c[0][0]=s;
dfs(1);
cout<<maxx;
return 0;
}
using namespace std;
int n;
char a[22] [22],b[20],c[22] [22];
int flag[22];
char s;
int maxx=0,ans=0;
int cmp(char a[],char b[])
{
int m=0;
int lena=strlen(a);
int lenb=strlen(b);
int j=0;
do
{
j++;
int i=0;
for(i=0;i<=j-1;i++)
{
if(b[i]!=a[lena-j+i]) break;
}
if(i==j) return lenb-j;
else continue;
}
while(j<lena&&j<lenb);
return 0;
}
int dfs(int k)
{
int q=0;
for(int i=1;i<=n;i++)
{
if(flag[i])
{
int y=cmp(c[k-1],a[i]);
if(k==1&&c[0][0]==a[i][0])
{
strcpy(c[k],a[i]);
flag[i]--;
ans=strlen(a[i]);
q++;
dfs(k+1);
flag[i]++;
}
else if(y&&k!=1)
{
strcpy(c[k],a[i]);
flag[i]--;
ans+=y;
q++;
dfs(k+1);
ans-=y;
flag[i]++;
}
}
}
if(q==0) maxx=max(maxx,ans);
}
int main()
{
for(int i=0;i<=21;i++)
flag[i]=2;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
cin>>s;
c[0][0]=s;
dfs(1);
cout<<maxx;
return 0;
}
投递BOSS直聘等公司6个岗位
查看1道真题和解析