思路
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int f[11][10][10];
void init()
{
for(int i=0;i<=9;i++) f[1][i][i]=1;
for(int i=2;i<=10;i++)
for(int j=0;j<=9;j++)
for(int u=0;u<=9;u++)
{
if(u==j) f[i][j][u]+=pow(10,i-1);
for(int k=0;k<=9;k++)
f[i][j][u]+=f[i-1][k][u];
}
}
int dp(int n,int u)
{
if(!n) return u?0:1;
vector<int> num;
while(n) num.push_back(n%10),n/=10;
int ans=0,last=0;
//所有n位数的方案数量,因为本题不能算前导零,所以左边第一个分支取值为1~an-1;
for(int i=num.size()-1;i>=0;i--)
{
int x=num[i];
for(int j=(i==num.size()-1);j<x;j++)//算上后面的u的个数
{
ans+=f[i+1][j][u];
}
ans+=x*last*pow(10,i);//算上前面的u的个数
if(x==u) last++;//记录last
if(!i) ans+=last;//这个数本身所含有的
}
//所有0~n-1位数的方案数量,例如000123是不合法的,而123确实合法的
for(int i=1;i<num.size();i++)
for(int j=1;j<=9;j++)
ans+=f[i][j][u];
//若n是小于等于10的话,那么0的情况就不会被考虑进去,因此需要进行特判
//如果u==0,那么就将0的情况算进去
if(!u) ans+=f[1][u][u];
return ans;
}
int main()
{
int l,r;
init();
while(cin>>l>>r,l||r)
{
if(l>r) swap(l,r);//l可能大于r
for(int i=0;i<=9;i++)
printf("%d ",dp(r,i)-dp(l-1,i));
printf("\n");
}
return 0;
}
数据加强,小于10的数0统计都是0
感谢,已指正
你这个dp第一特判有问题,过不了最后一组数据,应该改成if(n<10)return n>=u
为什么预处理(u==j)时加的不是j*10^(i-1)
请问最后为什么ans += last呢?个人感觉会被包含在 ans+=xlastpow(10,i); 中
这个预处理的定义为什么模拟起来不太对?
比如f[2][1][2] : 表示两位数 最高位是1 的2出现的次数.
按照这个定义 2, 12 符合条件 应该是2 但是把f[][][]打出来 发现f[2][1][2] = 1 ?
这里我觉得就是1,预处理处理的是两位数,2的话是02,有前缀0,在dp里边特判了,因此预处理时只有12一个数满足
棒(๑•̀ㅂ•́)و✧
很好地贯彻了提高课的思路,棒(๑•̀ㅂ•́)و✧
膜
ans+=xlastpow(10,i);
这个我怎么有点没看懂呢
last表示前面u的数量,x*pow(10,i)表示后面的数总共有几个,这样相乘就可以得到前面的u一共有几个了
可以看第一张图啊,上面有详细解释了
明白了,明白了,orz
不客气ヾ(´∀`o)+
我觉得是不是第一张图第二行写错了,那是x=3的情况吧
已修改,谢谢指正✧(≖ ◡ ≖✿)