蒟蒻求调数位dp
查看原帖
蒟蒻求调数位dp
331246
FJ_Farmer_Johhn楼主2022/11/26 11:31
#include<bits/stdc++.h>
using namespace std;
unsigned long long cnt,a[100],ka,kb,ass;
void div(unsigned long long x)
{
	cnt=0;
	while(x)
	{
		a[++cnt]=x%10;
		x/=10;
	}
}
unsigned long long num(unsigned long long l,unsigned long long r)
{
	unsigned long long res=0;
	for(unsigned long long i=l;i>=r;i--)
		res=res*10+a[i];
	return res;
}
unsigned long long pow10(unsigned long long x)
{
	unsigned long long res=1;
	while(x--)
		res*=10;
	return res;
}
unsigned long long ct(unsigned long long x,unsigned long long k)
{
	if(!x)
		return 0;
	div(x);
	unsigned long long ans=0;
	for(unsigned long long i=cnt;i>0;i--)
	{
		if(i<cnt)
		{
			ans+=num(cnt,i+1)*pow10(i-1);
		}
		if(a[i]>k)
			ans+=pow10(i-1);
		else if(a[i]==k)
			ans+=num(i-1,1)+1;
	}
	return ans;
}
int main()
{
	unsigned long long T;
	scanf("%llu",&T);
	while(T--)
	{
		scanf("%llu%llu",&ka,&kb);
		if(!ka)
			ka++;
		ass=0;
		if(ka>kb)
			swap(ka,kb);
		for(unsigned long long i=1;i<=9;i++)
			ass+=(ct(kb,i)-ct(ka-1,i))*i;
		printf("%llu\n",ass);
	}
	return 0;
}

感谢各位大佬

2022/11/26 11:31
加载中...