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^24\times 2^20\times2^27\times1^2867×324×220×227×1286个。到了摘樱桃的时候了村民们同意把编号在区间[ a , b ] [a,b][a,b]中的树上的樱桃都摘下来。现在请你编写一个程序来计算采摘樱桃的总量。输入格式输入仅一行两个整数a , b a,ba,b代表能够采摘樱桃的树的起始点和终止点。输出格式输出仅一行一个整数代表能够采摘的樱桃总量。输入输出样例 #1输入 #11 9输出 #145输入输出样例 #2输入 #2100 111输出 #268输入输出样例 #3输入 #37774407 7774407输出 #386说明/提示【数据范围】对于所有数据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实现#includeiostream#includecstdio#includecstring#defineintlonglongusingnamespacestd;constintINFN2035;constintINF17;constintINFF13;intl,r,a[INF],tot,f[INF][INFF][INF][INFN];intDFS(intb,intc,intd,inte,intp){if(b0)returnpd*e*e;if(f[b][d][e][p]!-1!c)returnf[b][d][e][p];intMax(c?a[b]:9),sum0;for(inti0;iMax;i){sumDFS(b-1,(ciMax),i,(id?e1:1),(i!d?pd*e*e:p));}if(!c)f[b][d][e][p]sum;returnsum;}intcalc(intxx){memset(f,255,sizeoff);memset(a,0,sizeofa);tot0;while(xx){a[tot]xx%10;xx/10;}returnDFS(tot,1,10,0,0);}signedmain(){scanf(%lld %lld,l,r);coutcalc(r)-calc(l-1)\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容