不要62（HDU - 2089）
经典的数位dp的入门题。今天才知道原来这就可以做成一个板子。
题意：给你一个l和一个r，求[l,r]之间不存在4和连续62的数字的个数。
分析：直接说程序。
读入之后，把读入的数字按位放进digit数组之后，然后对digit数组进行操作。
DFS就是一个dp的过程，其中有三个状态，deep表示数字的第几位，flag表示当前这个数字是否为6，limit表示当前位数的数字。
#include<bits/stdc++.h>
#define ll long long
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
ll dp[10][2];
ll digit[10];
ll DFS(int deep,bool flag,bool limit)
{
if(deep==0) return 1; //此时访问完所有位数
if(!limit&&dp[deep][flag]!=-1) return dp[deep][flag]; //如果这个数字计算过就直接返回
ll ans=0;
int up=limit?digit[deep]:9; //如果传下来这是当前位数的最大值，那么up就是下一位数字（deep已经加一）
for(int i=0;i<=up;i++)
{
if(i==4) continue;
if(flag&&i==2) continue;
ans+=DFS(deep-1,i==6,limit&&i==up);
}
if(!limit) dp[deep][flag]=ans; //如果当前位是不是最大的那个数字，那么自然可以记录这个数字
return ans;
}
ll cal(ll num)
{
int k=0;
while(num)
{
digit[++k]=num%10;
num/=10;
}
return DFS(k,0,1);
}
void Solve()
{
ll n,m;
mem(dp,-1);
while(scanf("%lld%lld",&n,&m)!=EOF && (m + n)){
printf("%lld\n",cal(m)-cal(n-1));
}
}
int main()
{
//FILEIN
//FILEOUT
//std::ios::sync_with_stdio(false);
int Case=1,cases;
//scanf("%d", &Case); cases=Case;
while(Case--){
//printf("Case #%d:",cases-Case);
Solve();
}
return 0;
}
Character String（CodeForces - 55D）
题意：给你一个l和r，让你求[l,r]之间，能整除该数字每一位的 数字 的个数。
分析：嗯，数位dp。
本题注意两个点。1、2520为[1 9]的最小公倍数。有个很好理解的引理sum%(x*n)%x == sum%x;
2、状态的话除了第几位的位数，多了一个prelcm用于记录达到当前位数的最小公倍数。
#include<bits/stdc++.h>
#define ll long long
const int mod = 2520;
using namespace std;
ll dp[20][mod][50];
int digit[20];
int index[mod + 10];
ll gcd(ll a,ll b){
return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a,ll b){
return a / gcd(a,b) * b;
}
ll dfs(int deep,int presum,int prelcm,bool limit){
if(deep == 0) return presum % prelcm == 0;
if(!limit && dp[deep][presum][index[prelcm]] != -1){
return dp[deep][presum][index[prelcm]];
}
int up = limit ? digit[deep] : 9;
ll ans= 0;
for(int i = 0;i <= up ;i++){
int nowlcm = prelcm; //先继承，然后非0情况再求新的lcm
int nowsum = (presum * 10 + i) % mod; //当前在增一位
if(i) nowlcm = lcm(prelcm, i);
ans += dfs(deep - 1,nowsum, nowlcm, limit && i == up);
}
if(!limit) dp[deep][presum][index[prelcm]] = ans;
return ans;
}
ll Cal(ll num)
{
int k = 0;
while(num){
digit[++k] = num % 10;
num /= 10;
}
return dfs(k, 0, 1, 1);
}
//开2520是会爆，但是我们知道lcm必须要能够整除2520
void Init()
{
int num = 0;
for(int i = 1;i <= mod;i++){
if(mod % i == 0) index[i] = num++;
}
}
void Solve()
{
Init();
ll n;
ll a,b;
mem(dp,-1);
scanf("%I64d",&n);
for(ll i = 1;i <= n;i++){
scanf("%I64d%I64d",&a,&b);
printf("%I64d\n",Cal(b) - Cal(a-1));
}
}
int main()
{
//FILEIN
//FILEOUT
//std::ios::sync_with_stdio(false);
int Case=1,cases;
//scanf("%d", &Case); cases=Case;
while(Case--){
//printf("Case #%d:",cases-Case);
Solve();
}
return 0;
}
看懂了之后就会发现和 不要62 其实有惊人的相似！
