Codeforces-Round-1043-Div.-3-D.-From-1-to-Infinity
目录
Codeforces Round 1043 (Div. 3) D. From 1 to Infinity
D.从 1 到无穷大
每次测试的时间限制：1.5 秒
每次测试的内存限制：256 兆字节
输入：标准输入
输出：标准输出
瓦迪姆想了解由从 111 到无穷大的正整数连续写成的数字组成的无穷序列。也就是说，这个序列看起来像 123456789101112131415…123456789101112131415 \ldots123456789101112131415…
为了避免无穷大，瓦迪姆在 kkk /th数字处截断了这个序列，并舍弃了它之后的所有数字。这样，序列中就只剩下了 kkk 个数字。请帮助他找出剩余序列中的数字之和。
输入
每个测试由多个测试用例组成。第一行包含一个整数 ttt (1≤t≤2⋅104)(1 \le t \le 2 \cdot 10^4)(1≤t≤2⋅104) 。- 测试用例的数量。下面几行描述测试用例。
在每个测试用例的单行中，都有一个整数 kkk - 剩余序列 (1≤k≤1015)(1 \le k \le 10^{15})(1≤k≤1015) 中的位数。
输出
对于每个给定的 kkk ，输出长度为 kkk 的序列中的数字之和。
注
在第一个样本中，剩余序列为 123451234512345 。
在第二个样本中，剩余序列为 123456789112345678911234567891 。
第三个样本的剩余序列为 123456789101112345678910111234567891011 。
代码欣赏
#include<bits/stdc++.h>
#define int long long
using namespace std;
int num[20]={0,9,189,2889,38889,488889,5888889,68888889,788888889,8888888889,98888888889,1088888888889,11888888888889,128888888888889};
int shu10[20]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000};
int dp[25][2],f[25][2],n,shu[20],zhi[20],l;
int qiu(int u,int limit)
{
if(u==0)
return 0;
int sum=0;
if(dp[u][0]!=-1&&!limit)
return dp[u][0];
if(f[u][0]!=-1&&limit)
return f[u][0];
int ss=((u==1&&l<2)?1:0);
for(int i=ss;i<=(limit?zhi[u]:9);i++)
{
sum+=(qiu(u-1,limit&&i==zhi[u])+i*((limit&&i==zhi[u])?f[u-1][1]:dp[u-1][1]));
((limit)?f[u][1]:dp[u][1])+=((limit&&i==zhi[u])?f[u-1][1]:dp[u-1][1]);
}
((limit)?f[u][0]:dp[u][0])=sum;
return sum;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int _,flag;
memset(dp,-1,sizeof(dp));
dp[0][1]=f[0][1]=1;
for(int i=1;i<=20;i++)
dp[i][1]=0;
cin>>_;
while(_--)
{
cin>>n;int ans=0;
for(int i=1;i<=18;i++)
f[i][1]=0,f[i][0]=-1;
for(int i=13;i>=0;i--)
{
if(n>num[i])
{flag=i;break;}
}
int yu=n-num[flag];
int h=floor(yu/(flag+1))+shu10[flag]-1;
// int yyy=(n-h*(flag+1));
// cout<<"666666 "<<yu<<'\n';
if(yu%(flag+1)!=0)
{
int g=h+1;int js=0;
// cout<<"------"<<g<<'\n';
int yu1=yu%(flag+1);
while(g>0)
{
shu[++js]=g%10;
g/=10;
}
for(int i=js;i>=js-yu1+1;i--)
ans+=shu[i];
}
l=0;
// cout<<h<<" "<<ans<<'\n';
while(h>0)
{
zhi[++l]=h%10;
h/=10;
}
ans+=qiu(l,1);
cout<<ans<<'\n';
// cout<<f[1][0]<<" "<<f[1][1]<<" "<<'\n';
// cout<<dp[1][0]<<" "<<dp[1][1];
}
return 0;
}