P1019 单词接龙

admin

https://www.luogu.org/problemnew/show/P1019
题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。

输入输出格式
输入格式：
输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出格式：
只需输出以此字母开头的最长的“龙”的长度

输入输出样例
输入样例#1：
5
at
touch
cheat
choose
tact
a
输出样例#1：
23
说明
（连成的“龙”为atoucheatactactouchoose）

NOIp2000提高组第三题

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. int n;
   
4. long long ans;
   
5. string ss[21],jl;
   
6. char ch;
   
7. int b[21][21],num[21];
   
8. int cp(int i,int j)
   
9. {
   
10.     int l=0,l1=ss[i].size(),l2=ss[j].size();
    
11.     char ch=ss[i][l1-1];
    
12.     int p=ss[j].find(ch);
    
13.     if(p==0)return l2-1;
    
14.     if(p==-1||p>=l1)return 0;
    
15.     for(int k=p;k>=0;k--)if(ss[j][k]!=ss[i][l1-1-p+k])return 0;
    
16.     return l2-p-1;
    
17. }
    
18. void ms(int k,long long s)
    
19. {
    
20.     short p=0;
    
21.     for(int i=1;i<=n;i++)
    
22.         if(b[k][i]&&num[i]>0)
    
23.     {
    
24.         p++;
    
25.         num[i]--;
    
26.         s+=b[k][i];
    
27.         int tt=ss[i].size();
    
28.         ms(i,s);
    
29.         num[i]++;
    
30.         s-=b[k][i];
    
31.     }
    
32.     if(p==0)ans=max(ans,s);
    
33. }
    
34. int main()
    
35. {
    
36.     cin>>n;
    
37.     for(int i=1;i<=n;i++)cin>>ss[i],num[i]=2;
    
38.     cin>>ch;
    
39.     for(int i=1;i<=n;i++)
    
40.         for(int j=1;j<=n;j++)
    
41.         b[i][j]=cp(i,j);//cout<<ss[i]<<' '<<ss[j]<<' '<<b[i][j]<<endl;}
    
42.     for(int i=1;i<=n;i++)
    
43.     {
    
44.         int len=ss[i].size();
    
45.         if(ss[i][0]==ch)
    
46.         {
    
47.             num[i]--;
    
48.             ms(i,len);
    
49.         }
    
50.     }
    
51.     cout<<ans;
    
52.     return 0;
    
53. }
    

复制代码

admin

17年前我的程序，2001年9月写的 ，好遥远呀！

1. const
   
2.   maxn=20;
   
3. var
   
4.   s         :   array[1..maxn] of string;
   
5.   head      :   char;
   
6.   best,i,n  :   integer;
   
7.   add       :   array[1..maxn,1..maxn] of integer;
   
8.   used      :   array[1..maxn] of integer;
   
9. 
   
10. procedure calcadd;
    
11. var
    
12.   i,j,k,t,min:integer;
    
13.   ok:boolean;
    
14. begin
    
15.   for i:=1 to n do
    
16.     for j:=1 to n do
    
17.     begin
    
18.       {取s[i]和s[j]中较小值}      
    
19.       if length(s[i])<length(s[j]) then
    
20.                 min:=length(s[i])
    
21.           else min:=length(s[j]);
    
22.       for k:=1 to min-1 do
    
23.       begin
    
24.         {check}
    
25.         ok:=true;
    
26.         for t:=1 to k do
    
27.           if s[j,t]<>s[i,length(s[i])-k+t] then
    
28.           begin
    
29.             ok:=false;
    
30.             break;
    
31.           end;
    
32.         {OK指能否连接上}
    
33.       if ok then break;
    
34.       end;
    
35.       if ok then
    
36.         add[i,j]:=length(s[j])-k
    
37.       else
    
38.         add[i,j]:=0;
    
39.     end;
    
40.    {计算连接后的长度}
    
41. end;
    
42. 
    
43. procedure search(last,len:integer);
    
44. var
    
45.   i:integer;
    
46. begin
    
47.   if len>best then best:=len;
    
48.   for i:=1 to n do
    
