题目相关:
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 <cstdio>
#include <map> typedef long long LL; int main()
{ int kase;
scanf("%d", &kase);
while ( kase-- > 0 ) {
int n;
scanf("%d", &n); std::map<int, int> 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;
}