单词接龙(dragon)
时间限制: 1 Sec 内存限制: 64 MB
提交: 12 解决: 5
[提交][状态][讨论版]
题目描述
单
词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在
“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻
的两部分不能存在包含关系，例如at和atide间不能相连。
输入
第1行为一个单独的整数n(n≤20)，表示单词数，以下n行每行有一个单词，输入的最后1行为一个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
输出
输出以此字母开头的最长的“龙”的长度。
样例输入
5
at
touch
cheat
choose
tact
a
样例输出
23
提示
样例说明：连成的“龙”为atoucheatactactouchoose。
【分析】哎 这个题 一开始WA了好几发 仔细检查发现好多BUG 主要是判断两个字符串相交部分想错了 题目要求最长龙 而我找重复子字符串时 是从
首字符串头部开始遍历找的 导致在有些情况下把重复字符串找长了 例如：（头）CDABABA （尾）BABABA 这个时候重复字符串应该是BA 而不应该
是BABA 哎 还是我太菜 路还长 需要学的还很多 下面是AC代码 可能还可以优化 谁让我太菜 wo te e fa ke?
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define inf 0x3f3f3f3f
#define mod 1000000007
typedef long long ll;
using namespace std;
const int N=;
int n,dp[N],len;
int w[][];
int g[];
int b,c;
string str[],ch;
int maxn=;
map<string,int>p,pp;
struct man
{
string sa;
int aa[];
}; int charge(string a,string b)
{
for(int ii=a.size()-;ii>=;ii--)
{
int jj=ii,kk=;
while(jj<a.size()&&kk<b.size())
{
if(a[jj]!=b[kk])break;
jj++;kk++;
}
if(jj==a.size()&&ii!=)return (kk);
else if(jj==a.size()&&ii==) return ;
else if(jj==a.size()&&kk==b.size())return ;
}
} void bfs()
{
queue<man>q;
for(int i=;i<n;i++)
{
if(str[i][]==ch[])
{
man CH;
CH.sa=str[i];
for(int j=;j<=;j++){CH.aa[j]=;if(i==j)CH.aa[i]=;}
q.push(CH);
}
}
while(!q.empty())
{
man t=q.front();
int y=t.sa.size();
maxn=max(maxn,y);
q.pop();
for(int i=;i<n;i++)
{
string l=str[i],k;
if(t.aa[i]>=)continue;
int mm=charge(t.sa,l);
//printf("!!!%d\n",mm);
if(mm==)continue;
else
{
man K=t; K.aa[i]++;
l= l.erase(,mm);
k=t.sa+l;
K.sa=k;
if(pp[k]!=){q.push(K);pp[k]=;}
}
}
}
} int main() {
memset(w,,sizeof(w));
cin>>n;
for(int i=;i<n;i++)
{
cin>>str[i];
p[str[i]]=;
}
cin>>ch;
bfs();
cout<<maxn<<endl;
return ;
}
下面是我们实验室一个大神写的DFS。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
#include <queue>
#include <string>
#include <vector>
#include<functional>
#include <set>
#include <map>
#include <climits>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define fi first
#define se second
#define ping(x,y) ((x-y)*(x-y))
#define mst(x,y) memset(x,y,sizeof(x))
#define mcp(x,y) memcpy(x,y,sizeof(y))
using namespace std;
#define gamma 0.5772156649015328606065120
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define N 1000005
#define maxn 10005
typedef pair<int,int> PII;
typedef long long LL; int n,m,k,ans,temp;
string str[];
int len[];
int vis[];
int pic[][];
int match(int x,int y){
int res=;
int tlen=min(len[x],len[y]);
for(int i=;i<=tlen;++i){
int j=len[x]-i;k=;
while(j<len[x]&&k<len[y]&&k<i){
if(str[x][j]!=str[y][k])break;
++j;++k;
}
if(k==i){
res=i;
break;
}
}
return res==tlen?:res;
}
void init(){
for(int i=,t;i<=n;++i)
for(int j=;j<=n;++j){
if(t=match(i,j)){
pic[i][j]=t;
}
}
}
void dfs(int x){
if(temp>ans)ans=temp;
for(int i=;i<=n;++i)if(!vis[i]&&pic[x][i]){
temp=temp+len[i]-pic[x][i];
vis[i]=;
dfs(i);
vis[i]=;
temp=temp+pic[x][i]-len[i];
}
}
int main() {
//freopen("in.txt","r",stdin);
int i,j,group;
cin>>n;n<<=;
for(i=;i<=n;i+=){
cin>>str[i];
str[i+]=str[i];
len[i]=len[i+]=str[i].length();
}
char ch;cin>>ch;
init();
ans=;
for(i=;i<=n;++i)if(str[i][]==ch){
temp=len[i];
vis[i]=;
dfs(i);
vis[i]=;
}
cout<<ans<<endl;
return ;
}
