2016 ShenYang regional online 1007||hdu 5898 odd-even number (数位dp)

Posted by 111qqz on Sunday, September 18, 2016

TOC

题目链接

题意:题意说得一点页不清楚。。。意思在询问在区间[l,r]中满足某条件的数。该条件是,该数的任何一段数字是奇数组成的数串必须有偶数长度,任何一段数字是偶数组成的数串必须由奇数长度。

对于样例1,满足条件的29个数字分别是: 2,4,6,8,11,13,15,17,19,31,33,35,37,39,51,53,55,57,59,71,73,75,77,79,91,93,95,97,99.

对于样例2,满足条件的36的数字分别是:

110,112,114,116,118,

130,132,134,136,138

150,152,154,156,158

170,172,174,176,178

190,192,194,196,198

200,202,204,206,208,220

211,213,215,217,219

思路:数位dp.dp[i][j][k]表示长度为i,奇偶性相同的连续由j个,上一个的奇偶性为k.

注意不允许前导0.

其他就是细节了,太久没写数位dp调了好久啊QAQ

/* ***********************************************
Author :111qqz
Created Time :Sun 18 Sep 2016 01:11:37 PM CST
File Name :code/net/2016/shenyang/1007.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
int digit[40];
LL dp2[30][30][5];
LL dfs2(int pos,int cnt,int lst,bool limit,bool prehasnonzero)
{
    if (pos==0)
    {
    if (lst==1&&cnt%2==0) return 1;
       if (lst==2&&cnt%2==1) return 1;
    return 0;
    }
    if (prehasnonzero&&!limit&&dp2[pos][cnt][lst]!=-1) return dp2[pos][cnt][lst];
    int mx = limit?digit[pos]:9;
    LL res = 0 ;
    if (!prehasnonzero)
    {
    for ( int i = 0 ; i <= mx ; i++)
    {
        res+=dfs2(pos-1,i==0?0:1,i==0?0:2-i%2,limit&&i==mx,i==0?false:true);
    }
    }
    else
    {
    for ( int i = 0 ; i <= mx ; i++)
    {
       if (lst==1&&cnt>0&&cnt%2==0&&i%2==1&&pos==1) continue;
        if (lst==1&&cnt%2==1&&i%2==0) continue;
        if (lst==2&&cnt>0&&cnt%2==0&&i%2==1) continue;
        if (lst==2&&cnt%2==1&&i%2==0&&pos==1) continue;
        res+=dfs2(pos-1,((i%2==1&&lst==1)||(i%2==0&&lst==2))?cnt+1:1,2-i%2,limit&&i==mx,true);
    }
    }
    if (prehasnonzero&&!limit) dp2[pos][cnt][lst] = res;
    return res;
}
/*
LL dfs( int pos,int odd,int even,int lst,bool limit, bool prehasnonzero)
{
    if (pos==0) return 1;
    if (prehasnonzero&&!limit&&dp[pos][odd][even][lst]!=-1) return dp[pos][odd][even][lst];
    int mx = limit?digit[pos]:9;
    LL res = 0;
    if (prehasnonzero)
    {
    for ( int i = 0 ; i <= mx ; i++)
    {
        if (lst==1)
        {
        if (odd%2==0&&i%2==1) continue;
        if (odd%2==1&&i%2==0) continue;
        }else if (lst==2)
        {
        if (even%2==1&&i%2==0) continue;
        if (even%2==0&&i%2==1) continue;
        }
        cout<<"pos:"<<pos<<" i:"<<i<<endl;
        res += dfs(pos-1,i%2==1?odd+1:0,i%2==0?even+1:0,i%2==0?2:1,limit&&i==mx,true);
    }
    }
    else
    {
    for ( int i = 0 ; i <= mx ; i++)
    {
        cout<<"pos::"<<pos<<"  i:"<<i<<endl;
        res += dfs(pos-1,i%2==1?1:0,i%2==0?1:0,0,limit&&i==mx,i==0?false:true);
    }
    }
    if (prehasnonzero&&!limit) dp[pos][odd][even][lst] = res;
    return res;
}  */
LL solve(LL n)
{
    ms(digit,0);
    int len = 0 ;
    while (n)
    {
    digit[++len] = n;
    n /= 10;
    }
    return dfs2(len,0,0,true,false);
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
    int T;
    cin>>T;
    ms(dp2,-1);
    int cas = 0 ;
    while (T--)
    {
        LL l,r;
        scanf("%lld%lld",&l,&r);
        LL ans = solve(r) - solve(l-1);
        printf("Case #%d: ",++cas);
        printf("%lld\n",ans);
    }
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付