题解：CF2043C Sums on Segments

题意

给你一个长度为

n

的数组

a

，满足

a

中有且仅有一个不为

1

也不为

-1

的数（以下简称特殊的值），剩余的数都是

1

或

-1

。求所有可能的子区间的和的值（下文简称答案）。从小到大一次输出每一个值，每个值只输出一遍。

题解

首先，我们发现，如果把那个特殊的值考虑进来不那么好搞，而又“有且仅有一个不为

1

也不为

-1

的数”，于是我们考虑把

a

数组从那个特殊的值那里分成两段，他左边的成一段，他右边的另成一段，他自己提出来。然后我们就从考虑一个大问题分成了三个子问题：左边区间的所有可能的子区间的和的值，右边区间所有可能的子区间的和的值，包含特殊的值的所有可能的子区间的和的值。

左边区间 & 右边区间

这里有个不怎么显然的结论：在一个值域为

\{1,-1\}

的数组里，设他的最大子段和是

a

，最小子段和是

b

。那么，有且仅有属于

[b,a] \cap \mathbb{Z}

的数是答案，且这个集合里的每一个数都是答案。有了这个结论，左边区间的答案和右边区间的答案都好求了，但是，结论固然得证，所以我们就来证这个结论。

我们找到能造成最大子段和

a

的区间，然后，将它分成

a

个和为

1

的子区间，能够证明一定有分法。然后，如果我们想得到和为

a - 1

的子区间，我们只需要从左边或者右边去掉一个和为

1

的子区间就能得到。对于

a - 2,a - 3, \cdots 1

都可以用这种方法得出。于是我们就证得属于

[1,a] \cap \mathbb{Z}

的数一定是答案。如法炮制，我们也能证出属于

[b,-1] \cap \mathbb{Z}

也一定是答案。最后并上一个

{0}

，就得到了

[b,a] \cap \mathbb{Z}

。这样我们就成功的求出了左边区间和右边区间的答案。

包含特殊值的区间

也是如法炮制，不过因为要包含特殊值，所以就不能简单的求最大（小）字段和，要求最大（小）前（后）缀和。对于左边区间就是后缀，对于右边，就是前缀。然后我们设左边的最大后缀和是

max_{1}

，最小后缀和是

min_{1}

。右边的最大前缀和是

max_{2}

，最小前缀和是

min_{2}

，那么包含特殊值的区间的答案区间就是

[min_{1} + min_{2} + val,max_{1} + max_{2} + val] \cap \mathbb{Z}

。这里

val

指特殊值。

code

CPP

#include<bits/extc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 5;
int n,val,pos,sum;
int max1,min1,max2,min2;
int a[maxn],dp1[maxn],dp2[maxn];
void solve()
{
    cin >> n;
    pos = val = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] != 1 && a[i] != -1)
        {
            val = a[i];
            pos = i;
        }
    }
    max1 = min1 = 0;
    fill(dp1 + 1,dp1 + n + 1,0);
    fill(dp2 + 1,dp2 + n + 1,0);
    for (int i = 1; i <= pos - 1; i++)   
    {
        dp1[i] = max(dp1[i - 1] + a[i],0ll);
        max1 = max(max1,dp1[i]);//求左边区间的最大子段和
        dp2[i] = min(dp2[i - 1] + a[i],0ll);
        min1 = min(min1,dp2[i]);//求左边区间的最小子段和
    }
    max2 = min2 = 0;
    fill(dp1 + 1,dp1 + n + 1,0);
    fill(dp2 + 1,dp2 + n + 1,0);
    for (int i = pos + 1; i <= n; i++)
    {
        dp1[i] = max(dp1[i - 1] + a[i],0ll);
        max2 = max(max2,dp1[i]);//求右边区间的最大
        dp2[i] = min(dp2[i - 1] + a[i],0ll);
        min2 = min(min2,dp2[i]);//求右边区间的最小
    }
    set<int>ans;
    for (int i = min(min1,min2); i <= max(max1,max2); i++)
        ans.insert(i);//先把不包含val的值加入
    max1 = min1 = sum = 0;
    for (int i = pos - 1; i >= 1; i--)
    {
        sum += a[i];
        max1 = max(max1,sum);//求左边区间的最大后缀和
        min1 = min(min1,sum);//求左边区间的最小后缀和
    }
    max2 = min2 = sum = 0;
    for (int i = pos + 1; i <= n; i++)
    {
        sum += a[i];
        max2 = max(max2,sum);//如法炮制
        min2 = min(min2,sum);
    }
    for (int i = (min1 + min2); i <= (max1 + max2); i++)
        ans.insert(val + i);//记录答案
    cout << ans.size() << endl;
    for (auto i : ans)
        cout << i << " ";
    cout << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

upd:更新几处笔误

题解：CF2043C Sums on Segments

文章操作

题意

题解

左边区间 & 右边区间

包含特殊值的区间

code

相关推荐

评论

题解：CF2043C Sums on Segments