题解 CF1550C. Manhattan Subarrays (思维)

来源:Educational Codeforces Round 111 (Rated for Div. 2)

不难但很好的思维题

\(d(p,q)\)\(p,q\) 两点之间的曼哈顿距离

给定三个点,如果 \(d(p,r) = d(p,q) + d(q,r)\) 则三个点是 坏三元组

在给定的序列中每个点都是 \((b_i,i)\) 请判断序列中有多少个好子序列,长度为 \(1\)\(2\) 也为好序列

\(i < j < k\) 的情况下, \(d(p,r) = d(p,q) + d(q,r)\) 可以直接转化为:\(|b_i - b_k| = |b_i - b_j| + |b_j - b_k|\)

正如 \(i < j < k\) 一样,如果 \(b_i \le b_j \le b_k\) 或者 \(b_i \ge b_j \ge b_k\) 时肯定是坏序列了

所以我们可以直接遍历判断情况

代码
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        int n;
        cin >> n;
        vectora(n);
        auto check = [&](int L, int R) {
            for (int i = L; i <= R; ++i)for (int j = i + 1; j <= R; ++j)
                    for (int k = j + 1; k <= R; ++k) {
                        if (a[i] <= a[j] and a[j] <= a[k]) return 0;
                        if (a[i] >= a[j] and a[j] >= a[k]) return 0;
                    }
            return 1;
        };
        int ans = 0;
        for (int &x : a) cin >> x;
        for (int i = 0; i < n; ++i)
            for (int j = i; j < n; ++j)
                if (check(i, j)) ans += 1;
                else break;
        cout << ans << "\n";
    }
}

题解 CF1550C. Manhattan Subarrays (思维)

上一篇:div 实现漏斗图


下一篇:接口三要素类封装