首页 > 代码库 > hdu5898 odd-even number(数位dp)

hdu5898 odd-even number(数位dp)

题意:

求L到R区间内,连续奇数个数是偶数,连续偶数个数是奇数的数的个数

思路:

裸数位dp,赛场上忘了不合法的break,妈的调了一个多小时简直是日了狗了!

本来就是蒟蒻还感冒了什么题都写不出来

 

/* ***********************************************Author        :devil************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <stack>#include <map>#include <string>#include <cmath>#include <stdlib.h>#define inf 0x3f3f3f3f#define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate<class T>inline void rd(T &x){char c=getchar();x=0;while(!isdigit(c))c=getchar();while(isdigit(c)){x=x*10+c-0;c=getchar();}}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int mod=1e9+7;const int N=310;LL dp[22][4];void init(){    dp[1][0]=1;    dp[1][2]=1;    for(int i=2;i<20;i++)    {        dp[i][0]=(dp[i-1][2]+dp[i-1][1])*5;        dp[i][1]=dp[i-1][0]*5;        dp[i][2]=(dp[i-1][1]+dp[i-1][3])*5;        dp[i][3]=dp[i-1][2]*5;    }}int bit[21];LL solve(LL n){    int len=0;    while(n)    {        bit[++len]=n%10;        n/=10;    }    bit[len+1]=0;    LL ans=0;    int tp=bit[len]/2;    ans=ans+dp[len][1]*tp;    if(bit[len]%2==0) tp--;    ans=ans+dp[len][2]*tp;    for(int i=len-1;i>=1;i--)    {        ans=ans+dp[i][1]*5;        ans=ans+dp[i][2]*4;    }    int now=bit[len]%2,ln=1;    for(int i=len-1;i>=1;i--)    {        if(now%2==1)        {            if(ln%2==1)            {                ans=ans+dp[i][0]*(bit[i]/2);                if(bit[i]%2) ln++;                else break;            }            else            {                int tp=bit[i]/2;                ans=ans+dp[i][1]*tp;                if(bit[i]%2!=0) tp++;                ans=ans+dp[i][2]*tp;                if(bit[i]%2) ln++;                else                {                    now=0;                    ln=1;                }            }        }        else        {            if(ln%2==1)            {                int tp=bit[i]/2;                ans=ans+dp[i][1]*tp;                if(bit[i]%2) tp++;                ans=ans+dp[i][3]*tp;                if(bit[i]%2)                {                    now=1;                    ln=1;                }                else ln++;            }            else            {                int tp=bit[i]/2;                if(bit[i]%2!=0) tp++;                ans=ans+dp[i][2]*tp;                if(bit[i]%2) break;                else ln++;            }        }    }    return ans;}int main(){    init();    int t,cas=0;    LL n,m;    rd(t);    while(t--)    {        scanf("%lld%lld",&n,&m);        printf("Case #%d: %lld\n",++cas,solve(m+1)-solve(n));    }    return 0;}

 

hdu5898 odd-even number(数位dp)