第二道数位dp,因为“数位dp都是模板题”(误),所以是从第一道的基础上面改的。
核心思想就是分类讨论,分不同情况讨论对答案的贡献。
最最重要的是,该数位取与当前位相等的时候,贡献的个数是受这个数位影响的所有数(这个写法里包括它本身),那么就用x减去与x前缀相同的“整数”再+1就可以算出来了。
其他的数位dp……好像就不太会写了,再研究一下。
#includeusing namespace std;#define ll long longll dp[14][10][10];ll pow10[14];ll sum(int i,int j1,int j2,int k){ if(j1<0) j1=0; if(j2>9) j2=9; ll res=0; for(int j=j1;j<=j2;j++){ res+=dp[i][j][k]; } return res;}void init(){ pow10[0]=1; for(int i=1;i<=13;i++){ pow10[i]=pow10[i-1]*10; } for(int j=0;j<=9;j++) dp[1][j][j]=1; for(int i=2;i<=13;i++){ for(int j=0;j<=9;j++){ for(int k=0;k<=9;k++){ dp[i][j][k]=sum(i-1,0,9,k); if(j==k){ dp[i][j][k]+=pow10[i-1]; } } } } /*for(int j=1;j<=2;j++){ dp[9][j]=sum(8,0,j-2)+sum(8,j+2,9); }*/ /*for(int i=1;i<=13;i++){ for(int j=0;j<=9;j++){ for(int k=0;k<=9;k++) printf("dp[%d][%d][%d]=%d\n",i,j,k,dp[i][j][k]); } printf("\n"); }*/}ll A,B;int digit[14];int w;ll count(ll x){ //cout<<"x="< < =1;i--){ //printf("i=%d res=%d\n",i,res); if(i==k){ //最高位取0 for(int ii=i-1;ii>=1;ii--){ res+=sum(ii,1,9,w); //printf("you want=%d\n",res); } if(w==0) res+=1;//0 //其实不用特判啊 for(int j=1;j =1){ if(j==w) res+=pow10[i-1]; res+=sum(i-1,0,9,w); } else{ if(j==w) res+=1; } } //最高位就取相等,问题留给下一次循环 //取相等怎么会是满的呢? if(digit[i]==w) res+=(x-x/pow10[i-1]*pow10[i-1]+1); } else{ //前面的位都相等,非最高位的情况 for(int j=0;j =1){ if(j==w) res+=pow10[i-1]; res+=sum(i-1,0,9,w); } else{ if(j==w) res+=1; } } if(digit[i]==w) res+=(x-x/pow10[i-1]*pow10[i-1]+1); } } //一直相等的情况在上面自动处理了,不用另外处理 /*for(int i=1;i<=k;i++){ if(digit[i]==w){ res++; } }*/ //printf("res=%d\n",res); return res;}int main(){ init(); while(~scanf("%lld%lld",&A,&B)){ for(w=0;w<=9;w++) printf("%lld%c",count(B)-count(A-1)," \n"[w==9]); }}
后来学会了搜索写法。