hdu 3652 B-number (带整除的数位dp )

Posted by 111qqz on Wednesday, March 16, 2016

TOC

题目链接
题意:给出n,问[1,n]中,满足包含“13”且这个数(不是各位的和)能被13整除的数的个数。
思路:依然是数位dp..不过有一个小tip。。

由于包含13的情况非常难考虑(包含一个“13”,两个“13”…..)

所以要从反面考虑,即不包含13的情况。

但是由于还有另一个条件。

做法是把能被13整除的数考虑成全集U,然后在U中做分划,一部分是含13的,另一部分是不含13的。

这样我们要求两个答案,一个是能被13整除的,另一个是能被13整除并且不含13的,相减即为题目所求。

/* ***********************************************
Author :111qqz
Created Time :2016年03月16日 星期三 09时27分49秒
File Name :code/hdu/3652.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;
LL n;
LL dp[20][15];
LL dp2[20][2][15];
int digit[20];


LL dfs (int pos,int sum,bool limit)
{
    if (pos==0) return sum==0;
    
    if (!limit&&dp[pos][sum]!=-1) return dp[pos][sum];

    int mx = limit ? digit[pos]:9;

    LL res = 0LL ;
    for ( int i = 0 ; i  <=  mx ; i++)
    {
    res+=dfs(pos-1,(sum*10+i),limit&&i==mx);
    }
    
    if(!limit) dp[pos][sum] = res;
    return res;
}
LL dfs2(int pos,bool preis1,int sum,bool limit)
{
    if (pos==0) return sum==0;

    if (!limit&&dp2[pos][preis1][sum]!=-1) return dp2[pos][preis1][sum];

    int mx = limit? digit[pos]:9;
    LL res = 0 ;
    for ( int i = 0 ; i <=  mx ; i++)
    {
    if (preis1&&i==3) continue;
    res+=dfs2(pos-1,i==1,(sum*10+i),limit&&i==mx);
    }

    if (!limit) dp2[pos][preis1][sum] = res;
    return res;
}

LL solve ( LL n)
{
    ms(digit,0);

    int len =  0;
    while (n)
    {
    digit[++len] = n;
    n/= 10;
    }
    return dfs(len,0,true)-dfs2(len,false,0,true); //在能被13整除的数里划分,减去不含“13”的,就是含“13”的。
                          //因为含“13”的情况太复杂了。。。
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
	
    ms(dp,-1); //dp数组子啊外面清空就好。。。。因为dp数组是所有数据公用的啊。。。。
    ms(dp2,-1);
    while (~scanf("%lld",&n))
    {
        LL ans = solve (n);
        printf("%lld\n",ans);
    }

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

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