[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=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int maxn=10010;
bool judge(int now)
{
    int tmp=now;bool ok=0; 
    while(tmp)
    {
        int u=tmp%10;
        if(u==4)return false;
        if(u==7){ok=1;tmp/=10;continue;}
        if(ok)
        {
            if(u==3)return false;
            ok=0;
        }
        tmp/=10;
    }
    return true;
} 
int count(int l,int r)
{
    int cnt=0;
    for(int i=l;i<=r;i++)if(judge(i))cnt++;
    return cnt;
}
int a,b,pa,pb,ans;
int biao[10010]=}; 
int main()
{

    a=read();b=read();
    pa=a/1000000+1;pb=b/1000000;
    if(pa-1==pb)ans=count(a,b);
    else ans=count(a,pa*1000000)+count(pb*1000000+1,b)+biao[pb]-biao[pa];
    printf("%d
",ans);
    return 0;
}

View Code

然后想正解，正解是数位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=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int maxl=10;
int a,b,dp[15][15],la,lb,A[20],B[20],t,ans;
void init()
{
    for(int i=0;i<10;i++)if(i!=2)dp[1][i]=1;
    for(int i=2;i<=10;i++)
        for(int j=0;j<10;j++)
        {
            if(j==2)continue;
            for(int k=0;k<10;k++)
            {
                if(k==2)continue;
                if(j!=4 ||  k!=5)dp[i][j]+=dp[i-1][k];
            }
        }
    return;
}
int calc_A(int now)
{
    int ret=0;
    if(now<=0)return 0;
    for(int i=0;i<A[now];i++)
    {
        if(i==2)continue;
        if(i==5 && A[now+1]==4)continue;
        ret+=dp[now][i];
    }
    if(now==1)if(A[now]!=2 && (A[now]!=5 || A[now+1]!=4))ret++;
    if(A[now]!=2)ret+=calc_A(now-1);
    return ret;
}
int calc_B(int now)
{
    int ret=0;
    if(now<=0)return 0;
    for(int i=0;i<B[now];i++)
    {
        if(i==2)continue;
        if(i==5 && B[now+1]==4)continue;
        ret+=dp[now][i];
    }
    if(now==1)if(B[now]!=2 && (B[now]!=5 || B[now+1]!=4))ret++;
    if(B[now]!=2)ret+=calc_B(now-1);
    return ret;
}
int main()
{
    init();
    a=read()-1;b=read();
    t=a;while(t)A[++la]=t%10,t/=10;
    if(a==0)A[++la]=0;
    t=b;while(t)B[++lb]=t%10,t/=10;
    printf("%d
",calc_B(lb)-calc_A(la));   
    return 0;
}

View Code