题解"/>
Kuangbin 带你飞 数位DP题解
以前一直不知道该咋搞这个比较好。
感觉推起来那个数字好麻烦。后来有一种比较好的写法就是直接的DFS写法。相应的ismax表示当前位是否有限制。
数位DP也是有一种类似模版的东西，不过需要好好理解。与其他模版不同。
主要还是状态的定义
模版就不整理了。直接上题。
另外这里有一道题是数位DP+自动机的放到自动机里做
HDU 2089 不要62
基本的数位DP可以用来理解DFS写法
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 15;
int dp[MAXN][2];
int digit[MAXN],length;int calcu(int len,bool issix,bool ismax)
{if (len == 0) return 1;if (!ismax && dp[len][issix] != -1) return dp[len][issix];int limit = ismax ? digit[len] : 9;int tot = 0;for (int i = 0 ; i <= limit ; i++){if ((issix && i == 2) || i == 4 ) continue;tot += calcu(len - 1,i == 6 ,ismax && i == limit);}if (ismax) return tot;else return dp[len][issix] = tot;
}int slove(int x)
{int len = 0;int num = x;while (num){digit[++len] = num % 10;num /= 10;}return calcu(len,false,true);
}int main()
{memset(dp,-1,sizeof(dp));int l,r;while (scanf("%d%d",&l,&r) != EOF){if (l == 0 && r == 0) break;if (l > r) swap(l,r);printf("%d\n",slove(r) - slove(l - 1));}return 0;
} View Code HDU 3555 Bomb
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 30;
LL dp[MAXN][2];
int digit[MAXN];LL calcu(int length,bool isfour,bool ismax)
{if (length == 0) return 1;if (!ismax && dp[length][isfour] >= 0) return dp[length][isfour];LL tot = 0;int limit = ismax ? digit[length] : 9;for (int i = 0 ; i <= limit ; i++){if (isfour && i == 9) continue;tot += calcu(length - 1,i == 4,ismax && i == limit);}if (!ismax) return dp[length][isfour] = tot;return tot;
}LL slove(LL x)
{int len = 0;LL num = x;while (num){digit[++len] = num % 10;num /= 10;}return calcu(len,false,true);
}int main()
{int T,kase = 1;scanf("%d",&T);memset(dp,-1,sizeof(dp));while (T--){LL N;scanf("%I64d",&N);printf("%I64d\n",N - slove(N) + 1);}return 0;
} View Code POJ 3252 Round Numbers
统计二进制形式中0的个数比1的个数不小的数字的数目
很简单的只是进制变成了2进制，这里还要和下一个题目做一下比较。状态的定义不能想简单了
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 70;
LL dp[MAXN][MAXN][MAXN];
int digit[MAXN];LL calcu(int length,int preone,int prezero,bool zero,bool ismax)
{if (length == 0) return prezero >= preone;if (!ismax && dp[length][preone][prezero] >= 0) return dp[length][preone][prezero];LL tot = 0;int limit = ismax ? digit[length] : 1;for (int i = 0 ; i <= limit ; i++){int addone = 0,addzero = 0;if (i == 1) addone = 1;if (i == 0) addzero = 1;tot += calcu(length - 1,preone +addone,(zero && i == 0) ? 0 : prezero + addzero, zero && i == 0 ,ismax && i == limit);}if (!ismax) return dp[length][preone][prezero] = tot;return tot;
}LL slove(LL x)
{int len = 0;LL num = x;while (num){digit[++len] = num % 2;num >>= 1;}return calcu(len,0,0,true,true);
}int main()
{LL l,r;memset(dp,-1,sizeof(dp));while (scanf("%I64d%I64d",&l,&r) != EOF){// printf("%I64d\n",slove(r));//printf("%I64d\n",slove(l - 1));//printf("%I64d\n",slove(l));printf("%I64d\n",slove(r) - slove(l - 1));}return 0;
} View Code Spoj BAlnum BALNUM - Balanced Numbers
这个题题意是统计十进制形式中奇数出现偶数次，偶数出现奇数次的数字 个数
为什么这道题状态不能向前边那个题，直接dp[i][j][k]第i位出现j个奇数k个偶数然后直接推，
看起来很简单，然而这个状态是错的。为什么？考虑dp[5][3][2]，他究竟表示什么。
可以在记忆花过程中直接返回这个值么？13522后边若干位和14688后边若干位都是这个dp状态！！
所以上述状态是错的。正确的是三进制状压。表示每个数字出现的次数的状态0，1，2
具体看代码
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 30;
const int MAXD = 60010;
LL dp[MAXN][MAXD];
int digit[MAXN];
//order : 9 8 7 6 5 4 3 2 1 0;
//num: 0 1 2 3 4 5 6 7 8 9
//sta : 0 no 1 odd 2 evenbool judge(int sta)
{int num[15];for (int i = 0 ; i < 10 ; i++){num[i] = sta % 3;sta /= 3;}for (int i = 0 ; i < 10 ; i++){if (num[i] != 0){if (i % 2 == 0 && num[i] == 2) return false;if (i % 2 == 1 && num[i] == 1) return false;}}return true;
}int getsta(int x,int sta)
{int num[15];for (int i = 0 ; i < 10 ; i++){num[i] = sta % 3;sta /= 3;}if (num[x] == 0) num[x] = 1;else num[x] = 3 - num[x];int ret = 0;for (int i = 9 ; i >= 0 ; i--)ret = ret * 3 + num[i];return ret;
}LL calcu(int length,int presta,bool zero,bool ismax)
{if (length == 0) return judge(presta);if (!ismax && dp[length][presta] >= 0) return dp[length][presta];int limit = ismax ? digit[length] : 9;LL ret = 0;for (int i = 0 ; i <= limit ; i++){ret += calcu(length - 1,(zero && i == 0) ? 0 : getsta(i,presta),zero && i == 0,ismax && i == limit);}if (!ismax) return dp[length][presta] = ret;return ret;
}LL slove(LL x)
{LL num = x;int len = 0;while (num){digit[++len] = num % 10;num /= 10;}return calcu(len,0,true,true);
}int main()
{int T;memset(dp,-1,sizeof(dp));scanf("%d",&T);while (T--){LL l,r;scanf("%lld%lld",&l,&r);//cout << slove(r) << endl;printf("%lld\n",slove(r) - slove(l - 1));}return 0;
} View Code
Codeforces 55D Beautiful numbers
判断数字是否能整除他的十进制形式中所有非0数字的个数
注意到能整除所有位数实际上就是能整除这些位数的LCM，最大就是2520
那么状态定义dp[i][j][k] = val表示到达第i位对2520的摸为多少，当前的LCM为多少
另外代码里对LCM进行了哈希
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
LL gcd(LL a, LL b) {return a % b == 0 ? b : gcd(b, a % b);}
LL lcm(LL a,LL b) {return a / gcd(a,b) * b;}
const int MAXN = 110;
const int MAXD = 2600;
const LL MOD = 2520;
LL dp[30][MAXD][MAXN];
int digit[MAXN];
int Hash[MAXD];void init()
{int cas = 0;for (int i = 1 ; i <= MOD ; i++){if (MOD % i == 0)Hash[i] = ++cas;}
}LL calcu(int length,int premod,int prelcm,bool ismax)
{if (length == 0) return premod % prelcm == 0;if (!ismax && dp[length][premod][Hash[prelcm]] >= 0)return dp[length][premod][Hash[prelcm]];int limit = ismax ? digit[length] : 9;LL tot = 0;for (int i = 0 ; i <= limit ; i++){int nextmod = (premod * 10 + i) % MOD;int nextlcm;if (i == 0) nextlcm = prelcm;else nextlcm = lcm(prelcm,i);tot += calcu(length - 1,nextmod,nextlcm,ismax && i == limit);}if (ismax) return tot;else return dp[length][premod][Hash[prelcm]] = tot;
}LL slove(LL x)
{LL num = x,len = 0;while (num){digit[++len] = num % 10;num /= 10;}return calcu(len,0,1,true);
}int main()
{init();memset(dp,-1,sizeof(dp));int T;scanf("%d",&T);while (T--){LL l,r;scanf("%I64d%I64d",&l,&r);// cout << slove(r) << endl;printf("%I64d\n",slove(r) - slove(l - 1));}return 0;
} View Code HDU 3709 Balanced Number
一开始觉得好难。后来发现只需要枚举支点。复杂度并不会高多少。20而已
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
//此题枚举支点即可不用想麻烦了。
const int MAXN = 30;
LL dp[MAXN][MAXN][MAXN * 100];
int digit[MAXN];LL calcu(int length,int premid,int preval,bool ismax)
{if (length == 0) return preval == 0;if (preval < 0) return 0;if (!ismax && dp[length][premid][preval] >= 0) return dp[length][premid][preval];LL tot = 0;int limit = ismax ? digit[length] : 9;for (int i = 0 ; i <= limit ; i++){int add = (length - premid) * i;int nextval = preval + add;tot += calcu(length - 1,premid,nextval,ismax && i == limit);}if (!ismax) return dp[length][premid][preval] = tot;return tot;
}LL slove(LL x)
{int len = 0;LL num = x;while (num){digit[++len] = num % 10;num /= 10;}LL ret = 0;for (int i = 1 ; i <= len ; i++)ret += calcu(len,i,0,true);return ret - len + 1;
}int main()
{memset(dp,-1,sizeof(dp));LL l,r;int T;scanf("%d",&T);while (T--){scanf("%I64d%I64d",&l,&r);printf("%I64d\n",slove(r) - slove(l - 1));}return 0;
} View Code HDU 3652 B-number
包含13且整除13的数字个数
为什么不能直接dp[i][0/1]表示到达第i位是否出现13？同前面错误状态的比较
代码
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 30;
LL dp[MAXN][5][20];
int digit[MAXN];LL calcu(int length,int presta,int premod,bool ismax)
{if (length == 0) return (presta == 2 && premod == 0);if (!ismax && dp[length][presta][premod] >= 0) return dp[length][presta][premod];LL tot = 0;int limit = ismax ? digit[length] : 9;for (int i = 0 ; i <= limit ; i++){int nextmod = (premod * 10 + i) % 13;int nextsta = presta;if (presta == 0 && i == 1) nextsta = 1;if (presta == 1 && i != 1) nextsta = 0;if (presta == 1 && i == 3) nextsta = 2;tot += calcu(length - 1,nextsta,nextmod,ismax && i == limit);}if (!ismax) return dp[length][presta][premod] = tot;return tot;
}LL slove(LL x)
{LL num = x;int len = 0;while (num){digit[++len] = num % 10;num /= 10;}return calcu(len,0,0,true);
}int main()
{memset(dp,-1,sizeof(dp));LL N;while (scanf("%I64d",&N) != EOF){printf("%I64d\n",slove(N));}return 0;
} View Code HDU 4352 XHXJ's LIS
统计数字表示中LIS==K的数字的个数
这题状压+数位DP
觉得好厉害。为什么状压。考虑nlognLIS是怎么做的。这里的数字只能是0-9
所以状压。举个例子 1 2 4 6 是g数组,LIS = 4，现在来了个5.G数组变成 1 2 4 5 LIS仍然等于4
考虑好NLOGN LIS 怎么来的。注意前导0和0！
然后数位DP
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 30;
LL dp[MAXN][(1 << 10) + 50][15];
LL L,R,K;
int digit[MAXN];int getsta(int x,int s)
{for (int i = x ; i < 10 ; i++){if (s & (1 << i)){return (s ^ (1 << i)) | (1 << x);}}return s | (1 << x);
}int getnum(int x)
{int ret = 0;while (x){if (x & 1) ret++;x >>= 1;}return ret;
}LL calcu(int length,int presta,bool prezero,bool ismax)
{if (length == 0) return getnum(presta) == K;if (!ismax && dp[length][presta][K] >= 0) return dp[length][presta][K];LL tot = 0;int limit = ismax ? digit[length] : 9;for (int i = 0 ; i <= limit ; i++){tot += calcu(length - 1,(i == 0 && prezero) ? 0 : getsta(i,presta),i == 0 && prezero,ismax && i == limit);}if (ismax) return tot;else return dp[length][presta][K] = tot;
}LL slove(LL x)
{int len = 0;LL num = x;while (num){digit[++len] = num % 10;num /= 10;}return calcu(len,0,true,true);
}int main()
{int T,kase = 1;memset(dp,-1,sizeof(dp));scanf("%d",&T);while (T--){scanf("%I64d%I64d%I64d",&L,&R,&K);printf("Case #%d: %I64d\n",kase++,slove(R) - slove(L - 1));}return 0;
} View Code HDU 4734 f(x)
数位DP的一维状态表示差值即可
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL int
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 15;
const int MAXD = 100010;
LL dp[20][MAXD];
int digit[MAXN];
LL val,A,B;LL calcu(int length,int preval,bool ismax)
{if (length == 0) return preval >= 0;if (preval < 0) return 0;if (!ismax && dp[length][preval] >= 0) return dp[length][preval];LL tot = 0;int limit = ismax ? digit[length] : 9;for (int i = 0 ; i <= limit ; i++){tot += calcu(length - 1,preval - (1 << (length - 1)) * i,ismax && i == limit);}if (!ismax) return dp[length][preval] = tot;return tot;
}int f(int x)
{int ret = 0,cas = 0;while (x){ret += (x % 10) * (1 << cas);cas++;x /= 10;}return ret;
}LL slove()
{int len = 0;LL num = B;while (num){digit[++len] = num % 10;num /= 10;}return calcu(len,f(A),true);
}int main()
{memset(dp,-1,sizeof(dp));int T,kase = 1;scanf("%d",&T);while (T--){scanf("%d%d",&A,&B);printf("Case #%d: %d\n",kase++,slove());}return 0;
} View Code HDU 4507
主要是要求的不是数字个数。而是平方和。
那么可能久有点问题了
怎么做考虑(a + b1) ^ 2 + (a + b2) ^ 2 + .... 等于
a^2 * n + b1^ 2 + b2 ^ 2 + ..bn ^ 2 + 2 * a * (b1 + b2 +... bn)
上式实际上就是比如枚举到第3为a就1000，递归的找到b然后推即可
于是dp有三个值。数字个数。一次方和，二次方和
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 25;
const int MOD = 1e9 + 7;
LL fac[20];
typedef pair<int,pair<LL,LL> >PII;
PII dp[MAXN][10][10][2];
int digit[MAXN];
bool vis[MAXN][10][10][2];PII calcu(int length,int presum,int remain,bool contain,bool ismax)
{if (length == 0){if (!contain && presum && remain)return make_pair(1,make_pair(0LL,0LL));else return make_pair(0,make_pair(0LL,0LL));}if (!ismax && vis[length][presum][remain][contain])return dp[length][presum][remain][contain];PII ret = make_pair(0,make_pair(0LL,0LL));int limit = ismax ? digit[length] : 9;for (int i = 0 ; i <= limit ; i++){PII nxt = calcu(length - 1,(presum + i) % 7,(remain * 10 + i) % 7,contain || (i == 7),ismax && i == limit);LL preval = (LL)i * fac[length - 1] % MOD;ret.first = (ret.first + nxt.first) % MOD;ret.second.first = (ret.second.first + nxt.second.first + preval * nxt.first) % MOD;ret.second.second = (ret.second.second + nxt.second.second + 2 * preval * nxt.second.first % MOD+ preval * preval % MOD * nxt.first) % MOD;}if(!ismax){vis[length][presum][remain][contain] = true;dp[length][presum][remain][contain] = ret;return ret;}return ret;
}LL slove(LL x)
{int len = 0;LL num = x;while(num){digit[++len] = num % 10;num /= 10;}return calcu(len,0,0,0,true).second.second;
}int main()
{fac[0] = 1;for (int i = 1 ; i < 20 ; i++) fac[i] = fac[i - 1] * 10 % MOD;int T;memset(vis,false,sizeof(vis));scanf("%d",&T);while (T--){LL l,r;scanf("%I64d%I64d",&l,&r);printf("%I64d\n",(slove(r) - slove(l - 1) + MOD) % MOD);}return 0;
} View Code BCD CODE 放到自动机专题里在做
转载于:.html
更多推荐
Kuangbin 带你飞 数位DP题解
发布评论