Codeforces Round 997 (Div. 2)

A

求的是 perimeter, 看成 area 了。

一道 A 卡了 26 min

B

思路跟答案完全不一样。

C

用样例构造答案过了。没看正解

D

做了很久，推了个式子最后发现不能用。

正难则反，考虑用 $\frac {n*(n+1)} 2$ 来减掉不合法的方案数。

假设一个连续子数组中 $\leq x$ 的数为 $-1$ , $>x$ 的数为 $1$ 。

那么如果这个连续子数组的和为 0，这个数组就是一个不合法数组。

首先这么构造一定排除了奇数。对于偶数来讲，会把 $x$ 正好卡到 $\frac {len} 2$ 的位置，且 $\frac{len} 2 + 1$ 正好是 $>x$ 的数。

然后枚举 $x$ ，维护前缀和快速求 $s_{j\sim i}=0$ 的数量。

注意对于 [1, 2, 6, 6] 这个不合法数组会在 $2\leq x\leq 6$ 时各被算一遍答案。

我们考虑只在遇到 $a_i=x$ 时再添加前缀和。

这样枚举到区间和为 0 的，一定就包含了 $x$ ，且 $x$ 是 -1 中的最大元素，就一定保证这个数是被按照 $x$ 来计数的。

参考题解 : Codeforces Round 997 (Div. 2) - maburb - 博客园

void solve(){
    int n;
    cin >> n;

    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    int ans = n * (n + 1) / 2;
    for(int x = 1; x <= 10; x ++) {
        vector<int> sum(n + 1);
        for(int i = 1; i <= n; i ++) {
            sum[i] = sum[i - 1] + (a[i] <= x ? -1 : 1);
        }

        vector<int> cnt(2 * n + 1);
        for(int i = 1, j = 0; i <= n; i ++) {
            if(a[i] == x) {
                while(j < i) {
                    cnt[sum[j] + n] ++;
                    j ++;
                }
            }
            ans -= cnt[sum[i] + n];
        }
    }

    cout << ans << '\n';
}

2025-01-17 22-33-03 div2_哔哩哔哩_bilibili