华师一附中OI组

标题: P1019 单词接龙 [打印本页]
作者: admin    时间: 2018-5-11 10:47
标题: P1019 单词接龙
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提高组第三题
作者: 黄煦喆    时间: 2018-5-26 21:05
  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    时间: 2018-5-26 21:18
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;

  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;

  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;

  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    时间: 2018-5-26 21:27
用二维数字add[i,j]表示单词i加到单词j的后面增加的长度，0表示不能添加，这样可以预先打印出这个数组查错，运行时也可以查表获得数据，减少主程序的代码长度。
主程序就很简单了，类似2个A 2个B等的全排列，找最大值就是，基本的pmn框架。
作者: 张笑宇    时间: 2018-5-26 22:05
  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.         }

  55.     }
  56.     cout<<ans;
  57.     return 0;
  58. }
复制代码
作者: 吴语林    时间: 2018-7-30 00:04
  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. }
复制代码
作者: 倚窗倾听风吹雨    时间: 2018-9-8 17:01
  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    时间: 2018-9-14 15:55
  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;

  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. }
复制代码
作者: 白至白    时间: 2018-9-25 19:41
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2