对于统计一个区间类的计数问题可以考虑用数位DP来写。
回到本题就是统计首位相同数字个数。dp[i][j]表示位数为i且首位为j的个数。
<pre name="code" class="cpp">#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<iostream>#include<queue>#include<cmath>#include<map>#include<stack>#include<bitset>using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )typedef long long LL;typedef pair<int,int>pil;const int INF = 0x3f3f3f3f;LL dp[20][10][10][2];int num[50];LL l,r;LL dfs(int pos,int st,int ed,int first,int flag){if(pos==0)return st==ed;if(!flag&&dp[pos][st][ed][first]!=-1)return dp[pos][st][ed][first];int d=flag?num[pos]:9;LL sum=0;for(int i=0;i<=d;i++){int s=st,e=ed;if(!first&&i)s=i;if(pos==1)e=i;sum+=dfs(pos-1,s,e,first||i,flag&&i==d);}if(!flag) dp[pos][st][ed][first]=sum;return sum;}LL solve(LL x){if(x==0) return 1;int pos=0;while(x){num[++pos]=x%10;x/=10;}return dfs(pos,0,-1,0,1);}int main(){CLEAR(dp,-1);while(~scanf("%lld%lld",&l,&r)){LL ans=solve(r)-solve(l-1);printf("%lld\n",ans);}return 0;}
，穿过紫堇，穿过木棉，穿过时影时现的悲喜和无常。
