蒟蒻求调数位dp,能过样例(回复必关
查看原帖
蒟蒻求调数位dp,能过样例(回复必关
576803
z526楼主2022/11/15 19:24
#include <iostream>
#include<cstring>
#define ll long long
using namespace std;
const int N = 40;
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/15 19:24
加载中...