枚举+优化(8)——前缀和2

例3.题目链接:hihoCoder1534

 这道题要注意一下数据范围。首先N小于等于10万。其次Ai,也就是数组中每个数的值,是在负100万到正100万之间。假如这里Ai都是正整数的话,那么总共的划分方法不会太多,因为随着p增大,第一段的和S1是不断增大的。  但是因为这里Ai有可能是0,也有可能是负数,所以划分方法可能非常多。例如有可能数据是10万个Ai全都是0。这样随便一个划分都是满足条件的。答案是C(99999, 2),甚至超过了int范围。  我们看一下样例,A数组是[3, 2, 1, 0, 2]。一共有3种切分方法:第一种是3|2|1 0 2,3单独一组,2单独一组,然后1 0 2一组,三段的和依次是3,2,3;第二种是3|2 1|0 2|,3单独一组,2和1一组,0 2一组,三段的和依次是3,3, 2;第三种是3|2 1 0|2,3单独一组,2 1 0一组,0单独一组,三段的和依次是3 3 2。

思路

 这道题一个基本的思路就是枚举3段的断点p和q,然后求出来3段的和S1, S2和S3。然后判断S1,S2和S3是不是满足题目要求,也就是相差不超过1。如果满足条件就给答案累加1。因为这里S1,S2和S3都是部分和,所以可能用前缀和来计算。但是在此之前,我们需要一个函数来判断三段和是否满足条件,如果满足条件就让结果+1。伪代码如下:

Ok(S1,S2,S3):
If |S1 - S2| <= 1 and |S1 - S3| <= 1 and |S2 - S3| <= 1
    return true
return false

 然后我们预处理前缀和,以及进行枚举。伪代码如下:

//预处理前缀和
S[0] = 0
For i = 1...N
    S[i] = S[i - 1] + A[i]
//枚举+判断
Ans = 0
For p = 1...N-2
    For q = p+1...N-1
        S1 = S[p]

 上面这个伪代码预处理前缀和的复杂度是O(N)。后面枚举pq的复杂度是O(N^2^)。对于确定的pq,判断三段和是不是满足条件是O(1)。所以整体复杂度是O(N^2)。至此,题目中70%的分数应该能拿到了,还有30%需要优化

优化

 优化的方法当然还是从枚举入手,我们假设只枚举q,也就是最后一段的断点。我们来分析一下这时候我们知道哪些信息,距离我们要的答案还有多远。

 看上图,假设A数组是[3, 2, 1, 0, 2],然后我们枚举q=N-1,也就是第三段只包含A[N]=2这一个数。在q已经确定的情况下,可以知道S3的值。比如上面的例子中S3=2。根据题目要求S1、S2和S3的差不能超过1。所以对于一个合法的切分方案,S1的取值只可能是S3-1, S3, S3+1三种,也就是1,2,3  但是由于S1+S2+S3的和是整个数组的和,也就是8。所以S1的三种取值不见得都能成立。比如S1=1这种情况,由于S3=2是确定的,所以S2一定等于8-1-2=5。这是S2与S3相差超过1,不符合题目要求。所以S1=1这种情况不成立。同理S1=2也是不成立的。但是S1=3是成立的,因为这时S2的值是8-3-2=3。S2与S1和S3相差都不超过1  在S[1], S[2]和S[3]三个前缀和中,有几个的值是3。因为每有一个前缀和的值是3,都等价于找到了一种满足条件的切分方案:我们把这个前缀作为第一段,它的和等于3;剩下的就是第二段,它的和一定是3

 实际例子中我们可以看上图,绿色的数组是前缀和。S[1], S[2], S[3]分别是3,5,6,只有S[1]=3。所以q=N-1这种情况下,只有一种切分方案:3|2 1 0|2  上面是q=N-1的情况,我们再枚举q=N-2的情况,如下图:

 S3还是等于2。S1的可能取值还是S3-1,S3,S3+1,也就是1,2,3。其中只有S1=3时,S2的值满足题目要求。所以我们的问题变成S[0]和S[1]中,有几个前缀和等于3?

 因为前缀和S[1]=3, S[2]=5,所以还是只有S[1]=3一个解。于是q=N-2这种情况下,也只有一种切分方案:3|2 1|0 2  最后一种情况是q=N-3的时候:

 这时S3值是3。于是S1的取值范围是S3-1, S3, S3+1,也就是2, 3, 4。S1=2是成立的,因为这时S2=8-2-3=3,{2, 3, 3}相差都不超过1。S1=3也是成立的,因为这时S2=8-3-3=2,{3, 2, 3}相差都不超过1。S1=4是不成立的。于是我们的问题变成,前缀和S[0]中,有几个前缀和的值是2,有几个前缀和的值是3

 这时只有S[1]=3一个前缀和满足条件,所以q=N-3时,只有一组划分方法:3|2|1 0 2  上面我们就把样例的3种划分方法都求出来了。我们回顾一下上面的思路,基本就是从N-1到2枚举q,对于每一个q,我们都要求一类问题的解:  q = N-1时,前缀和S[1], S[2], … S[N-2]中有几个前缀和的值是X?(这里X可能是S3-1, S3, S3+1)  q = N-2时,前缀和S[1], S[2], … S[N-3]中有几个前缀和的值是X?(这里X可能是S3-1, S3, S3+1) …  q = 2时,前缀和S[1]中有几个前缀和的值是X?(这里X可能是S3-1, S3, S3+1)  当然上面枚举q的过程中S3的值会变化,另外注意我们关心的前缀和集合也在变短。  对于这一类问题,就是一堆前缀和中,有几个X,我们当然可以用哈希表来实现。使得每次询问的复杂度都是O(1)的。具体来说,我们可以用unordered_map<long long, int> cnt来保存每个值出现了几次,例如cnt[3]表示前缀和是3的有几个。注意这里key的类型是long long,因为前缀和可能超过int范围

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
int n,a[100001];
long long s[100001],ans = 0;
unordered_map<long long,int> cnt;

