首页 > 代码库 > 【BZOJ4521】【CQOI2016】手机号码
【BZOJ4521】【CQOI2016】手机号码
感觉数位dp好恶心……
原题:
人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不
吉利的数字等。手机运营商在发行新号码时也会考虑这些因素,从号段中选取含有某些特征的号
码单独出售。为了便于前期规划,运营商希望开发一个工具来自动统计号段中满足特征的号码数
量。
工具需要检测的号码特征有两个:号码中要出现至少3个相邻的相同数字,号码中不能同
时出现8和4。号码必须同时包含两个特征才满足条件。满足条件的号码例如:13000988721、
23333333333、14444101000。而不满足条件的号码例如:1015400080、10010012022。
手机号码一定是11位数,前不含前导的0。工具接收两个数L和R,自动统计出[L,R]区间
内所有满足条件的号码数量。L和R也是11位的手机号码。
10^10 < = L < = R < 10^11
数位dp好恶心>π<
f[i][flag1][last1][last2][flag2][flag3]
第i位,有没有到顶(0表示到了,1表示没到),前一个是啥,再前一个是啥,关于4和8的状态(两个压成了一维),有没有三连(稽
然后这里要从高往低,设flag为4和8的状态,mark为三连(稽)的状态
初始状态就是f[2][0][a[1]][a[2]][flag][0]=1,因为从高往低dp,所以a也是从高位彺低位
注意不用担心这里的1会直接被算到答案里的情况,因为flag不一定不为3(为3表示有4又有8),同时mark=0,所以这个1对答案没贡献,但是可能会对其它合法的状态有贡献
然后对于每一位首先需要判断一下上限是否会对其它状态贡献,就在循环外面开一个flag‘和一个mark‘,表示上限的状态
每到1为flag‘|=a[i]关于4或8的状态,mark‘|=是否和前面两个形成三连(稽)
如果flag不等于3,即状态合法,那么f[i][0][a[i-1]][a[i-2]][flag][mark]=1
为啥mark等于0的时候依旧会贡献?因为flag这次完了就真的完了,mark暂时没有三连(稽)以后还可以翻
然后枚举上一位k,再上一位j,再上一位q,以及关于4和8的状态p
转移式如下:
f[i][1][k][q][flag][1]+=(q<a[i])*f[i-1][0][j][k][p][1]+f[i-1][1][j][k][p][1];
f[i][1][k][q][flag][mark]+=(q<a[i])*f[i-1][0][j][k][p][0]+f[i-1][1][j][k][p][0];
恩再多我也解释不了了,只能意会
全程抄代码,感觉只是勉强理解了这题,并不能自己写出来
注意l=1e10的情况,减一下就不是11位了
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 #define ll long long 8 ll n,m; 9 int a[20]; 10 ll f[12][2][10][10][4][2]; 11 int QAQ(int x,int y){ return ((x==8)<<1)|(x==4)|((y==8)<<1)|(y==4);} 12 ll play(ll x){ 13 memset(f,0,sizeof(f)); 14 for(int i=11;i>=1;--i) a[i]=x%10,x/=10; 15 int flg=QAQ(a[1],a[2]),mk=0; 16 f[2][0][a[1]][a[2]][flg][0]=1; 17 for(int i=1;i<=a[1];++i)for(int j=0;j<=9;++j){ 18 if(i==a[1] && j>=a[2]) continue; 19 f[2][1][i][j][QAQ(i,j)][0]=1; 20 } 21 for(int i=3;i<=11;++i){ 22 flg|=QAQ(a[i],a[i]),mk|=(a[i]==a[i-1] && a[i]==a[i-2]); 23 if(flg!=3) f[i][0][a[i-1]][a[i]][flg][mk]=1; 24 for(int j=0;j<=9;++j)for(int k=0;k<=9;++k)for(int p=0;p<=2;++p)for(int q=0;q<=9;++q){ 25 int flg1=p|QAQ(q,q),flg2=(q==k && k==j); 26 if(flg1==3) continue; 27 f[i][1][k][q][flg1][1]+=(q<a[i])*f[i-1][0][j][k][p][1]+f[i-1][1][j][k][p][1]; 28 f[i][1][k][q][flg1][flg2]+=(q<a[i])*f[i-1][0][j][k][p][0]+f[i-1][1][j][k][p][0]; 29 } 30 } 31 ll bwl=0; 32 for(int i=0;i<=9;++i)for(int j=0;j<=9;++j)for(int p=0;p<=2;++p)for(int q=0;q<=1;++q) 33 bwl+=f[11][q][i][j][p][1]; 34 return bwl; 35 } 36 int main(){//freopen("ddd.in","r",stdin); 37 cin>>n>>m; 38 if(n==10000000000LL){ cout<<play(m)<<endl; return 0;} 39 cout<<play(m)-play(n-1)<<endl; 40 return 0; 41 }
【BZOJ4521】【CQOI2016】手机号码
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。