来源: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";
}
}