P1624 单词缩写

题目描述

树树发现好多计算机中的单词都是缩写，如GDB是全称Gnu DeBug的缩写。但是，有时候缩写对应的全称会不固定，如缩写LINUX可以理解为：

（1） LINus’s UniX

（2） LINUs’s miniX

（3） Linux Is Not UniX

现在树树给出一个单词缩写，以及一个固定的全称（若干个单词组成，空格隔开）。全

称中可能会有无效的单词，需要忽略掉，一个合法缩写要求每个有效单词中至少有一个字符出现在缩写中，所写必须按顺序出现在全称中。

对于给定的缩写和一个固定的全称，问有多少种解释方法？解释方法为所写的每个字母在全称每个有效单词中出现的位置，有一个字母位置不同，就认为是不同的解释方法。

输入输出格式

输入格式：

第一行输入一个N，表示有N个无效单词；

接下来N行分别描述一个由小写字母组成的无效单词；

最后是若干个询问，先给出缩写（只有大写字母），然后给出一个全称，读入以“LAST CASE”结束。

[数据规模]

1≤N≤100，每行字符串长度不超过150，询问次数不超过20，最后方案数不超过10^9。

输出格式：

对于每个询问先输出缩写，如果当前缩写不合法，则输出“is not a valid abbreviation”,否则输出“can be formaed in i ways”(i表示解释方法数)

输入输出样例

输入样例#1：复制

2

and

of

ACM academy of computer makers

RADAR radio detection and ranging

LAST CASE

输出样例#1：复制

ACM can be formed in 2 ways

RADAR is not a valid abbreviation

洛谷题解

先暴力去掉所有的单词，只对有效单词进行计算。

dp[i][j]表示前i个单词使用了前j个大写字母的方案数

初始条件dp[0][0]=1

转移：若第i个单词使用第j到第j+k个大写字母的方案数为temp[k]

则dp[i][j+k]=dp[i-1][j-1]*temp[k]

最终ans=dp[n][m]

时间复杂度Ｏ（Ｌ１＊Ｎ＊Ｌ２＊Ｌ２）

空间复杂度Ｏ(Ｌ１*Ｎ*Ｌ２)

L1缩写长度 N全称中单词的个数 L2全称中一个单词的长度