bool ok(long long s1,long long s2,long long s3)
{
    if(abs(s1 - s2) <= 1 && abs(s1 - s3) <= 1 && abs(s2 - s3) <= 1)
        return true;
    return false;
}

int main()
{
    cin >> n;
    s[0] = 0;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
        if(i < n)
            cnt[s[i]]++;
    }
    long long s3 = 0;
    for(int q = n - 1;q >= 2;q--)
    {
        s3 += a[q + 1];
        cnt[s[q]]--;
        for(long long s1 = s3 - 1;s1 <= s3 + 1;s1++)
        {
            long long s2 = s[n] - s1 - s3;
            if(ok(s1,s2,s3))
                ans += cnt[s1];
        } 
    }
    cout << ans;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

51 Nod 1007 正整数分组【类01背包】

1007 正整数分组 基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题 将一堆正整数分为2组,要求2组的和相差最小。 例如:1...

2787
来自专栏应兆康的专栏

100个Numpy练习【3】

Numpy是Python做数据分析必须掌握的基础库之一,非常适合刚学习完Numpy基础的同学,完成以下习题可以帮助你更好的掌握这个基础库。

4529
来自专栏Script Boy (CN-SIMO)

Java中随机数的产生方式与原理

查阅随机数相关资料,特做整理 首先说一下java中产生随机数的几种方式 在j2se中我们可以使用Math.random()方法来产生一个随机数,这个产生的随机数...

2430
来自专栏算法channel

Tensorflow|Tensor, 与Numpy比较,Constant

本教程参考stanford.edu-cs20si 01 Operations分类预览 ? 02 Tensor 1 0-d tensor, or "scala...

3967
来自专栏极客猴

Django 学习笔记之模型高级用法(下)

除了抽象模型,在模型中定义的字段都会成为表中的列。如果我们需要给模型指定其他一些信息,例如排序方式、数据库表名等,就需要用到 Meta。Meta 是一个可选的类...

892
来自专栏小樱的经验随笔

Vijos P1116 一元三次方程求解【多解,暴力,二分】

一元三次方程求解 描述 有形如:ax^3+bx^2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d 均为实数),并约定该方程存在三...

36012
来自专栏计算机视觉与深度学习基础

Leetcode 190 Reverse Bits

Reverse bits of a given 32 bits unsigned integer. For example, given input 432...

20910
来自专栏应兆康的专栏

100个Numpy练习【3】

翻译:YingJoy 网址: https://www.yingjoy.cn/ 来源: https://github.com/rougier/numpy-100...

40810
来自专栏逆向技术

逆向知识十三讲,汇编中数组的表现形式,以及还原数组

            逆向知识十三讲,汇编中数组的表现形式,以及还原数组 讲解数组之前,要了解数组的特性 1.数据具有连续性 2.数据类型相同 比如:   i...

2007
来自专栏简书专栏

基于tensorflow的一元一次方程回归预测

安装tensorflow命令:pip install tensorflow 下面一段代码能够成功运行,则说明安装tensorflow环境成功。

964

扫码关注云+社区