题解 AT1483 【1】
_虹_
2019-03-30 20:27:23
貌似没有递推的题解。
补上一篇。
```cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define reg register
const int kmaxn=25;
typedef long long ll;
ll dp[kmaxn][10];//dp(i,j)表示在第1-i位，第i位以1结尾，1到(i-1)位随便放时，1出现的次数
ll m[kmaxn];
int n;
void init()
{
m[0]=dp[1][1]=1;
m[1]=10;
for(reg int i=2;i<=n;++i)
{
m[i]=m[i-1]*10;//预处理出10的i次幂
for(reg int j=0;j<10;++j)
{
for(reg int k=0;k<10;++k)
{
dp[i][j]+=dp[i-1][k];//不管这一位放什么，前一位都随便放，所以dp(i,j)=sigma dp(i,0 to 9);
}
}
dp[i][1]+=m[i-1];//当这一位放1时贡献的答案
}
}
ll query(const vector<int>& vec)
{
ll res=0;
ll ans=0;
for(reg int i=0,j=vec.size();i<j;++i)//预处理出上界的数值
{
res+=vec[i]*m[i];
}
for(reg int i=vec.size();i>0;--i)
{
for(reg int j=0;j<vec[i-1];++j)//当前位小于上界，更高位==上界时
{
ans+=dp[i][j];
}
res-=vec[i-1]*m[i-1];
if(vec[i-1]==1)//当前位上界是一时，这个1产生的贡献就是低位的数值
ans+=res;
}
return ans;
}
inline void trans(vector<int>& vec,const string& str)//倒置整数+char转int
{
vec.clear();
for(reg int i=str.size()-1;i>=0;--i)
{
vec.push_back(str[i]-'0');
}
}
inline void add(vector<int>& vec)//加个一，闭区间变开区间
{
int t=1;
for(reg int i=0,j=vec.size();i<j;++i)
{
vec[i]+=t;
t=vec[i]/10;
vec[i]%=10;
}
if(t)
vec.push_back(t);
}
string l,r;
vector<int> lv,rv;
int main()
{
ios::sync_with_stdio(false);
cin>>r;
n=r.size()+1;
init();
trans(rv,r);
add(rv);
cout<<query(rv)<<endl;
return 0;
}
其实l和lv并没有用上的说，毕竟左边界是1,query(0)显然等于0...
```