首页 > 代码库 > [BZOJ 1833] [ZJOI2010] count 数字计数 【数位DP】
[BZOJ 1833] [ZJOI2010] count 数字计数 【数位DP】
题目链接：BZOJ - 1833
题目分析
数位DP ..
用 f[i][j][k] 表示第 i 位是 j 的 i 位数共有多少个数码 k 。
然后差分询问...Get()中注意一下，如果固定了第 i 位，这一位是 t ，那么数码 t 的答案是要加一个值的（见代码）。
代码
#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MaxBit = 15;typedef long long LL;struct ES{ LL A[11];};ES operator + (const ES &a, const ES &b) { ES ret; for (int i = 0; i <= 9; ++i) ret.A[i] = a.A[i] + b.A[i]; return ret;}LL A, B;LL P10[MaxBit]; ES f[MaxBit][11];ES Get(LL x) { ES ret; for (int i = 0; i <= 9; ++i) ret.A[i] = 0; if (x == 0) return ret; int l = 1; while (P10[l] <= x) ++l; for (int i = 1; i <= l - 1; ++i) { for (int j = 1; j <= 9; ++j) { ret = ret + f[i][j]; } } //0没有被统计 ++ret.A[0]; LL t; t = x / P10[l - 1]; x %= P10[l - 1]; //如果只有1位，下面这里也会不统计0，但是已经在上面补上了0 for (int i = 1; i <= t - 1; ++i) ret = ret + f[l][i]; ret.A[t] += x; for (int i = l - 1; i >= 1; --i) { t = x / P10[i - 1]; x %= P10[i - 1]; for (int j = 0; j <= t - 1; ++j) ret = ret + f[i][j]; ret.A[t] += x; } return ret;}int main() { P10[0] = 1ll; for (int i = 1; i <= 13; ++i) P10[i] = P10[i - 1] * 10ll; for (int i = 1; i <= 13; ++i) { for (int j = 0; j <= 9; ++j) { for (int k = 0; k <= 9; ++k) { f[i][j] = f[i][j] + f[i - 1][k]; } f[i][j].A[j] += P10[i - 1]; } } scanf("%lld%lld", &A, &B); ES TA, TB; TA = Get(A); TB = Get(B + 1); for (int i = 0; i <= 9; ++i) { printf("%lld", TB.A[i] - TA.A[i]); if (i == 9) printf("\n"); else printf(" "); } return 0;}
[BZOJ 1833] [ZJOI2010] count 数字计数 【数位DP】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。