49.     if (add[last,i]>0)and(used[i]<2) then
    
50.     begin
    
51.       inc(used[i]);
    
52.       search(i,len+add[last,i]);
    
53.       dec(used[i]);
    
54.     end;
    
55. end;
    
56. 
    
57. begin
    
58.   readln(n);
    
59.   for i:=1 to n do
    
60.     readln(s[i]);
    
61.   readln(head);
    
62.   calcadd;
    
63.   best:=0;
    
64.   fillchar(used,sizeof(used),0);
    
65.   for i:=1 to n do
    
66.     if s[i,1]=head then
    
67.     begin
    
68.       used[i]:=1;
    
69.       search(i,length(s[i]));
    
70.       used[i]:=0;
    
71.     end;
    
72.   writeln(best);
    
73. end.
    

复制代码

admin

用二维数字add[i,j]表示单词i加到单词j的后面增加的长度，0表示不能添加，这样可以预先打印出这个数组查错，运行时也可以查表获得数据，减少主程序的代码长度。
主程序就很简单了，类似2个A 2个B等的全排列，找最大值就是，基本的pmn框架。

张笑宇

1. #include<iostream>
   
2. using namespace std;
   
3. int n,i,j,ii,c[25],ans=-1;///c字符出现次数
   
4. string s[25],ss;///s原字符 ss起点
   
5. int hb(string s1,string s2)
   
6. {
   
7.     int l1=s1.size(),l2=s2.size();
   
8.     for (i=1; i<=min(l1,l2)-1; i++) ///i枚举重复的长度
   
9.     {
   
10.         string ss1="",ss2="";
    
11.         for (j=l1-i; j<=l1-1; j++)
    
12.             ss1=ss1+s1[j];
    
13.         for (j=0; j<=i-1; j++)
    
14.             ss2=ss2+s2[j];
    
15.         ///cout<<ss1<<" "<<ss2<<" "<<s1<<" "<<s2<<endl;
    
16.         bool bb=true;
    
17.         for (j=0; j<=i-1; j++)
    
18.             if (ss1[j]!=ss2[j]) bb=false;
    
19.         if (bb) return i;
    
20.     }
    
21.     return 0;///找不到就返回0
    
22. }
    
23. void dfs(int sum,string last)
    
24. {
    
25.     ans=max(ans,sum);
    
26.     ///cout<<ans<<endl;
    
27.     for (int k=1; k<=n; k++)
    
28.     {
    
29.         if (c[k]>0)///还可以选择
    
30.         {
    
31.             int x=hb(last,s[k]);///最小公共长度
    
32.             if (x>0)
    
33.             {
    
34.                 c[k]--;
    
35.                 dfs(sum+s[k].size()-x,s[k]);
    
36.                 c[k]++;
    
37.             }
    
38.         }
    
39.     }
    
40. }
    
41. int main()
    
42. {
    
43.     cin>>n;
    
44.     for (i=1; i<=n; i++) cin>>s[i],c[i]=2;
    
45.     cin>>s[0];
    
46.     for (ii=1;ii<=n;ii++)
    
47.     {
    
48.         if (s[ii][0]==s[0][0])
    
49.         {
    
50.             c[ii]--;
    
51.             dfs(s[ii].size(),s[ii]);
    
52.             for (i=1;i<=n;i++) c[i]=2;
    
53.         }
    
54. 
    
55.     }
    
56.     cout<<ans;
    
57.     return 0;
    
58. }

复制代码

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int n,vis[100]={0},all=0;
    
14. string a[100];
    
15. char qi;
    
16. void dfs(int la,int s)
    
17. {
    
18.         all=max(s,all);
    
19.         int lon=a[la].length();
    
20.         for(int i=lon-1;i>=1;i--)
    
21.                 for(int j=0;j<n;j++)
    
22.                         if(vis[j]<=1&&a[j][0]==a[la][i]&&a[j].length()>lon-i)
    
23.                         {
    
24.                                 int e=1;
    
25.                                 for(int k=i;k<lon;k++)
    
26.                                         if(a[la][k]!=a[j][k-i])
    
27.                                         {
    
28.                                                 e=0;
    
29.                                                 break;
    
30.                                         }
    
31.                                 if(e)
    
32.                                 {
    
33.                                         vis[j]++;
    
34.                                         dfs(j,s-lon+i+a[j].length());
    
35.                                         vis[j]--;
    
36.                                 }
    
37.                         }
    
38.                        
    
39. }
    
