自动搬运

查看原文

来自洛谷，原作者为

	dyc2022 「知らない世界を見せてよ」

搬运于2025-08-24 21:52:21，当前版本为作者最后更新于2024-03-12 17:45:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

把 $n$ 的十进制形式拆分为若干个由相同的数码形成的连续子段，设共有 $m$ 个子段，第 $i$ 个子段的数码为 $num_i$，长度为 $len_i$，则城市 $n$ 的「房子数」$f(x)=\sum \limits^{m}_{i=1}num_ilen_i^2$。

给定整数 $[l,r]$，求 $\sum\limits^{r}_{i=l}f(i)$。

解法

考虑使用数位 dp。

我们可以使用记忆化搜索，定义 dfs(k,last,len,lim,sum) 表示还有 $k$ 位未搜，上一位数字为 $last$，当前位所属的连续段长度为 $len$，$lim$ 表示是否有数位限制，$sum$ 表示当前的和。由于显然 $sum$ 很大，因此要使用 std::map 进行映射。

接下来讲转移。如果要开始新的一个连续串，那么就计算前一个串的贡献。

AC 代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 17
using namespace std;
map<int,int> dp[N][N][N];
int num[N],len;
int dfs(int k,int last,int len,int lim,int sum)
{
    if(!k)return sum+len*last*len;
    if(!lim&&dp[k][last][len][sum])return dp[k][last][len][sum];
    int maxn=lim?num[k]:9,ans=0;
    for(int i=0;i<=maxn;i++)
    {
        if(i==last)ans+=dfs(k-1,i,len+1,lim&&i==maxn,sum);
        else ans+=dfs(k-1,i,1,lim&&i==maxn,sum+len*len*last);
    }
    if(!lim)dp[k][last][len][sum]=ans;
    return ans;
}
int solve(int x)
{
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)dp[i][j][k].clear();
    len=0;
    while(x)num[++len]=x%10,x/=10;
    return dfs(len,-1,0,1,0);
}
main()
{
    int l,r;
    scanf("%lld%lld",&l,&r);
    printf("%lld\n",solve(r)-solve(l-1));
    return 0;
}