[KCOJ3393]上马

题目描述 Description

Chicken在IEC（International Equestrianism Competition(国际马术表演赛)）惨跪，没有成功的上到马，他深刻的记得他的选手号是45，现在Chicken又将要⾯临新的⼀场⽐赛，他希望选手号不出现45（连续），同时他又⼗分讨厌2，所以也不希望4出现在准考证号中。现在他想知道在A和B之间有多少合法的选手号，你能否能满足他上马的欲望呢？

输入描述 Input Description

⼀⾏，2个正整数A，B

输出描述 Output Description

⼀⾏，⼀个整数，表⽰符合要求的准考证号的数量

样例输入 Sample Input

25 50

样例输出 Sample Output

数据范围及提示 Data Size & Hint

对于50%的数据，A,B<=1000000
对于100%的数据，A,B<=2*10^9

题外话：其实本题题目描述不是这样，但是因为原题目描述太和谐，于是博主就给改成了更和谐的题目描述。

这道题50分很好拿，暴力随便一搞就可以了。然后100分的话，没有什么思路的话可以打表，f(i)表示0-i之间有多少个合法的就可以，ans就是f(b)-f(a-1)。但是范围为2*10^9，数组开不下，所以我们选择分段打表，每10^6位打一个表，然后对于A,B可以判断出A，B所在块的位置，暴力算一下，中间的就用表预处理一下，一算就好了。下面贴出打表的代码，由于打表部分太长，省略掉表的部分。（int biao[]={此处为表的内容};）

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<queue>

using namespace std;

typedef long long LL;

#define mem(a,b) memset(a,b,sizeof(a))

inline int read()

{

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

    while(!isdigit(c)){if(c=='-')f=-;c=getchar();}

    while(isdigit(c)){x=x*+c-'';c=getchar();}

    return x*f;

}

const int maxn=;

bool judge(int now)

{

    int tmp=now;bool ok=;

    while(tmp)

    {

        int u=tmp%;

        if(u==)return false;

        if(u==){ok=;tmp/=;continue;}

        if(ok)

        {

            if(u==)return false;

            ok=;

        }

        tmp/=;

    }

    return true;

}

int count(int l,int r)

{

    int cnt=;

    for(int i=l;i<=r;i++)if(judge(i))cnt++;

    return cnt;

}

int a,b,pa,pb,ans;

int biao[]=};

int main()

{

    a=read();b=read();

    pa=a/+;pb=b/;

    if(pa-==pb)ans=count(a,b);

    else ans=count(a,pa*)+count(pb*+,b)+biao[pb]-biao[pa];

    printf("%d\n",ans);

    return ;

}

然后想正解，正解是数位DP，dp(i,j)表示一个i位数的第一位为j时候的方案数，这个很好处理，查询时还是类似的思路f(b)-f(A-1),用一个函数处理f(i)的值，此处细节比较多，直接贴代码：

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<queue>

#include<string>

using namespace std;

typedef long long LL;

#define mem(a,b) memset(a,b,sizeof(a))

inline int read()

{

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

    while(!isdigit(c)){if(c=='-')f=-;c=getchar();}

    while(isdigit(c)){x=x*+c-'';c=getchar();}

    return x*f;

}

const int maxl=;

int a,b,dp[][],la,lb,A[],B[],t,ans;

void init()

{

    for(int i=;i<;i++)if(i!=)dp[][i]=;

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

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

        {

            if(j==)continue;

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

            {

                if(k==)continue;

                if(j!= ||  k!=)dp[i][j]+=dp[i-][k];

            }

        }

    return;

}

int calc_A(int now)

{

    int ret=;

    if(now<=)return ;

    for(int i=;i<A[now];i++)

    {

        if(i==)continue;

        if(i== && A[now+]==)continue;

        ret+=dp[now][i];

    }

    if(now==)if(A[now]!= && (A[now]!= || A[now+]!=))ret++;

    if(A[now]!=)ret+=calc_A(now-);

    return ret;

}

int calc_B(int now)

{

    int ret=;

    if(now<=)return ;

    for(int i=;i<B[now];i++)

    {

        if(i==)continue;

        if(i== && B[now+]==)continue;

        ret+=dp[now][i];

    }

    if(now==)if(B[now]!= && (B[now]!= || B[now+]!=))ret++;

    if(B[now]!=)ret+=calc_B(now-);

    return ret;

}

int main()

{

    init();

    a=read()-;b=read();

    t=a;while(t)A[++la]=t%,t/=;

    if(a==)A[++la]=;

    t=b;while(t)B[++lb]=t%,t/=;

    printf("%d\n",calc_B(lb)-calc_A(la));

    return ;

}

巴特西

[KCOJ3393]上马

最新文章

热门文章