P3754 首都效应 题解

· · 题解

题意

把 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;
}