Luogu传送门

先来看看题意:

定义$S(x)$为$x$各个数位上的数字的$k$次幂和($k$给定)。

定义$h(x)$为满足$h(x)\leq min\{x,h(s(x))\}$的最大值。

求$\sum^r_{x=l} h(x) \pmod {10^7+7}$的值。

$1\leq l,r \leq 10^6,1\leq k \leq 6$

第一眼以为是一道数学题,看了几眼题面没看懂题意。

那么让我们把这个看不懂的$h(x)$认真看看,其实就是要找到一个在不断的$x=s(x)$过程中的最小的$x$,即$min\{x,s(x),s(s(x))...\}$。最大值三个字没啥用,因为是唯一的值。


考虑递归,思考边界在哪里。

在$k$给定的情况下,相同的$x$所计算出来的$s(x)$是一定的。所以当我们递归到已经出现过的数值的时候,就没必要在继续下去了。

于是最终的思路就是不断的$x=s(x)$,直到一个值出现第二次时,这条路上的最小值就是答案。

但是不太友善的数据范围让我有点慌,于是加了个小小的优化:预处理每一个数字的$k$次方。

然而..

(经过了几次试探$vis$数组的大小),被卡在了#10

再看看数据范围,仿佛明白了什么。

同一个$s(x)$可能会被多次用到,但同一个$h(x)$不会。

那么对$s(x)$记忆化。

然而现实又一次打败了我:我可怜的#10依然$TLE$。

有点慌了,跑去翻了翻题解,感觉没啥不同...

可问题在于:我的$get\_s$是这么写的:

int get_s(int x)
{
    if(s[x])return s[x];
    int cnt=0;
    while(x){cnt+=p[x%10];x/=10;}
    return s[x]=cnt;
}

看上去好像没有问题。

可细细看看最终的返回值,此时的$x$必定为$0$,而程序不会$get\_x(0)$,这会导致记忆化失效

芜湖!

int get_s(int x)
{
    if(s[x])return s[x];
    int cnt=0,a=x;
    while(x){cnt+=p[x%10];x/=10;}
    return s[a]=cnt;
}

略改,一发入魂。


求$h(x)$部分

int work(int x)
{
    int res=x,k=x;
    while(ap[k]!=x)
    {
        ap[k]=x;
        k=get_s(k);
        res=min(res,k);
    }
    return res;
}

($ap$即$vis$数组)

这样写可以避免每次数组的清空。意思应该也很轻松能理解。

整篇代码

#include<bits/stdc++.h>
using namespace std;
int mod=1e7+7,ans=0;
int p[10];
int s[10000010];
int ap[10000010];
inline int min(int a,int b){return a<b?a:b;}
int get_s(int x)
{
    if(s[x])return s[x];
    int cnt=0,a=x;
    while(x){cnt+=p[x%10];x/=10;}
    return s[a]=cnt;
}
int work(int x)
{
    int res=x,k=x;
    while(ap[k]!=x)
    {
        ap[k]=x;
        k=get_s(k);
        res=min(res,k);
    }
    return res;
}
int main()
{
    int k,l,r;
    scanf("%d%d%d",&k,&l,&r);
    for(int i=1;i<=9;i++)
        p[i]=pow(i,k);
    for(int i=l;i<=r;i++)
        (ans+=work(i))%=mod;
    printf("%d\n",ans);
    return 0;
}
最后修改:2020 年 08 月 17 日 08 : 09 PM