当前位置：首页 > news >正文

打卡信奥刷题（3150）用C++实现信奥题 P7682 [COCI 2008/2009 #5] TRESNJA

news 2026/4/22 23:09:41

P7682 [COCI 2008/2009 #5] TRESNJA

题目描述

Lana 住在一个快乐的小村庄里。主街旁边有一排樱桃树。Lana 注意到每棵树用从1 11开始的连续整数编号。经过大量研究，Lana 注意到树的编号唯一地决定了树的樱桃数量。对于一棵树，考虑将树编号中的连续数字组拆分出来。对于每组数字，将这一组中唯一的数字乘以该组数字长度的平方。把这些数字加在一起就得到了树上的樱桃总数。例如，在编号为77744007 7774400777744007的树中，我们将编号中的连续数字组拆分出来，得到4 44组数：777 777777、44 4444、00 0000和7 77。所以编号为77744007 7774400777744007的树中樱桃的数量为7 × 3 2 + 4 × 2 2 + 0 × 2 2 + 7 × 1 2 = 86 7\times 3^2+4\times 2^2+0\times2^2+7\times1^2=867×32+4×22+0×22+7×12=86个。

到了摘樱桃的时候了，村民们同意把编号在区间[ a , b ] [a,b][a,b]中的树上的樱桃都摘下来。现在请你编写一个程序来计算采摘樱桃的总量。

输入格式

输入仅一行，两个整数a , b a,ba,b，代表能够采摘樱桃的树的起始点和终止点。

输出格式

输出仅一行，一个整数，代表能够采摘的樱桃总量。

输入输出样例 #1

输入 #1

1 9

输出 #1

输入输出样例 #2

输入 #2

100 111

输出 #2

输入输出样例 #3

输入 #3

7774407 7774407

输出 #3

说明/提示

【数据范围】

对于所有数据，1 ⩽ a ⩽ b ⩽ 10 15 1\leqslant a\leqslant b\leqslant 10^{15}1⩽a⩽b⩽1015。

【题目来源】

本题来源自COCI 2008-2009 CONTEST 5 T5 TRESNJA，按照原题数据配置，满分120 120120分。

由 Eason_AC 翻译整理提供。

C++实现

#include<iostream>#include<cstdio>#include<cstring>#defineintlonglongusingnamespacestd;constintINFN=2035;constintINF=17;constintINFF=13;intl,r,a[INF],tot,f[INF][INFF][INF][INFN];intDFS(intb,intc,intd,inte,intp){if(b<=0)returnp+d*e*e;if(f[b][d][e][p]!=-1&&!c)returnf[b][d][e][p];intMax=(c?a[b]:9),sum=0;for(inti=0;i<=Max;i++){sum+=DFS(b-1,(c&&i==Max),i,(i==d?e+1:1),(i!=d?p+d*e*e:p));}if(!c)f[b][d][e][p]=sum;returnsum;}intcalc(intxx){memset(f,255,sizeoff);memset(a,0,sizeofa);tot=0;while(xx){a[++tot]=xx%10;xx/=10;}returnDFS(tot,1,10,0,0);}signedmain(){scanf("%lld %lld",&l,&r);cout<<calc(r)-calc(l-1)<<"\n";return0;}