数列
问题描述
给你一个长度为N的由0和1组成的整数序列：A=(A1,A2,⋯,AN)。
你可以选择是否进行一个操作。该操作为选择一个区间（l,r) ，使得区间的0变成1，1变成0。
改变后的序列称作A’
我们设f(A)为整数序列A中1的个数。想问你f(A')有多少个取值的可能
输入
第一行一个整数n表示序列的长度。（1≤N≤3×10^5）
第二行n个数，为0或1
输出
输出可以操作一次或不操作后的序列f(A')有多少种取值可能。
输入例子 1 输出例子 1
4 4
0 1 1 0
输入例子 2 输出例子 2
5 6
0 0 0 0 0
输入例子 3 输出例子 3
6 0 1 0 1 0 1 3
提示
对于样例一：
翻转(2,3)区间，f(A')=0
翻转(2,2)区间，f(A')=1
不进行操作， f(A')=2
翻转(1,1)区间，f(A')=3
一共4种可能
提示
首先需要证明对于所有f(A’)的取值是连续的。
我们可以考虑翻转一个区间(l,r),其值为x。
考虑扩展该区间，即r+1或l-1，发现扩展的那位如果是1，那么扩展后区间为x-1如果是0则x+1
同理考虑缩小该区间，则与之前的情况相反。
我们能发现该值只会+1或-1，那么可以证明f(A’)的取值是连续的。
所以必然存在可能使得有翻转区间后f(A’)的最小值，通过滑动区间变为最大值。
那么该问题可以进行转换成翻转一个区间使得1的个数最多和最少。
考虑ai为0，翻转后f(A’)+1，为1 f(A’)-1，
所以构造b序列为ai为0时bi为1，为1时bi为-1
然后从前往后扫一遍，构造bi的前缀和s求出Si-Sj最大max和最小min。（j<i）
答案为max-min+1
官方答案
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n;
vector<int> s(n+1);
int mx=0,mn=0;
set<int> f;
f.insert(0); //记录前缀的前缀和。
for (int i=1;i<=n;++i){
int x;cin>>x;
s[i]=s[i-1] + (x ? -1 : 1); //构造的b的前缀和
mx=max(mx , s[i] - *f.begin()); //最大值为si减去之前sj的最小值
mn=min(mn , s[i] - *(--f.end())); //最小值为si减去之前sj的最大值
f.insert(s[i]);
}
cout<< mx - mn + 1;
}
标签：周赛,OJ,int,前缀,数列,序列,例子,区间,翻转 From： https://www.cnblogs.com/hihopkc/p/16844403.html