$cometoj\#4\ D\ $求和不是$dp$

$Des$

$Sol$

$upd:$以下两段是错误做法,但我不想删掉$.jpg$

-----------------------以下是错误部分------------------------------

看到问$\sum_{n-l}^rf(n)$一定会想到数位$dp$叭,于是尝试数位$dp$,然而并不会做.但是觉得可以先尝试想暴力方法(当然是优秀点的暴力)?

对于一个数$abcd$,如下变化:$(a+b)(b+c)(c+d)$,$(a+2b+c)(b+2c+d)$,$(a+3b+3c+d)$,注意到其实中间过程中有没有取$\%$并没有影响,就这样加起来到最后再取$\%$是一样的.看到这里我想到了杨辉三角形.到这里可以得出,对于一个数$x$,我们可以在$log_{10}x$的时间里得出$f(x)$.然后你就可以去打暴力了.

-----------------------以下是正确部分------------------------------

容易发现,若最后一位的数字变化$1$,那么其$f$值也会变化$1$.又因为$f$值只能取$0$到$1$.所以对于连续的十个数,它们的$f$值的和是$\sum_{i=0}^9i=45.$于是要算出$\sum_{i=1}^{l}f(i)$就要简单多了,先$as+=45*(l/10)$,然后单独计算一下后面剩下的数就好了(只要暴力计算剩下的数的第一个就好了,其他的都可以推出来).最后的答案就是$sol(r)-sol(l-1)$.

总结一下,这题似乎不能用数位$dp$,而且数据范围又那么大,其实可以猜测到一定是有规律的一些数可以捆绑在一起算,这些数捆绑在一起的值又会有一定的规律.(突然想起上个学期做过的一个三角函数的题目,也是连续三个一起算,然后这个值又是是循环起来的).要找出这个规律就一定要去分析这个$f(n)$的性质/特殊性.

$over.$

$Code$

上午脑子很乱,$Wa$了$Inf$次,中午睡醒后重构一遍,虽然第一遍仍然没有过样例,但是再冷静地查了下错,于是过样例之后一遍$A$了.

Code

#include<bits/stdc++.h>

#define il inline

#define Ri register int

#define go(i,a,b) for(Ri i=a;i<=b;++i)

#define yes(i,a,b) for(Ri i=a;i>=b;--i)

#define e(i,u) for(Ri i=b[u];i;i=a[i].nt)

#define mem(a,b) memset(a,b,sizeof(a))

#define ll long long

#define db double

#define inf 2147483647

using namespace std;

il ll read()

{

    ll x=0,y=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}

    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}

    return x*y;

}

int a[20];

il ll calc(ll x)

{

    Ri ct=0;

    mem(a,0);

    while(x){a[++ct]=x%10,x/=10;}

    while(ct>1)

    {

	go(i,1,ct-1)a[i]=(a[i]+a[i+1])%10;

	--ct;while(!a[ct] && ct>0)--ct;

    }

    return a[1];

}

il ll sol(ll x)

{

    ll ret=(x+1)/10*45,ct=(x+1)%10;

    ll qvq=calc(x-ct+1);

    while(ct--)

    {

	ret+=qvq;

	qvq=(qvq+1)%10;

    }

    return ret;

}

int main()

{

    int T=(int)read();

    while(T--)

    {

	ll l=read(),r=read();

	//printf("sol(%lld)=%lld sol(%lld)=%lld\n",l-1,sol(l-1),r,sol(r));

	printf("%lld\n",sol(r)-sol(l-1));

    }

    return 0;

}

巴特西

$cometoj\#4\ D\ $求和不是$dp$

\(Des\)

\(Sol\)

\(Code\)

最新文章

热门文章

巴特西

$cometoj\#4\ D\ $求和 不是$dp$

\(Des\)

\(Sol\)

\(Code\)

最新文章

热门文章

$cometoj\#4\ D\ $求和不是$dp$