首页 > 代码库 > BZOJ 4521 CQOI 2016 手机号码 数位DP
BZOJ 4521 CQOI 2016 手机号码 数位DP
4521: [Cqoi2016]手机号码
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 539 Solved: 325
[Submit][Status][Discuss]
Description
人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不
吉利的数字等。手机运营商在发行新号码时也会考虑这些因素,从号段中选取含有某些特征的号
码单独出售。为了便于前期规划,运营商希望开发一个工具来自动统计号段中满足特征的号码数
量。
工具需要检测的号码特征有两个:号码中要出现至少3个相邻的相同数字,号码中不能同
时出现8和4。号码必须同时包含两个特征才满足条件。满足条件的号码例如:13000988721、
23333333333、14444101000。而不满足条件的号码例如:1015400080、10010012022。
手机号码一定是11位数,前不含前导的0。工具接收两个数L和R,自动统计出[L,R]区间
内所有满足条件的号码数量。L和R也是11位的手机号码。
Input
输入文件内容只有一行,为空格分隔的2个正整数L,R。
10^10 < = L < = R < 10^11
Output
输出文件内容只有一行,为1个整数,表示满足条件的手机号数量。
Sample Input
12121284000 12121285550
Sample Output
5
样例解释
满足条件的号码: 12121285000、 12121285111、 12121285222、 12121285333、 12121285550
样例解释
满足条件的号码: 12121285000、 12121285111、 12121285222、 12121285333、 12121285550
HINT
Source
Solution
这是一道简单的数位DP,状态不难想:F[i][j][k1][k2][k3][k4][k5]。
表示做到第i位,放的数为j,最后连续两位是否相同,是否存在连续三位相同,是否出现过4,是否出现过8,前缀与原数前缀是否相同。
转移也是比较简单的,枚举上面的东西,再枚举第i+1位填什么,根据题意转移即可。
但是需要注意的是,初始化的时候需要弄一个第10位出来,否则判连续两位相同会比较伤。
而且一般情况下都是cal(r)-cal(l-1),如果固定11位来做的话就会出现问题,这时候可以用开区间来做,变成cal(r+1)-cal(l)。
Code
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <string> 5 #include <algorithm> 6 7 using namespace std; 8 9 #define FIO "a" 10 #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i) 11 #define mset(a, b) memset(a, b, sizeof(a)) 12 const int maxn = 15; 13 typedef long long LL; 14 LL f[maxn][maxn][2][2][2][2][2], l, r; 15 //×?μ?μúi??£?×?????ê?j£?×?oóá???êyê?·?á?D?£?ê?·?óDá?D?èy???àí?£?ê?·?óD4£?ê?·?óD8£??°×oó??-êy?°×oμ?1??μ 16 17 LL cal(LL x) 18 { 19 mset(f, 0); 20 LL ans = 0; int len = 0, digit[15], a, b, c, d, e; 21 while (x) { digit[++len] = x%10, x /= 10; } 22 reverse(digit+1, digit+len+1); 23 f[0][10][0][0][0][0][1] = 1; 24 REP(i, 0, len-1) 25 REP(j, 0, 10) 26 REP(k1, 0, 1) 27 REP(k2, 0, 1) 28 REP(k3, 0, 1) 29 REP(k4, 0, 1) 30 REP(k5, 0, 1) 31 if (f[i][j][k1][k2][k3][k4][k5]) 32 REP(k, 0, 9) 33 { 34 if (k5 && k > digit[i+1]) continue ; 35 if (k == j) a = 1; else a = 0; 36 if (!k2) b = (a+k1 == 2); else b = k2; 37 if (!k3) c = (k == 4); else c = k3; 38 if (!k4) d = (k == 8); else d = k4; 39 if (c+d == 2) continue ; 40 if (k5 && k == digit[i+1]) e = 1; else e = 0; 41 f[i+1][k][a][b][c][d][e] += f[i][j][k1][k2][k3][k4][k5]; 42 } 43 REP(j, 0, 9) 44 REP(k1, 0, 1) 45 REP(k3, 0, 1) 46 REP(k4, 0, 1) 47 { 48 if (k3 && k4) continue ; 49 ans += f[len][j][k1][1][k3][k4][0]; 50 } 51 return ans; 52 } 53 54 int main() 55 { 56 // freopen(FIO ".in", "r", stdin); 57 // freopen(FIO ".out", "w", stdout); 58 scanf("%lld %lld", &l, &r); 59 printf("%lld\n", cal(r+1)-cal(l)); 60 return 0; 61 }
BZOJ 4521 CQOI 2016 手机号码 数位DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。