UVA - 1640 The Counting Problem (数位dp)

题意:统计l-r中每种数字出现的次数

很明显的数位dp问题，虽然有更简洁的做法但某人已经习惯了数位dp的风格所以还是选择扬长避短吧(说白了就是菜啊)

从高位向低位走，设状态$(u,lim,ze)$表示当前走到了第几位，是否有上限，是否有前导零的状态，则问题转化成了求所有转移路径中经过的所有数字的数量统计问题。

设$f[u][lim][ze]$为从状态$(u,lim,ze)$向后走能到达的状态总数，$g[u][lim][ze][i]$为状态$(u,lim,ze)$及其向后走能到达的所有状态中数字$i$出现的总数，各种转移就行了，实现细节比较复杂就不啰嗦了~~

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=+,inf=0x3f3f3f3f;

 int l,r,bit[N],nb,f[N][][],g[N][][][],vis[N][][],cnt[N],ka;

 void dfs(int u,int lim,int ze) {

     if(vis[u][lim][ze]==ka)return;

     vis[u][lim][ze]=ka;

     if(u==) {

         f[u][lim][ze]=;

         for(int i=; i<=; ++i)g[u][lim][ze][i]=;

         return;

     }

     f[u][lim][ze]=;

     for(int i=; i<=; ++i)g[u][lim][ze][i]=;

     for(int i=; i<=(lim?bit[u]:); ++i) {

         int lim2=(lim&&i==bit[u]),ze2=(ze&&i==);

         dfs(u-,lim2,ze2);

         f[u][lim][ze]+=f[u-][lim2][ze2];

         if(!(ze&&i==))g[u][lim][ze][i]+=f[u-][lim2][ze2];

         for(int j=; j<=; ++j)g[u][lim][ze][j]+=g[u-][lim2][ze2][j];

     }

 }

 void solve(int x,int F) {

     for(nb=; x; x/=)bit[++nb]=x%;

     dfs(nb,,);

     for(int i=; i<=; ++i)cnt[i]+=F*g[nb][][][i];

 }

 int main() {

     while(scanf("%d%d",&l,&r)&&l) {

         if(l>r)swap(l,r);

         memset(cnt,,sizeof cnt);

         ++ka,solve(r,);

         ++ka,solve(l-,-);

         for(int i=; i<=; ++i)printf("%d%c",cnt[i]," \n"[i==]);

     }

     return ;

 }