LibreOJ2044 - 「CQOI2016」手机号码

Description

给出两个十一位数\(L,R\)，求\([L,R]\)内所有满足以下两个条件的数的个数。

出现至少\(3\)个相邻的相同数字；
不能同时出现\(4\)和\(8\)。

Solution

数位DP。

首先将问题转换成\(solve(R)-solve(L)\)的形式，这样只需要求不超过\(n\)的满足条件的数的个数。

定义\(dp[k][x][f_1][f_2][f_3][f_4]\)，其中\(k\)表示位数，\(x\)表示尾数，\(f_1\)表示第\(k\)位与第\(k-1\)位是否相同，\(f_2\)表示是否出现过三连，\(f_3\)表示\(4,8\)的出现情况（\(00,01,10,11\)），\(f_4\)表示是否在第\(k\)达到上限。

考虑第\(k+1\)位的每种取值\(i\)。若\(i=x\)，则\(f_1=1\)；若已有三连或原\(f_1=1\)且\(i=x\)，则\(f_2=1\)；若\(i\)等于\(4\)或\(8\)，改变\(f_3\)；若在第\(k\)位就达到上限且\(i\)等于n的第\(k+1\)位，则\(f_4=1\)。

用队列进行转移或循环每一维即可解决。

时间复杂度\(O(11×10×2×2×4×2\cdot10)\)。

Code

//「CQOI2016」手机号码

#include <cstdio>

#include <cstring>

#include <queue>

typedef long long lint;

struct state

{

    int k,x,f1,f2,f3,f4;

    state(int _k,int _x,int _f1,int _f2,int _f3,int _f4) {k=_k,x=_x,f1=_f1,f2=_f2,f3=_f3,f4=_f4;}

};

const int LEN=11;

lint dp[12][10][2][2][4][2];

std::queue<state> Q;

int is48(int x) {return (x==8)<<1|(x==4);}

lint solve(lint n)

{

    memset(dp,0,sizeof dp);

    int v[12];

    for(lint i=LEN,t=n;i>=1;i--,t/=10) v[i]=t%10;

    for(int i=1;i<=v[1];i++)

    {

        int f3=is48(i),f4=(i==v[1]);

        dp[1][i][0][0][f3][f4]=1;

        Q.push(state(1,i,0,0,f3,f4));

    }

    while(!Q.empty())

    {

        state s=Q.front(); Q.pop();

        int k=s.k,x=s.x,f1=s.f1,f2=s.f2,f3=s.f3,f4=s.f4,val=dp[k][x][f1][f2][f3][f4];

        if(k==LEN) continue;

        int t=f4?v[k+1]:9;

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

        {

            int _f1=(i==x),_f2=f2||f1&&(i==x),_f3=f3|is48(i),_f4=f4&&i==t;

            lint &r=dp[k+1][i][_f1][_f2][_f3][_f4];

            if(!r) Q.push(state(k+1,i,_f1,_f2,_f3,_f4));

            r+=val;

        }

    }

    lint r=0;

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

        for(int _f1=0;_f1<=1;_f1++)

            for(int _f3=0;_f3<=2;_f3++)

                r+=dp[LEN][i][_f1][1][_f3][0]+dp[LEN][i][_f1][1][_f3][1];

    return r;

}

int main()

{

    lint L,R;

    scanf("%lld%lld",&L,&R);

    if(L==(lint)1e10) printf("%lld\n",solve(R)-solve(L)+1);

    else printf("%lld\n",solve(R)-solve(L-1));

    return 0;

}

巴特西

LibreOJ2044 - 「CQOI2016」手机号码

Description

Solution

Code

最新文章

热门文章