CQOI 手机号码

手机号码"/>

CQOI 手机号码

题意

给出 11 11 11位的手机号码，求出 [ L , R ] [L,R] [L,R]中有多少个符合条件的手机号码，必须出现连续三位相同，不能同时出现 8 8 8和 4 4 4，并且无前导零。

题解

做法很简单。
记录下是否有 8 8 8和 4 4 4，限制遍历，同时手机号码必须要 11 11 11位没有前导零，所以我们最高位从 1 1 1开始。套数位 d p dp dp模板即可。
注意 1 e 10 − 1 1e10-1 1e10−1是 9 9 9位数这是没有答案的。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;ll dp[20][2][2][2][20][25];
int num[20],tmp;ll dfs(int pos,int limit,int have8,int have4,int havev,int prepre,int pre){if(!pos)return havev==1;if(!limit&&dp[pos][have8][have4][havev][prepre][pre]!=-1)return dp[pos][have8][have4][havev][prepre][pre];int up=limit?num[pos]:9;ll ans=0;for(int i=(pos==tmp?1:0);i<=up;i++){if(have8&&i==4)continue;if(have4&&i==8)continue;ans+=dfs(pos-1,limit&&(i==num[pos]),have8||(i==8),have4||(i==4),havev||(i==pre&&prepre>=2),(i==pre?prepre+1:1),i);}if(!limit)dp[pos][have8][have4][havev][prepre][pre]=ans;return ans;
}
//10000000000
ll slove(ll x){memset(num,0,sizeof(num));tmp=0;if(!x)num[++tmp]=0;while(x){num[++tmp]=x%10;x/=10;}if(tmp<11)return 0;return dfs(tmp,1,0,0,0,10,10);
}int main(){memset(dp,-1,sizeof(dp));ll L,R;cin>>L>>R;cout<<slove(R)-slove(L-1)<<endl;
}