精华内容
下载资源
问答
  • 和 hdu 3555 Bomb相差不大,就是了一个要整除的条件,那就在再添加一个状态来标记是否能被13整除。然后数位dp即可。 不过在转移状态的时候,我搞错了 参考:...

    求1-n内,包含13且能够被13整除的数字的个数。
    和 hdu 3555 Bomb相差不大,就是多了一个要整除的条件,那就再添加一个状态来标记是否能被13整除。然后数位dp即可。
    不过在转移状态的时候,我搞错了这里写图片描述
    参考:http://blog.csdn.net/libin56842/article/details/10026063

    #include <bits/stdc++.h>
    using namespace std;
    
    int dp[15][15][3];
    int digit[11];
    int len;
    
    void calc(int num)
    {
        len = 0;
        while(num)
        {
            digit[len++] = num%10;
            num /= 10;
        }
    }
    
    int dfs(int i, int mod, int s, bool e)
    {
        if(i == -1) return mod==0&&s==2;
        if(!e && ~dp[i][mod][s]) return dp[i][mod][s];
        int res = 0;
        int u = e?digit[i]:9;
        for(int d = 0; d <= u; ++d)
        {
            int _mod = (mod*10+d)%13;
            int _s = s;
            if(s == 0 && d == 1)
                _s = 1;
            if(s == 1 && d != 1)
                _s = 0;
            if(s == 1 && d == 3)
                _s = 2;
            res += dfs(i-1,_mod,_s,e&&d==u);
        }
        return e?res:dp[i][mod][s]=res;
    }
    
    int solve(int num)
    {
        calc(num);
        return dfs(len-1,0,0,true);
    }
    
    int main()
    {
        int n;
        memset(dp,-1,sizeof(dp));
        while(scanf("%d",&n) != EOF)
            printf("%d\n",solve(n));
        return 0;
    }
    
    展开全文
  • 找出1~n范围内含有13并且能被13整除的数字的个数 Input 组输入,每组用例占一行为一个整数n,以文件尾结束输入 Output 对于每组用例,输出1~n中含有13并能被13整数的数字个 Sample Input 13 100 200 ...

    Description
    找出1~n范围内含有13并且能被13整除的数字的个数
    Input
    多组输入,每组用例占一行为一个整数n,以文件尾结束输入
    Output
    对于每组用例,输出1~n中含有13并能被13整数的数字个数
    Sample Input
    13
    100
    200
    1000
    Sample Output
    1
    1
    2
    2
    Solution
    数位DP,以dp[len][mod][sure][state]表示到第len位的数模13的余数为mod(sure是否含13,state表示当前位是不是1)时满足条件的数字个数
    Code

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    using namespace std;
    typedef long long ll;
    int dp[15][15][2][2];
    int num[15];
    int a;
    int dfs(int len,int mod,bool sure,bool state,bool fp)//len表示当前位置,mod表示当前的数模13的余数,sure表示当前的数是否含有13,state表示当前位是不是1 
    {
        if(len<0)
            return sure==true&&mod==0;
        if(!fp&&dp[len][mod][sure][state]!=-1)
            return dp[len][mod][sure][state];
        int ret=0;
        int fpmax=fp?num[len]:9;
        for(int i=0;i<=fpmax;i++)
            ret+=dfs(len-1,(mod*10+i)%13,sure||state&&i==3,i==1,fp&&i==fpmax);
        if(!fp)
            dp[len][mod][sure][state]=ret;
        return ret;
    }
    int f(int x)
    {
        int len=0;
        while(x)
        {
            num[len++]=x%10;
            x/=10;
        }
        return dfs(len-1,0,0,0,true);
    }
    int main()
    {
        memset(dp,-1,sizeof(dp));//初始化 
        while(scanf("%d",&a)!=EOF)
            printf("%d\n",f(a));
        return 0;
    }
    展开全文
  • = 1e9),问你n内有多少个含有‘13’且能被13整除。 思路: dp[pos][sum][ind]。一维表示从左至右的第pos。二维sum表示前pos前缀模13的值。三维ind,ind = 0表示前pos前缀中没有出现’13’、且pos -...

    B-number HDU - 3652

    题意:
    多次询问,每次询问给你一个数n(1 <= n <= 1e9),问你n内有多少个数含有‘13’且能被13整除。

    思路:

    • dp[pos][sum][ind]。一维表示数从左至右的第pos位。二维sum表示前pos位前缀数模13的值。三维ind,ind = 0表示前pos位前缀数中没有出现’13’、且pos - 1位的数不为1,ind = 1表示前pos位前缀数中没有出现’13’、且pos - 1位的数为1,ind = 2表示前pos位前缀数中出现了’13’。

    • 转移式类似于不要62,区别只是多了一个模13是否为0的判断条件。

    code:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int mod = 13;
    int dp[20][20][3];
    int head[20];
    int dfs(int pos, int sum, int ind, bool limit) {
    	if(pos == -1){
    		if(ind == 2 && sum % mod == 0) return 1; //该数出现了'13'且可以被13整除
    		else return 0;
    	}
    	if(!limit && dp[pos][sum][ind] != -1) return dp[pos][sum][ind];
    	 
    	int max_digit = limit ? head[pos] : 9;
    	int ans = 0;
    	for(int i = 0; i <= max_digit; i++){
    		if(i == 1) ans += dfs(pos - 1, (sum * 10 + i) % 13, ind == 2 ? 2 : 1, limit && i == max_digit);			
    		else if(i == 3) ans += dfs(pos - 1, (sum * 10 + i) % 13, (ind == 2 || ind == 1) ? 2 : 0, limit && i == max_digit);
    	         else ans += dfs(pos - 1, (sum * 10 + i) % 13, ind == 2 ? 2 : 0, limit && i == max_digit);
    	}
    	if(!limit) dp[pos][sum][ind] = ans;
    	return ans;
    } 
    
    int solve(int l){
    	int cot = 0;
    	while(l){
    		head[cot++] = l % 10;
    		l /= 10;
    	}
    	memset(dp, -1, sizeof(dp));
    	return dfs(cot - 1, 0, 0, true);
    }
    int main(){
    	int n;
    	while(~scanf("%d", &n)){
    		printf("%d\n", solve(n));
    	} 
    	
    }
    
    展开全文
  • HDU 3652 B-number 数位dp

    2019-06-29 12:33:13
    给你一个n 找出1~n 里 能被13整除并且包含“13”的的个数 数位dp 不说 模板改改dfs函数就行 dp[i][j][k] 三个分别代表,第i模为j state为k 解释下state:2为前面已经有13了 1为上一是1,0是上一不是1 #...

    给你一个数n 找出1~n 里 能被13整除并且包含“13”的数的个数
    数位dp 不多说 模板改改dfs函数就行

    dp[i][j][k] 三个分别代表,第i位模为j state为k 解释下state:2为前面已经有13了 1为上一位是1,0是上一位不是1

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #define ll long long
    using namespace std;
    ll a[20],dp[20][15][5];
    ll dfs(int pos,int mod,int state,bool limit)
    {
    	if(pos== 0) //遍历到最后一位 并且能被13整除 并且数字中含有“13” 
    		return mod== 0 &&state== 2;
    	if(!limit&&dp[pos][mod][state]!=-1)
    		return dp[pos][mod][state];
    	int up=limit?a[pos]:9;
    	ll cnt=0;
    	for(int i=0;i<=up;i++)
    	{
    		int temp_state=state;
    		if(temp_state!=2)//如果之前没出现过13,就进这里 出现过就一直是2
    		{
    			if(temp_state== 1)//如果上一位是1 这一位是3 就代表就13了 state为2 如果上一位是1这一位不是3了 就没有1了 所以state是0
    			{
    				if(i== 3)
    					temp_state=2;
    				else if(i!=1)
    					temp_state=0;
    			}
    			if(temp_state== 0&&i== 1)
    				temp_state=1;
    		}
    		cnt+=dfs(pos-1,(mod*10+i)%13,temp_state,limit&&i==up);
    	}
    	if(!limit)
    		dp[pos][mod][state]=cnt;
    	return cnt;
    }
    ll solve(ll x)
    {
    	int k=0;
    	while(x)
    	{
    		int temp=x%10;
    		x/=10;
    		a[++k]=temp;
    	}
    	return dfs(k,0,0,1);
    }
    int main()
    {
    	ll n;
    	while(cin>>n)
    	{
    		memset(dp,-1,sizeof(dp));
    		cout<<solve(n)<<endl;
    	}
    }
    
    展开全文
  • 求[1,n]中,数位表示中包含"13"子串,且数字能被13整除的数量 题解 其实就是 不要62 那道题的思想,感觉一年终于把其理解透彻了 万一哪天忘了呢,总结一下吧,dp[i][j][k]表示当前第i 状态为j 当前%13...
  • 求1到n之间含有13且能被13整除的个数。 解题思路: 就是“不要49”的加强版,在设置状态时需要多用一维,用于判断是否整除13。很容易的可以想到,出来的一维可以表示当前除以13的余数。 这样状态设置:dp[pos]...
  • 前言 本来写的超级超级繁琐,可是被csdn搞了,...如求不含4的的个数,含13且能被13整除的个数,区间内所有数码的出现次数等。 解法 首先这样的题一般满足前缀性质,即[l,r]内的答案可以变为[1,r]-[...
  • 幸运

    2017-12-25 19:53:01
    北方的小红红就不太喜欢“7”这个数字,她认为如果一个正整数能被7整除,或者这个的某一有7,这个就不是一个吉利的。比如71,十上有7这个数字,所以71是不吉利数字。再比如14能被7整除,14也不是吉利数字...
  • 幸运--打表

    2018-01-15 20:26:12
    北方的小红红就不太喜欢“7”这个数字,她认为如果一个正整数能被7整除,或者这个的某一有7,这个就不是一个吉利的。比如71,十上有7这个数字,所以71是不吉利数字。再比如14能被7整除,14也不是吉利数字...
  • HDU 3652 B-number

    2011-08-07 16:52:53
    困在能被13整除上了,查了能被13整除的特性,不知道怎么转化dp... 后来看了解题报告,状态上记录个模13的余数就好了~ #include #include #include int ans; int num[10], ln; int f[10][13][3]; ...
  • 程序分析:判断素数的方法:用一个分别去除2到sqrt(这个),如果能被整除, 则表明此不是素数,反之是素数。  【程序15】  题目:打印出如下图案(菱形)  *  ***  ******  ********  ******  ***  * ...
  • 13.求整数[2335,4321]之间即不能被3整除,又不能被5整除的奇数的个数。(530) Private Sub Command1_Click() Dim i As Integer, n As Integer n = 0 For i = 2335 To 4321 Step 2 If Then n = n + 1 End ...
  • 一亿以内的回文素数

    千次阅读 2015-05-12 14:54:00
    题意分析:求1~100000000内的回文...2.偶数的回文能被11整除,自己证明去。所以,偶数的回文除了11都是合数。 3.一个k位数,可以构造出一个奇数的回文。比如13,可以构造131;189可以构造18981.所以10
  • Java算法总结2010-09-20

    2010-11-27 12:54:55
    6.打印出500之内所有能被7或9整除*/ 7. * 编写一个Java程序 使它随即产生1800到2000之间的年份,打印它是否是一个闰年,闰年是1584年以后的年份,它要能被400整除, * 要能被4整除但是不能被100整除,已知使用Math....
  • 基于本程序的一些基本的c语法:  '%'为取余运算符,用于把它前面的整数值或表达式除以  其后面的整数值或表达式,结果为不能被后面的整数或表达  式整除的最小整数,它后面的数值应该为大于1的正整数。...
  • 1.程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除, 则表明此数不是素数,反之是素数。 【程序3】 题目:打印出所有的"水仙花数",所谓"水仙花数"是指一个三位数,其各位数字立方和...
  • 最小生成树.pptx

    2020-08-13 22:18:36
    素数又称质数,一个大于1的自然数,除了1和它本身外,不能被其他自然数整除,换句话说就是该除了1和它本身以外不再有其他的因数;否则称为合数。啊!1不是素数啊素数的判断啊,也耳熟能详了,暴力枚举一下除1和...
  • java 经典习题.doc

    2009-09-16 11:32:59
    1.程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除, 则表明此数不是素数,反之是素数。 【程序3】 题目:打印出所有的"水仙花数",所谓"水仙花数"是指一个三位数,其各位数字立方和...
  • C语言经典例题100道

    2011-01-10 13:14:03
    85.判断一个素数能被几个9整除 86.两个字符串连接程序 87.结构体变量传递 88.读取数字的整数值并打印出该值个的* 89.数据加密 90.专升本一题 91.时间函数举例1 92.时间函数举例2 93.时间函数举例3 94.一个猜数...
  • 这里EAN_13编码要求是13位长度的数字,并且满足:把所有偶数序号上的相加求和,用求出的和乘3,再把所有奇数序号上的相加求和,用求出的和加上刚才偶数序号上的,然后得出和能被10整除。(这个规则校验在...
  • 这里EAN_13编码要求是13位长度的数字,并且满足:把所有偶数序号上的相加求和,用求出的和乘3,再把所有奇数序号上的相加求和,用求出的和加上刚才偶数序号上的,然后得出和能被10整除。(这个规则校验在...
  • c++ 面试题 总结

    2009-09-16 08:44:40
    一个程序片断可能会分为几十段,这样很时间就会浪费在计算每一段的物理地址上(计算机最耗时间的大家都知道是I/O吧)。 段页式管理:结合了段式管理和页式管理的优点。把主存分为若干页,每一页又分为若干段...
  • C语言程序设计经典例子

    热门讨论 2009-05-22 20:08:27
    题目:打印出所有的“水仙花数”,所谓“水仙花数”是指一个三位数,其各位数字立方和等于该数  本身。例如:153是一个“水仙花数”,因为153=1的三次方+5的三次方+3的三次方。 1.程序分析:利用for循环控制100-...
  • javascript入门笔记

    2018-05-15 15:01:07
    反复使用 :可以被多次调用 代码块 :包含条可执行的语句 2、函数的声明与调用 1、普通函数 语法: function 函数名(){ 语句块; } 调用:在JS中任何的合法位置处,都可以通过 函数名() 的方式进行调用 ...
  • 达内 coreJava 习题答案

    2010-02-10 19:49:01
    (1)若某个年份能被4整除但不能被100整除,则是闰年。 (2)若某个年份能被400整除,则也是闰年。 import java.util.Scanner; class Bissextile{ public static void main(String[] arge){ System.out.print(...
  • Proteus仿真—40个单片机初学程序.

    热门讨论 2009-04-13 13:00:56
    1. 闪烁灯 1. 实验任务 如图4.1.1所示:在P1.0端口上接一个发光二极管L1,使L1在不停地一亮一灭,一亮一灭的时间间隔为0.2秒。...如图13所示,利用AT89S51单片机的P0端口的P0.0-P0.7连接到一个共阴数码管...
  • Java开发技术大全(500个源代码).

    热门讨论 2012-12-02 19:55:48
    notMultipleOfThree.java 把100-200之间不能被3整除输出 outputByDoWhile.java 用while循环随机输出数据 outputByWhile.java 用do~while循环随机输出数据 outputMax.java 求两个中的最大 ...
  • SuperNotepad

    2012-11-14 11:23:53
    8的二进制1000应为01000(符号省)) 08) 多种替换|转换功能 (注:支持批量\par\tab\asc\nul) 09) 状态栏便捷查看文本编码方式、文件路径、字符的各种信息 例︰字体|大小|颜色|...|编码 10) 浏览...
  • delphi 开发经验技巧宝典源码

    热门讨论 2010-08-12 16:47:23
    0128 使用ExceptAddr函数获得异常抛出的地址 83 0129 格式化异常处理信息 84 4.8 图形图像相关函数 85 0130 将TColor类型的颜色值转换为RGB值 85 0131 使用Bounds函数获得某矩形的TRect 86 0132 从已有...
  • 0128 使用ExceptAddr函数获得异常抛出的地址 83 0129 格式化异常处理信息 84 4.8 图形图像相关函数 85 0130 将TColor类型的颜色值转换为RGB值 85 0131 使用Bounds函数获得某矩形的TRect 86 0132 从已有...

空空如也

空空如也

1 2
收藏数 36
精华内容 14
关键字:

多位数能被13整除