P4124 [CQOI2016]手机号码

P4124 [CQOI2016]手机号码

#include <bits/stdc++.h>
#define int long long
using namespace std ;
int l , r , num[15] ;
int f[15][15][15][2][2][2][2] ;
int dfs(int p ,int a ,int b ,int c ,int d ,int _4 ,int _8 ) {
    //p位数,p+1位是a,p+2位是b,是否满足条件一,当前位数是否大于n,是否满足条件二 
    if(_4&&_8) return 0 ;//不合法贡献为0
    if(p <= 0) return c ;//如果位数枚举完了,如果有贡献就返回一,没有贡献就返回0
    if(~f[p][a][b][c][d][_4][_8]) return f[p][a][b][c][d][_4][_8] ;//返回贡献
    int res = 0 ;int lim = !d ? num[p] : 9 ;//如果当前位严格小于最高位,那就可以随便填,否则只能从num填
    for(int i = 0 ; i <= lim ; i ++) {
        res += dfs(p-1,i,a,c||(i==a&&i==b),d||(i<lim),_4||(i==4),_8||(i==8)) ;
    } 
    return f[p][a][b][c][d][_4][_8] = res ;
//  return res ;
}
int calc(int x) {
    if(x < 1e10) return  0 ;
    int len = 0 ;
    while(x) {
        num[++len] = x % 10 ;
        x /= 10 ;
    }
    memset(f,-1,sizeof(f)) ;
    int res = 0 ;
//  cout << len << endl ;
    for(int i = 1 ; i <= num[len] ; i ++) {
        res += dfs(10,i,0,0,i<num[len],i==4,i==8) ;
    }return res ;
}
signed main () {
    cin >> l >> r ;
    cout << calc(r) - calc(l-1) << endl ; 
    return 0 ;
}

P4124 [CQOI2016]手机号码

上一篇:Android scrollTo() scrollBy() Scroller讲解及应用


下一篇:基于appium实现的线性代码引用unittest单元测试框架