定义数组 $s$ 表示花的种类。其中，玫瑰和牡丹分别表示为 $-1$ 和 $1$，则 $\lvert \sum\limits^{n}_{i=1} s_i \rvert$ 即为花坛的观赏度。

不难发现，对于区间 $[l,r]$ 进行一次操作，区间贡献会变成其和的相反数，等价于 $s$ 的总和减去两倍区间 $[l,r]$ 的和。 所以我们分别计算 $s$ 中子序列的最大值和最小值，以两值为边界枚举一遍，中间用 set 统计答案即可。

Python

from collections import defaultdict

n = int(input())
a = [int(x) if x != "0" else -1 for x in input().split()]
s = sum(a)
max_sum = 0
min_sum = 0
left = 0
right = 0
res = set()

for i in range(n):
    max_sum = max(max_sum + a[i], a[i])
    min_sum = min(min_sum + a[i], a[i])
    left = min(left, min_sum)
    right = max(right, max_sum)

for i in range(left, right+1):
    res.add(abs(s - 2*i))

print(len(res))

java

import java.util.HashSet;
import java.util.Scanner;

/**
 * @Author: sj
 * @Date: 2024-08-25
 * @Description:
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] flowers = new int[n];
        int sum = 0;
        for(int i = 0; i < n; i++){
            int a = scanner.nextInt();
            if(a == 0){
                a = -1;
            }
            flowers[i] = a;
            sum += a;
        }
        int[] dp_max = new int[n + 1];
        int[] dp_min = new int[n + 1];
        dp_min[0] = 0;
        dp_max[0] = 0;
        for(int i = 0; i < n; i++){
            dp_max[i + 1] = Math.max(dp_max[i] + flowers[i], flowers[i]);
            dp_min[i + 1] = Math.min(dp_min[i] + flowers[i], flowers[i]);
        }
        int max = dp_max[1];
        int min = dp_min[1];
        for(int i = 2; i < n; i++){
            if(dp_max[i] > max){
                max = dp_max[i];
            }
        }
        for(int i = 2; i < n; i++){
            if(dp_min[i] < min){
                min = dp_min[i];
            }
        }
        HashSet set = new HashSet();
        for(int i = min; i <= max; i++){
            set.add(Math.abs(sum - 2 * i));
        }
        System.out.println(set.size());

    }
}

C++

#include<bits/stdc++.h>
using namespace std;
int a[100001],dp[100001][2]={0};
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {cin>>a[i];
    dp[i][0]=dp[i-1][0]+(a[i]==0);
    dp[i][1]=dp[i-1][1]+(a[i]==1);
    }
    unordered_set<int> val;
    for(int l=1;l<=n;l++){
        for(int r=l;r<=n;r++){
            int temp_val,temp0,temp1;
            if(r==l){
                if(a[r]==1){
                    temp_val=abs((dp[n][0]+1)-(dp[n][1]-1));
                }
                else{
                    temp_val=abs((dp[n][0]-1)-(dp[n][1]+1));
                }
            }
            else{
                temp0=dp[l-1][0]+dp[n][0]-dp[r][0]+(dp[r][1]-dp[l-1][1]);
                temp1=dp[l-1][1]+dp[n][1]-dp[r][1]+(dp[r][0]-dp[l-1][0]);
                temp_val=abs(temp1-temp0);
            }
            val.insert(temp_val);

        }
    }
    cout<<val.size()
;
}

会员可以从《提交记录》的页面查看其他人的AC代码供参考。

题目描述

小红喜欢玫瑰和牡丹，小红在他的花坛中种了 $n$ 盆花，每盆花要么是玫瑰，要么是牡丹，并按顺序从左往右依次编号，从 1 到 $n$。花坛的观赏度定义为玫瑰与牡丹的盆数之差的绝对值。现在定义一种操作：选取一个连续的区间 $[1, r]$，将编号从 1 到编号 $r$ 的花盆中的玫瑰替换成牡丹，将牡丹替换成玫瑰。

小红不关心观赏度的高低，而是关心经过至多一次这样的操作，花坛可能出现的观赏度的种类数。请问经过至多一次这样的操作，小红的花坛一共有多少种不同的观赏度？

输入描述

输入共两行：

• 第一行是一个整数 $n$ （$1 \leq n \leq 100,000$），表示花坛中的花盆数量。
• 第二行是 $n$ 个数字，每个数字表示花的种类，0 表示玫瑰，1 表示牡丹。

输出描述

输出一行，一个数字，表示经过至多一次操作后，花坛一共有多少种不同的观赏度。

样例输入输出

2
0 1

2

4
0 1 1 0

3

说明

【样例 #1】

不操作，观赏度为 $0$，

操作区间 $[1, 1]$，观赏度为 $2$，

操作区间 $[2, 2]$，观赏度为 $2$，

操作区间 $[1, 2]$，观赏度为 $0$，

共有 $2$ 种不同的观赏度。