关于题PR003004 - Digit Sum,为什么总是uke
  • 板块学术版
  • 楼主z526
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/11/16 06:20
  • 上次更新2023/10/27 02:49:19
查看原帖
关于题PR003004 - Digit Sum,为什么总是uke
576803
z526楼主2022/11/16 06:20
#include <iostream>
#include<cstring>
#define ll unsigned long long
using namespace std;
const int N=50;
ll l,r,dp[N],sum[N],mi[N];
ll ans1[N],ans2[N];
ll a[N];
ll t;
ll anss;
inline void init() {
	anss=0;
	memset(dp,0,sizeof(dp));
	memset(sum,0,sizeof(sum));
	memset(mi,0,sizeof(mi));
	memset(ans1,0,sizeof(ans1));
	memset(ans2,0,sizeof(ans2));
	memset(a,0,sizeof(a));
}
inline void solve(ll n, ll *ans) {
	ll tmp=n;
	int len=0;
	while (n)a[++len] =n%10,n/=10;
	for (register int i=len; i>=1; --i) {
		for(register int j(0); j<10; j++)ans[j]+=dp[i-1]*a[i];
		for(register int j(0); j<a[i]; j++)ans[j]+=mi[i-1];
		tmp-=mi[i-1]*a[i],ans[a[i]]+=tmp+1;
		ans[0]-=mi[i-1];
	}
}
int main() {
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	//cout.tie(0);
	cin>>t;
	while(t--) {
		init();
		cin>>l>>r;
		mi[0]=1;
		for(register int i=(1); i<=16; ++i) {
			dp[i]=dp[i-1]*10+mi[i-1];
			mi[i]=10*mi[i-1];
		}
		solve(r,ans1),solve(l-1,ans2);
		for(register int i=0; i<10; ++i) anss+=i*(ans1[i]-ans2[i]);
		cout<<anss<<'\n';
	}
	return 0;
}
2022/11/16 06:20
加载中...