1009 数字1的数量 数位dp
1级算法题就这样了，前途渺茫啊。。。更新一下博客，我刚刚想套用数位dp的模板，发现用那个模板也是可以做到，而且比第二种方法简单很多第一种方法：我现在用dp[pos][now]来表示第pos位数字为now时数字1的数量，如果用数位dp的话，现在我们有三种情况第一种情况：now！=1，那我没什么好说的了...
数位DP GYM 100827 E Hill Number
题目链接题意：判断小于n的数字中，数位从高到低成上升再下降的趋势的数字的个数分析：简单的数位DP，保存前一位的数字，注意临界点的处理，都是套路。#include<bits/stdc++.h>typedeflonglongll;constintN=70+5;charstr[N];lldp[...
HDU2089 不要62[数位DP]
不要62TimeLimit:1000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):36862 AcceptedSubmission(s):13418ProblemDescripti...
数位DP之奥义
恩是的没错数位DP的奥义就是一个简练的dfs模板intdfs(intposition,intcondition,boolboundary){if(position<)return(condition?);if(condition<)return;if(!boundary&&...
数位dp总结
由简单到稍微难点。从网上搜了10到数位dp的题目，有几道还是很难想到的，前几道基本都是模板题，供入门用。点开即可看题解。hdu3555Bombhdu3652B-numberhdu2089不要62hdu4734F(x)hdu4389Xmodf(x)ural1057AmountofDegreeshdu4...
数位DP入门
HDU2089 不要62DESC:问l,r范围内的没有4和相邻62的数有多少个。#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>usingnamespace...
浅谈数位DP
在了解数位dp之前，先来看一个问题：例1.求a~b中不包含49的数的个数.0<a、b<2*10^9注意到n的数据范围非常大，暴力求解是不可能的，考虑dp,如果直接记录下数字，数组会开不起，该怎么办呢？要用到数位dp.数位dp一般应用于：求出在给定区间[A,B]内，符合条件P(i)的数i的...
BZOJ1799 self 同类分布 数位dp
BZOJ1799self同类分布去博客园看该题解题意给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。【约束条件】1≤a≤b≤10^18题解1.所有的位数之和<9*18=1622.所以，dp[i][j][k][m]表示有i位（允许有前导0），数位和为k，模数为m，前i位与模数的模为...
P2657 [SCOI2009]windy数 （数位DP）
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintINF=2e9;intdp[15][15];intmaxNu...
BZOJ3598[Scoi2014]方伯伯的商场之旅 数位DP
看到数据范围很容易想到数位DP然后就很容易想到枚举每一位作为最优点我们可以发现对于一个数字如果他的最优点确定了那离最优点越远花费越高我们可以先将所有的数字全合并到第一个点(用数位DP求)然后依次枚举从i->i+1更优的数字有多少个在这里我们只需要求出他对答案的贡献即可从i->i+1前i位...
bzoj3598: [Scoi2014]方伯伯的商场之旅【数位dp】
Description方伯伯有一天去参加一个商场举办的游戏。商场派了一些工作人员排成一行。每个人面前有几堆石子。说来也巧，位置在i的人面前的第j堆的石子的数量，刚好是i写成K进制后的第j位。现在方伯伯要玩一个游戏，商场会给方伯伯两个整数L,R。方伯伯要把位置在[L,R]中的每个人的石子都合并成一堆石...
【BZOJ1026】windy数，数位DP
Time:2016.08.14Author:xiaoyimi转载注明出处谢谢思路：依旧蛋疼的数位DPf[i][j]表示有i位，且最高位为j的windy数个数转移方程比较好写关键是具体求值的时候不太好弄从小位往高位求cal(i)实际上算出的是1~i-1的windy数所以判断一下i是否为windy数就可...
[BZOJ3598][SCOI2014]方伯伯的商场之旅(数位DP,记忆化搜索)
3598:[Scoi2014]方伯伯的商场之旅TimeLimit:30Sec MemoryLimit:64MBSubmit:449 Solved:254[Submit][Status][Discuss]Description方伯伯有一天去参加一个商场举办的游戏。商场派了一些工作人员排成一行。每个...
LightOJ1068 Investigation（数位DP）
这题要求区间有多少个模K且各位数之和模K都等于0的数字。注意到[1,231]这些数最大的各位数之和不会超过90左右，而如果K大于90那么模K的结果肯定不是0，因此K大于90就没有解。考虑到数据规模，数据组数，这题状态这么表示：dp[i][j][k]：位数为i模K结果为j且各位数之和模K结果为k的数字...
数位DP 求K进制下0~N的每个数每位上出现的数的总和
好久没写博客了，因为感觉时间比较紧，另一方面没有心思，做的题目比较浅也是另一方面。热身赛第二场被血虐了好不好，于是决定看看数位DP吧。进入正题：如题是一道经（简）典（单）的数位dp。第一步，对于数K^n-1这种形式的数，位数为n，它的各个位上，每个数0~K-1出现过的次数是一样的。于是对于数B=K^...
【BZOJ1662】[Usaco2006 Nov]Round Numbers 圆环数 数位DP
【BZOJ1662】[Usaco2006Nov]RoundNumbers圆环数Description正如你所知，奶牛们没有手指以至于不能玩“石头剪刀布”来任意地决定例如谁先挤奶的顺序。她们甚至也不能通过仍硬币的方式。所以她们通过"roundnumber"竞赛的方式。第一头牛选取一个整数，小于20亿。...
[BZOJ 1833] [ZJOI2010] count 数字计数 【数位DP】
题目链接：BZOJ-1833题目分析数位DP..用f[i][j][k]表示第i位是j的i位数共有多少个数码k。然后差分询问...Get()中注意一下，如果固定了第i位，这一位是t，那么数码t的答案是要加一个值的（见代码）。代码#include<iostream>#include<c...
Ural1057 - Amount of Degrees(数位DP)
题目大意求给定区间[X,Y]中满足下列条件的整数个数：这个数恰好等于K个互不相等的B的整数次幂之和。例如，设X=15，Y=20，K=2，B=2，则有且仅有下列三个数满足题意：输入：第一行包含两个整数X和Y。接下来两行包含整数K和B。输出：只包含一个整数，表示满足条件的数的个数。数据规模：1≤X≤Y≤...
ural 1057 Amount of degrees 【数位dp】
题意：求（x--y）区间转化为c进制1的个数为k的数的出现次数。分析：发现其满足区间减法，所以能够求直接求0---x的转化为c进制中1的个数为k的数的出现次数。首先用一个数组f【i】【j】：表示前i位中有j位为1的个数。能够通过方程f【i】【j】=f【i-1】【j】+f【i-1】【j-1】来预处理出...
URAL 1057. Amount of Degrees(数位DP)
题目链接我看错题了。。。都是泪啊，不存在3*4^2这种情况。。。系数必须为1。。。#include<cstdio>#include<cstring>#include<iostream>#include<vector>usingnamespacestd;...