ZOJ 3872--解题报告-白红宇

ZOJ 3872--解题报告

阅读量：6372 次

发布时间：2019-06-23

本文共 1645 字，大约阅读时间需要 5 分钟。

题目相关:

　　3872相关链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5520

　　Edward拥有一组数列. 其定义了Beauty数: 连续子串的和(重复的项只计算一次). 比如子串: 2, 3, 3. 则总和为beauty=2+3= 5 (数值3只计算一次).

　　目标: 求一组数列中, 所有Beauty数的总和.

思路分析:

　　• 评估数据:

　　数据规模: 数列的长度为N (1 <= N <= 100000)

　　数值范围: 成员都是正整数, 且大小不大于1000000.

　　由此可得, 子串个数为N*(N-1)/2, 而最终的总数最大范围为 N*Ｎ*M = 10^5 * 10^5 * 10^6 = 10^16, 超过4位int/long范围, 尚在8位long long的表示范围内.

　　• 思路权衡

　　采用暴力的方式去解决, 枚举每个子串, 显然不可行. 就算子串的和计算为O(1), 由于子串个数N*(N-1)/2的数据规模10^10, 显然不行.

　　关于计数/累计和的问题时, 往往可以采取动态规划的方式来简化这个问题.

设定opt[k]表示序列以第k个元素结尾的所有子串和, val[k]为数组的第k个元素数值.    如果不考虑重复数据不得累加的问题, 则递进公式为:        opt[k] = opt[k - 1] + delta(k) * val[k] = opt[k - 1] + k * val[k]    opt[k]在opt[k-1]对应的所有子串基础上, 尾部添加val[k]项组成新子串. 总共添加k次.        然而由于重复数字只计算一次的限制, 该公式需要修正.     引入索引映射idx, 其key为数值, value表示该数值最后出现的索引位置.    修正的核心为:          delta(k) = 新子串数 - 忽略次数 = k - idx[val[k]]    注: idx[val[k]]为val[k]最后出现的索引位置,  在这之前的子串因该数值已出现过, 视为忽略.    于是递进公式演变为:        opt[k] = opt[k - 1]  + delta(k) * val[k] = opt[k - 1] + (k - idx[val[k]]) * val[k];    最后结果为:        result = opt[1] + opt[2] + ... + opt[n]    这样总得时间复杂度为O(N).

AC代码:

#include 
     
      #include 
      typedef long long LL;int main(){        int kase;    scanf("%d", &kase);    while ( kase-- > 0 ) {        int n;        scanf("%d", &n);            std::map
       
         kbmap;        LL opt_sum = 0, total_sum = 0;        int val;        for ( int i = 1; i <= n; i++ ) {            scanf("%d", &val);            opt_sum = opt_sum + (i - kbmap[val]) * val;            total_sum += opt_sum;            kbmap[val] = i;          }                 printf("%ld\n", total_sum);            }    return 0;}

转载地址：http://qguqa.baihongyu.com/

你可能感兴趣的文章