题解 P1624 【单词缩写】

xgzc · 2017-09-23 19:59:41 · 题解

看大家都是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[110][200];//无效单词
char c1[200];
char c[200];
char all[200][200];//有效单词
int ma[26][200];//每个字母的有效位置
int tag[200];
int tag1[200];//两个标记
int cut[200];//单词的尾后位置
int sum[26];//出现的次数
int f[200][200];//dp数组

int main()
{
    scanf("%d\n",&n);
    for(RG int i=1;i<=n;i++)
    {
        scanf("%s",a[i]);
    }
    scanf("%s",c1);
    while(1)
    {
        RG int i_1_1=1;
        strcpy(c,c1);
        if(strcmp(c,"LAST")==0)
        {
            scanf("%s",all[i_1_1++]);
            if(strcmp(all[i_1_1-1],"CASE")==0) break;
        }
        while(cin>>all[i_1_1++])
        {
            RG int j=0;
            int len=strlen(all[i_1_1-1]);
            while(all[i_1_1-1][j]<'a'&&j<len) j++;
            if(j>=len)
            {
                strcpy(c1,all[i_1_1-1]);
                i_1_1--;
                break;
            }
            else
            {
                for(RG int i=1;i<=n;i++)
                {
                    if(strcmp(a[i],all[i_1_1-1])==0)
                    {
                        i_1_1--;
                        break;
                    }
                }
            }
        }
        i_1_1--;
        printf("%s ",c);
        int len=strlen(c);
        for(RG int i=0;i<len;i++)
        {
            c[i]=c[i]+32;
        }
        //读入
        if(len<i_1_1)//分类讨论
        {
            puts("is not a valid abbreviation");
        }
        else if(len==i_1_1)
        {
            int ans=1;
            for(RG int i=0;i<len;i++)
            {
                int len2=strlen(all[i+1]);
                RG int tmp=0;
                for(RG int j=0;j<len2;j++)
                {
                    if(all[i+1][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,0,sizeof(sum));
            memset(f,0,sizeof(f));
            memset(tag,0,sizeof(tag));
            memset(cut,0,sizeof(cut));
            memset(ma,0,sizeof(ma));
            int cz=strlen(all[1]);
            for(int i=2;i<=i_1_1;i++)
            {
                 strcpy(all[1]+cz,all[i]);
                 cut[i-1]=cz;
                 cz=strlen(all[1]);
            }
            //连串
            cut[i_1_1]=cz;
            for(int i=0;i<cz;i++)
            {
                int j=all[1][i]-'a';
                ma[j][++sum[j]]=i;
            }
            //记字母位置
            for(int k=0;k<len;k++)
            {
                int id=c[k]-'a';
                int ci=min(k+1,i_1_1);
                int ti=1;
                for(int i=0;i<cz;i++)
                {
                    tag1[i]=tag[i];
                }//备份
                for(int i=1;i<=sum[id]&&ma[id][i]<cut[ci];i++)
                {
                    while(ma[id][i]>=cut[ti]) ti++;
                    if(i_1_1-ti>len-k-1) continue;
                    if(k==0)
                    {
                        tag1[ma[id][i]]=0;//标记
                        f[k][i]=1;//初始值
                    }
                    else
                    {
                        int t=c[k-1]-'a';
                        for(int j=1;j<=sum[t];j++)
                        {
                            if(ma[t][j]<ma[id][i]&&ma[t][j]>=cut[ti-2]&&tag[ma[t][j]]==k-1)
                            {
                                f[k][i]+=f[k-1][j];//转移
                                tag1[ma[id][i]]=k;//标记×2
                            }
                        }
                    }
                }
                for(int i=0;i<cz;i++)
                {
                    tag[i]=tag1[i];//备份
                }
            }
            int ans=0;
            for(int i=1;i<=sum[c[len-1]-'a'];i++)
            {
                ans+=f[len-1][i];//求和
            }
            if(ans)
            {
                printf("can be formed in %d ways\n",ans);
            }
            else puts("is not a valid abbreviation");
        }
    }
    return 0;
}