这属于两个串匹配的问题，就一个前i，一个前j就好，反正是找子问题。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 char w[][];

 char s[],let[];

 char over[]={'L','A','S','T',' ','C','A','S','E'};

 struct word

 {

     char c[];

     int l;

 }a[];

 int t,n,m,len;

 int dp[][],temp[];

 bool Case_is_Over()

 {

     for (int i=;i<=;i++)

         if (s[i]!=over[i]) return false;

     return true;

 }

 int main()

 {

     freopen("abbr.in","r",stdin);

     freopen("abbr.out","w",stdout);

     scanf("%d\n",&t);

     for (int i=;i<=t;i++) scanf("%s",w[i]);

     while ()

     {

         char ch=getchar();len=;

         while ( ! ( (ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z') || ch==' ' ) ) ch=getchar();

         while ( (ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z') || ch==' ' ) s[len++]=ch,ch=getchar();

         n=m=;//设每个询问有n个单词，m个大写字母

         if (Case_is_Over()) break;

         int p=;

         for (int i=;i<;i++) memset(a[i].c,,sizeof(a[i].c)),a[i].l=;

         while (s[p]>='A'&&s[p]<='Z')

         {

             printf("%c",s[p]);

             let[++m]=s[p]+;

             p++;

         }

         p++;

         while (p<len)

         {

             n++;

             while (s[p]>='a'&&s[p]<='z')

             {

                 a[n].c[a[n].l++]=s[p];

                 p++;

             }

             for (int i=;i<=t;i++)

                 if (strcmp(w[i],a[n].c)==)

                 {

                     memset(a[n].c,,sizeof(a[n].c));

                     a[n].l=;

                     n--;break;

                 }

             p++;

         }

         memset(dp,,sizeof(dp));

         dp[][]=;

         for (int i=;i<=n;i++) //枚举单词

             for (int j=i;j<=i+m-n;j++) //枚举当前单词使用大写字母的起始位置

             {

                 memset(temp,,sizeof(temp));

                 for (int p=;p<a[i].l;p++) //第i个单词的第p个位置

                     for (int k=min(i+m-n-j,p);k>=;k--) //恰好等于第j+k个大写字母

                         if (let[j+k]==a[i].c[p])

                             if (k) temp[k]+=temp[k-];

                             else temp[k]++;

                 for (int k=i+m-n-j;k>=;k--)

                     dp[i][j+k]+=dp[i-][j-]*temp[k];

             }

         if (dp[n][m]) printf(" can be formed in %d ways\n",dp[n][m]);

         else printf(" is not a valid abbreviation\n");

     }

     return ;

 }

看大家都是N^4或N³算法，N²算法还没有，~~赶紧水一发~~

基本思路:

把所有串连接起来，记录每个串的尾后位置，

设f[k][i]表示现在在处理缩写的第K个字符，在大字符串中第I个位置对前面字符的总贡献数，则f[k][i]=Σf[k-1][j]，

其中j表示满足条件的前一个缩写字符。其中满足条件的定义为“无空缺单词，且是前一个字母”。则答案为Σf[最后一个字符][j],(1<=j<=n)。

为避免出现同一字母出现位置的不同，用一个数组进行标记即可。

标记要一次打完才能更新！！！

 #include<bits/stdc++.h>

 #define RG register

 using namespace std;

 int n;

 char a[][];//无效单词

 char c1[];

 char c[];

 char all[][];//有效单词

 int ma[][];//每个字母的有效位置

 int tag[];

 int tag1[];//两个标记

 int cut[];//单词的尾后位置

 int sum[];//出现的次数

 int f[][];//dp数组

 int main()

 {

     scanf("%d\n",&n);

     for(RG int i=;i<=n;i++)

     {

         scanf("%s",a[i]);

     }

     scanf("%s",c1);

     while()

     {

         RG int i_1_1=;

         strcpy(c,c1);

         if(strcmp(c,"LAST")==)

         {

             scanf("%s",all[i_1_1++]);

             if(strcmp(all[i_1_1-],"CASE")==) break;

         }

         while(cin>>all[i_1_1++])

         {

             RG int j=;

             int len=strlen(all[i_1_1-]);

             while(all[i_1_1-][j]<'a'&&j<len) j++;

             if(j>=len)

             {

                 strcpy(c1,all[i_1_1-]);

                 i_1_1--;

                 break;

             }

             else

             {

                 for(RG int i=;i<=n;i++)

                 {

                     if(strcmp(a[i],all[i_1_1-])==)

                     {

                         i_1_1--;

                         break;

                     }

                 }

             }

         }

         i_1_1--;

         printf("%s ",c);

         int len=strlen(c);

         for(RG int i=;i<len;i++)

         {

             c[i]=c[i]+;

         }

         //读入

         if(len<i_1_1)//分类讨论

         {

             puts("is not a valid abbreviation");

         }

         else if(len==i_1_1)

         {

             int ans=;

             for(RG int i=;i<len;i++)

             {

                 int len2=strlen(all[i+]);

                 RG int tmp=;

                 for(RG int j=;j<len2;j++)

                 {

                     if(all[i+][j]==c[i]) tmp++;

                 }

                 if(tmp) ans*=tmp;

                 else

                 {

                     puts("is not a valid abbreviation");

                     break;

                 }

             }

             printf("can be formed in %d ways\n",ans);

         }

         else //重点

         {

             memset(sum,,sizeof(sum));

             memset(f,,sizeof(f));

             memset(tag,,sizeof(tag));

             memset(cut,,sizeof(cut));

             memset(ma,,sizeof(ma));

             int cz=strlen(all[]);

             for(int i=;i<=i_1_1;i++)

             {

                  strcpy(all[]+cz,all[i]);

                  cut[i-]=cz;

                  cz=strlen(all[]);

             }

             //连串

             cut[i_1_1]=cz;

             for(int i=;i<cz;i++)

             {

                 int j=all[][i]-'a';

                 ma[j][++sum[j]]=i;

             }

             //记字母位置

             for(int k=;k<len;k++)

             {

                 int id=c[k]-'a';

                 int ci=min(k+,i_1_1);

                 int ti=;

                 for(int i=;i<cz;i++)

                 {

                     tag1[i]=tag[i];

                 }//备份

                 for(int i=;i<=sum[id]&&ma[id][i]<cut[ci];i++)

                 {

                     while(ma[id][i]>=cut[ti]) ti++;

                     if(i_1_1-ti>len-k-) continue;

                     if(k==)

                     {

                         tag1[ma[id][i]]=;//标记

                         f[k][i]=;//初始值

                     }

                     else

                     {

                         int t=c[k-]-'a';

                         for(int j=;j<=sum[t];j++)

                         {

                             if(ma[t][j]<ma[id][i]&&ma[t][j]>=cut[ti-]&&tag[ma[t][j]]==k-)

                             {

                                 f[k][i]+=f[k-][j];//转移

                                 tag1[ma[id][i]]=k;//标记×2

                             }

                         }

                     }

                 }

                 for(int i=;i<cz;i++)

                 {

                     tag[i]=tag1[i];//备份

                 }

             }

             int ans=;

             for(int i=;i<=sum[c[len-]-'a'];i++)

             {

                 ans+=f[len-][i];//求和

             }

             if(ans)

             {

                 printf("can be formed in %d ways\n",ans);

             }

             else puts("is not a valid abbreviation");

         }

     }

     return ;

 }

巴特西

P1624 单词缩写

P1624 单词缩写

题目描述

输入输出格式

输入输出样例

标记要一次打完才能更新！！！

最新文章

热门文章