40. int main()
    
41. {
    
42.         scanf("%d",&n);
    
43.         for(int i=0;i<n;i++)
    
44.                 cin>>a[i];
    
45.         cin>>qi;
    
46.         for(int i=0;i<n;i++)
    
47.                 if(a[i][0]==qi)
    
48.                 {
    
49.                         vis[i]++;
    
50.                         dfs(i,a[i].length());
    
51.                         vis[i]--;
    
52.                 }
    
53.         printf("%d",all);
    
54.         return 0;
    
55. }

复制代码

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. const int M=23;
   
4. string s[M];
   
5. char ch;
   
6. int visit[M],l[M][M],ans,an;
   
7. int n;
   
8. void match(int x,int y)
   
9. {
   
10.     bool b=0;
    
11.     int j=0;
    
12.     for(int i=s[x].size()-1;i>=0;i--)
    
13.     {
    
14.         for(int k=i;k<s[x].size();k++)
    
15.         if(s[x][k]!=s[y][j++])
    
16.         {
    
17.             b=1;
    
18.             break;
    
19.         }
    
20.         if(!b)
    
21.         {
    
22.             l[x][y]=s[x].size()-i;
    
23.             if(l[x][y]==min(s[x].size(),s[y].size()))l[x][y]=0;
    
24.             return;
    
25.         }
    
26.         b=0;
    
27.         j=0;
    
28.     }
    
29.     return;
    
30. }
    
31. void dfs(int x)
    
32. {
    
33.     bool flag=0;
    
34.     for(int i=1;i<=n;i++)
    
35.     {
    
36.         if(visit[i]>=2)continue;
    
37.         if(l[x][i]==0)continue;
    
38.         visit[i]++;
    
39.         flag=1;
    
40.         an+=s[i].size()-l[x][i];
    
41.         dfs(i);
    
42.         an-=s[i].size()-l[x][i];
    
43.         visit[i]--;
    
44.     }
    
45.     if(!flag)
    
46.     {
    
47.         ans=max(ans,an);
    
48.         return;
    
49.     }
    
50. }
    
51. int main()
    
52. {
    
53.     cin>>n;
    
54.     for(int i=1;i<=n;i++)
    
55.     cin>>s[i];
    
56.     cin>>ch;
    
57.     for(int i=1;i<=n;i++)
    
58.     {
    
59.         for(int j=1;j<=n;j++)
    
60.         {
    
61.             match(i,j);
    
62.      ///       cout<<l[i][j]<<" ";
    
63.         }
    
64.     ///    cout<<endl;
    
65.     }
    
66.     for(int i=1;i<=n;i++)
    
67.     {
    
68.         if(s[i][0]==ch)
    
69.         {
    
70.             visit[i]++;
    
71.             an=s[i].size();
    
72.             dfs(i);
    
73.             an=0;
    
74.             visit[i]--;
    
75.         }
    
76.     }
    
77.     cout<<ans<<endl;
    
78.     return 0;
    
79. }
    

复制代码

universehyf

1. #include<iostream>
   
2. using namespace std;
   
3. int l,minl,ans=0,cc=0,n;
   
4. char ss;
   
5. string s[30];
   
6. bool b[30][30];
   
7. int c[30][30];
   
8. int bb[30];
   
9. void dfs(int x,int las)
   
10. {
    
11.     for(int i=1;i<=n;i++)
    
12.         if((bb[i]>0)&&(b[las][i]==1)&&(x!=1||s[i][0]==ss))
    
13.         {
    
14.             cc=cc+s[i].size()-c[las][i];
    
15.             bb[i]--;
    
16.             /*if(x==n)
    
17.             {
    
18.                 //cout<<cc<<endl;
    
19. 
    
20.             }*/if(cc>ans) ans=cc;
    
21.             //cout<<cc;
    
22.              dfs(x+1,i);
    
23.             cc=cc-(s[i].size()-c[las][i]);
    
24.             bb[i]++;
    
25.         }
    
26. }
    
