首页 > 其他分享 >题解:AT_abc379_e [ABC379E] E - Sum of All Substrings

题解:AT_abc379_e [ABC379E] E - Sum of All Substrings

时间:2024-11-09 23:40:45浏览次数:4  
标签:题解 Sum 一位 Substrings 答案 ans 贡献 sum

很水的一道题。

我们先把题目上各地的数字看成一个序列,然后考虑计算该序列分别会对答案的每一位产生多少贡献。

具体的,我们从后往前考虑答案的每一位。通过简单推演可知,设你当前考虑到答案的第 \(i\) 个数字,那么原序列对这一位的贡献为 \(\sum_{j=1}^{n-i+1}a_j\times j\)。

这个东西显然可以预处理,这样答案每一位的贡献就计算出来了。

但是我们需要考虑进位的问题,也就是说,我们用一个变量 \(sum\) 统计当前的进位。设当前这一位计算出来的贡献为 \(ans\),那么答案的这一位就是 \((ans+sum)\% 10\),同时让 \(sum\leftarrow \frac{sum+ans}{10}\) 即可。

这样填完答案的每一位以后我们需要判断此时 \(sum\) 是否为 \(0\),如果不是还需要再计算一位。

最后把答案倒序输出即可。

提交记录

标签:题解,Sum,一位,Substrings,答案,ans,贡献,sum
From: https://www.cnblogs.com/Lydic/p/18537495

相关文章

  • 题解:AT_abc379_d [ABC379D] Home Garden
    难度严格小于C题。你考虑每盆花被种植的时间一定单调不降,这启示我们去用二分。具体的,我们用一个数组\(a\)表示当前所有的花的种植时间,并记录一个当前时间\(t\)。对于每个1操作都在数组后面加上个元素\(t\),对于\(2\)操作让\(t\leftarrowt+T\)。对于操作3,能够摘取的......
  • Toyota Programming Contest 2024#11(AtCoder Beginner Contest 379)题解
    总体情况A-Cyclic题意给你一个三位整数\(N\),其中每个数字都是介于\(1\)和\(9\)之间的整数。设\(a\),\(b\),\(c\)分别是\(N\)的百位、十位和个位数。打印一个按此顺序排列\(b\),\(c\),\(a\)所组成的整数,以及一个按此顺序排列\(c\),\(a\),\(b\)所组成......
  • 2024.11.9组队训练题解记录
    Teleportation鲍勃最近访问了一个奇怪的传送系统。该系统包含\(n\)个房间,编号为\(0\)到\(n-1\)。每个房间都安装了一个传送设备。每个传送设备都有一个看起来像钟表表面的仪表板,上面有一个指针,显示数字\(0\)到\(n-1\),按顺时针顺序排列。最初,第\(i\)个房间的传送设备上......
  • P4156 论战捆竹竿 题解
    论战捆竹竿题意:给定字符串\(s\),计数"串\(t\)的长度"可能的种数有多少种,使得\(t\)能被\(s\)作为印章印出来,且\(|t|\lew\)。\(n=|s|\le5\times10^5\),\(n\lew\le10^{18}\)。第一步:求出\(s\)的周期\(\{a_1\sima_m\}\),包含\(n\)(\(a_m=n\))。转化为求\(\suma_ib......
  • 题解:P11248 [GESP202409 七级] 矩阵移动
    笑点解析:这个人所在城市考试当天刮台风了,没考,免费送了一次12月的考试。设计这么一个东西:\(dp_{i,j}\)表示到格子\((i,j)\)的最大分数。本来还好,但现在的问题是,如果这个格子是‘?’,我哪儿知道到底可不可以变啊?万一变得太多了,那,那不就废了!万一少了,那我分不就没了?所以我们......
  • agc032 A~E 题解
    a倒推,每次删掉最后一个b[i]=i的即可b一开始发现可以构造完全二分图,使两边和同为S,这样每个点的和=对面二分图点的和=S,然后n=6和为奇数进一步发现可以直接分成A组组内和为B的组,然后组之间连边,此时S=(A-1)B,有AB=n(n+1)/2当n为奇数时取A=(n+1)/2,B=n,n单独一组其他大匹配小;n为偶数......
  • NOIP集训 P11071 「QMSOI R1」 Distorted Fate 题解
    题解:P11071「QMSOIR1」DistortedFate给定一个长度为\(n\)的数组\(A\),你需要完成以下\(q\)次操作。1.1lrx将\(A_i(l\lei\ler)\)异或上\(x\)。2.2lr求:\[(\sum_{i=l}^r\bigcup_{j=l}^iA_j)\bmod2^{30}\]其中\(\bigcup\)表示按位或。Input第一行输入......
  • [COCI2022-2023#5] Slastičarnica 题解
    前言题目链接:洛谷。题意简述一个长为\(n\)的序列\(\{a_n\}\)和\(q\)次操作,第\(i\)次操作中,你可以删除序列长为\(d_i\)的前缀或后缀,并需要保证删除的所有数\(\geqs_i\)。每次操作前,你可以选择任意长度的前缀或后缀,并将其删除,也可以不操作。请问,在你不能进行下一次操......
  • CodeforceTon Round 4 div1 + div2 题解
    题解A-EDreamissofar~A.BeautifulSequence检查每一位对应的数字是否小于等于位置,如果可以说明这个数字可以移动到对应位置上,遍历即可#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voidsolve(){ intn; cin>>n; vector<int>a......
  • CF607B Zuma 题解
    CF607BZuma不知道为什么你谷会评蓝,这不是很基础的区间DP吗。Problem-607B-Codeforces题意简述消除回文子串的最小次数。思路对于区间\([i,j]\),如果它是回文的,那么消除它所需的次数是\(1\)。如果它不是回文的,但是\(a[i]==a[j]\),那么当区间\([i+1,j-1]\)被消除到只剩下......