「百度之星」最强密码

2015年6月8日3,7543

由于近来密码库被盗的现象层出不穷，度度熊决定为自己的账号找一个最强密码。在研究了密码库很久之后，它总结出了一个规律：密码库中的所有密码都是一个“密码生成串”的子序列（某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列）。

经过强大的计算集群夜以继日的工作，度度熊得到了这个“密码生成串”。现在它希望找到一个“最强密码”，不是这个“密码生成串”的子序列，并且长度最短。

任性的度度熊还希望知道这样的“最强密码”有多少个。幸运的是，“密码生成串”和“最强密码”都只包含小写字母。

题解

yy一下构建出一张图，即每个结点加个字母能转移到另一个结点

然后递推一下即可

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define mod 1000000007
#define ll long long
using namespace std;
int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int T,n;
int f[100005],g[100005];
char a[100005];
vector<int>e[100005];
int main()
{
    T=read();
    int cas=0;
    while(T--)
    {
        cas++;
        printf("Case #%d:\n",cas);
        scanf("%s",a+1);
        n=strlen(a+1);
        for(int i=0;i<=n+1;i++)e[i].clear(),f[i]=inf,g[i]=0;
        for(int i=1;i<=26;i++)
        {
            char c=i+'a'-1;
            int last=n+1;
            for(int j=n;j>=0;j--)
            {
                e[j].push_back(last);
                if(a[j]==c)last=j;
            }
        }
        f[0]=0;g[0]=1;
        for(int i=0;i<=n+1;i++)
        {
            for(int j=0;j<e[i].size();j++)
            {
                if(f[i]+1<f[e[i][j]])f[e[i][j]]=f[i]+1,g[e[i][j]]=0;
                if(f[i]+1==f[e[i][j]])g[e[i][j]]+=g[i],g[e[i][j]]%=mod;
            }
        }
        printf("%d %d\n",f[n+1],g[n+1]);
    }
    return 0;
}

#include<map>

#include<set>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define mod 1000000007

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char c=getchar();

while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

return x*f;

}

int T,n;

int f[100005],g[100005];

char a[100005];

vector<int>e[100005];

int main()

{

T=read();

int cas=0;

while(T--)

{

cas++;

printf("Case #%d:\n",cas);

scanf("%s",a+1);

n=strlen(a+1);

for(int i=0;i<=n+1;i++)e[i].clear(),f[i]=inf,g[i]=0;

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

{

char c=i+'a'-1;

int last=n+1;

for(int j=n;j>=0;j--)

{

e[j].push_back(last);

if(a[j]==c)last=j;

}

f[0]=0;g[0]=1;

for(int i=0;i<=n+1;i++)

{

for(int j=0;j<e[i].size();j++)

{

if(f[i]+1<f[e[i][j]])f[e[i][j]]=f[i]+1,g[e[i][j]]=0;

if(f[i]+1==f[e[i][j]])g[e[i][j]]+=g[i],g[e[i][j]]%=mod;

}

printf("%d %d\n",f[n+1],g[n+1]);

}

return 0;

}

« PKUSC 2014 #2 「百度之星」大搬家 »

彭柯宾

大神，你这个节点是什么意思？求详细解释一下，谢谢啦

hzwer

当前匹配位置

彭柯宾

哦哦，对的，这个题已经搞懂了，感觉真是神DP，当时比赛的时候没看出来。。。太弱了23333

hzwer.com _ Home | http://hzwer.com

「百度之星」最强密码

分类目录

热门文章

Myfriends

近期评论