27. int main()
    
28. {
    
29.     cin>>n;
    
30.     for(int i=1; i<=n; i++)
    
31.         cin>>s[i];
    
32.     for(int i=1; i<=n; i++) bb[i]=2;
    
33.     for(int i=1;i<=n;i++) {b[0][i]=1;c[0][i]=0;}
    
34.     for(int i=1; i<=n; i++)
    
35.         for(int j=1; j<=n; j++)
    
36.         {
    
37.                 bool flag=true;l=s[i].size();
    
38.                 minl=min(s[i].size(),s[j].size());
    
39.                 for(int k=0; k<minl-1; k++)
    
40.                 {
    
41.                     if(!flag) break;
    
42.                     bool p=true;
    
43.                     for(int m=0; m<=k; m++)
    
44.                     {
    
45.                         if(s[i][l-1-k+m]!=s[j][m])
    
46.                             {
    
47.                                 p=false;
    
48.                                 break;
    
49.                             }
    
50.                     }
    
51.                     if(p)
    
52.                     {
    
53.                         b[i][j]=1;
    
54.                         c[i][j]=k+1;
    
55.                         flag=false;
    
56.                     }
    
57.                 }
    
58.         }
    
59.     /*for(int i=1;i<=n;i++)
    
60.         for(int j=1;j<=n;j++)
    
61.         {
    
62.             cout<<i<<" "<<j<<" ";
    
63.             if(b[i][j]) cout<<'y';
    
64.             else cout<<'n';
    
65.             cout<<" "<<c[i][j]<<endl;
    
66.         }*/
    
67.     cin>>ss;
    
68.     dfs(1,0);
    
69.     cout<<ans;
    
70.     return 0;
    
71. }

复制代码

白至白

1. #include<iostream>
   
2. #include<cstring>
   
3. using namespace std;
   
4. int n,maxx=0;
   
5. string word[21];
   
6. int b[21];
   
7. char ch;
   
8. int check(string s1,string s2) {
   
9.         int len1=s1.size(),len2=s2.size();
   
10.         int k=len2>=len1?1:len1-len2;
    
11.         for(int i=len1-1; i>=k ; i--)
    
12.                 if(s1[i]==s2[0]) {
    
13.                         int j;
    
14.                         for(j=i+1; s1[j]==s2[j-i]&&j<len1; j++);
    
15.                         if(j==len1) {
    
16. //                                cout<<"len "<<len2-len1+i<<endl;
    
17.                                 return len2-len1+i;
    
18.                         }
    
19.                 }
    
20.         return 0;
    
21. }
    
22. void dfs(string s,int sum) {
    
23.         int flag=0;
    
24.         for(int i=0; i<n; i++)if(b[i]) {
    
25.                         int che=check(s,word[i]);
    
26.                         if(che) {
    
27.                                 flag=1;
    
28. //                                cout<<s<<' '<<word[i]<<endl;
    
29.                                 b[i]--;
    
30.                                 dfs(word[i],sum+che);
    
31.                                 b[i]++;
    
32.                         } else continue;
    
33.                 }
    
34.         if(flag==0) {
    
35.                 if(sum>maxx)maxx=sum;
    
36.                 return ;
    
37.         }
    
38. }
    
39. int main() {
    
40.         cin>>n;
    
41.         for(int i=0; i<n; i++) {
    
42.                 b[i]=2;
    
43.                 cin>>word[i];
    
44.         }
    
45.         cin>>ch;
    
46.         for(int i=0; i<n; i++)
    
47.                 if(word[i][0]==ch) {
    
48.                         b[i]--;
    
49.                         dfs(word[i],word[i].size());
    
50.                 }
    
51.         cout<<maxx<<endl;
    
52.         return 0;
    
53. }

复制代码