首页 > 搜索 > DFS搜索 > HDU 3967-Zero’s Number-动态规划-[解题报告]HOJ
2015
04-14

HDU 3967-Zero’s Number-动态规划-[解题报告]HOJ

Zero’s Number

问题描述 :

Xnozero is very interested in k-divide number.

A way of k-divide on a number is defined as if number N can be divide into two parts m, n, and the sum of m and n can be divided by k, then this is a way of k-divide number based k.

For example, 3 + 33 = 36 is a way of 3-divide on number 333, as you can only divide 333 into 3 and 33, and the sum of 3 and 33 is 36, which can be divided by 3.

Zero’s number is defined as f(n,k), and f(n,k) is the number of ways of n divided into k-divide numbers.

As defined above, 333 can be divided into two parts in two ways 3|33 and 33|3, so f(333,3)=2.

Now give you A, B, K, can you help Xnozero compute the sum of f(i,K) (A≤i≤B)? (1 ≤ K ≤ 20, 10 ≤ A ≤ B ≤ 1017)

输入:

Multiple cases, process to the end of file.
Each line contains 3 integers A,B,K as descripted above.

输出:

Multiple cases, process to the end of file.
Each line contains 3 integers A,B,K as descripted above.

样例输入:

333 333 3
10 100 2

样例输出:

2
46

题意:对于两个数i和k,把它分为两个部分的数,n和m,如果(n+m)%k=0 那么这算一种分法

比如 333可分成,3、33或者33、3,对于 (333,3)就等于2.

现在给出 a、b、k,为 (a~b,k)有多少种分法

思路:对于一个数,注意前导零并枚举分点就好了。

 dp[22][22][22][22][2],   代表 i位,分点为fd,余数mod,对于k取余,是否有前导零

代码:

#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"stack"
#include"algorithm"
#include"iostream"
using namespace std;
__int64 dp[22][22][22][22][2],ten[22];  //i位,分点为fd,余数mod,对于k取余,是否有前导零
int num[22],cnt;
__int64 dfs(int site,int fd,int mod,int k,int ff,int f)
{
    if(site==0)  return mod?0:1;
    if(!f&&dp[site][fd][mod][k][ff]!=-1) return dp[site][fd][mod][k][ff];
    int len=f?num[site]:9;
    __int64 ans=0;
    for(int i=0; i<=len; i++)
    {
        if(site>fd)
        {
            if(ff==0&&site==fd+1&&i==0) continue; //前导0不能到分点前,也就是前半部分不能为0
            ans+=dfs(site-1,fd,(i*ten[site-fd]+mod)%k,k,ff||i!=0,f&&i==len);
        }
        else
            ans+=dfs(site-1,fd,(i*ten[site]+mod)%k,k,ff||i!=0,f&&i==len);
    }
    if(!f) dp[site][fd][mod][k][ff]=ans;
    return ans;
}
__int64 solve(__int64 x,int k)
{
    cnt=0;
    if(x<10) return 0;
    __int64 ans=0;
    while(x)
    {
        num[++cnt]=x%10;
        x/=10;
    }
    for(int i=1; i<cnt; i++)  //枚举分点 分界为这位之后
        ans+=dfs(cnt,i,0,k,0,1);
    return ans;
}
int main()
{
    __int64 a,b;
    int k;
    memset(dp,-1,sizeof(dp));
    ten[1]=1;
    for(int i=2; i<=18; i++) ten[i]=ten[i-1]*10;
    while(scanf("%I64d%I64d%d",&a,&b,&k)!=-1)
    {
        printf("%I64d\n",solve(b,k)-solve(a-1,k));
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/wdcjdtc/article/details/39344389


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  3. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }