题目传送门
【题目大意】
【思路分析】
这题看上去是个数位DP，实际上它就是一个脑筋急转弯[滑稽.jpg]
好的我们来正经分析一下，如果两个数有相同的前缀，只有个位不同的话，那么对应的$f$值必然不同。也就是说，对于只有个位数不同的10个数，个位数$i\in[0,9]$，对应的$f$值之和为$\sum_{i=1}^{9}i=45$。对于$\sum_{i=1}^{x}f(i)$，我们将其分成$[1,9],[10,19],[20,29]……[(\lfloor \frac{n}{10}\rfloor-1)*10,\lfloor \frac{n}{10}\rfloor*10-1]$，答案为$\lfloor \frac{n}{10}\rfloor*45$。剩下的$n\+1$个数我们单独计算其$f$值并求和，为了防止超时，我们可以转换一下$f(\lfloor \frac{n}{10}\rfloor*10+i)=(f(\lfloor \frac{n}{10}\rfloor*10)+i)\(i\in[0,n\])$
然后就很简单了，答案求$\sum_{i=1}^{r}f(i)-\sum_{j=1}^{l-1}f(j)$即可。
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define g() getchar() 8 #define rg register 9 #define go(i,a,b) for(rg int i=a;i<=b;i++) 10 #define back(i,a,b) for(rg int i=a;i>=b;i--) 11 #define db double 12 #define ll long long 13 #define il inline 14 #define pf printf 15 #define mem(a,b) memset(a,b,sizeof(a)) 16 using namespace std; 17 ll fr(){ 18 ll w=0,q=1; 19 char ch=g(); 20 while(ch<'0'||ch>'9'){ 21 if(ch=='-') q=-1; 22 ch=g(); 23 } 24 while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g(); 25 return w*q; 26 } 27 int T; 28 ll l,r; 29 il int solve(ll x){ 30 int a[20],L=0,R=2; 31 while(x) a[++L]=x%10,x/=10; 32 while(R<=L){ 33 back(i,L,R) a[i]=(a[i]+a[i-1])%10; 34 while(a[L]==0&&L>R) L--;//要去掉前导零 35 R++; 36 } 37 return a[L]; 38 } 39 il ll work(ll x){ 40 if(x<10) {ll ans=(1+x)*x>>1;return ans;}//特判小于10的情况 41 ll ans=(x/10)*45,b=(x/10)*10; 42 rg int a=x%10,c=solve(b); 43 go(i,0,a) ans+=1ll*(c+i)%10; 44 return ans; 45 } 46 int main(){ 47 //freopen("","r",stdin); 48 //freopen("","w",stdout); 49 T=(int)fr(); 50 while(T--){ 51 l=fr();r=fr(); 52 pf("%lld\n",work(r)-work(l-1)); 53 } 54 return 0; 55 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11587103.html
