CF2123C Prefix Min and Suffix Max

Tag：前缀

题目描述

给定一个由互不相同的整数组成的数组 a。

在每次操作中，你可以选择以下两种操作之一：

选择 a 的一个非空前缀\(^{\text{∗}}\)，并将其替换为该前缀的最小值，或
选择 a 的一个非空后缀\(^{\text{†}}\)，并将其替换为该后缀的最大值。

注意，你可以选择整个数组 a 作为前缀或后缀。

对于数组中的每个元素 \(a_i\)，判断是否存在一系列操作可以将 a 转换为 \(a_i\)，即，使数组 a 仅包含一个元素 \(a_i\)。将答案输出为一个长度为 n 的二进制字符串，其中第 i 个字符为 1 表示存在将 a 转换为 \(a_i\) 的操作序列，否则为 0。

\(^{\text{∗}}\)前缀指的是数组的前 k 个元素组成的子数组，其中 k 为某个整数。

\(^{\text{†}}\)后缀指的是数组的后 k 个元素组成的子数组，其中 k 为某个整数。

数据说明：

\(1\leq t \leq 10^4\)
\(1\leq n\leq 2\cdot 10^5\)
\(1\leq a_i \leq 10^6\)
\(\sum n \leq 2 \cdot 10^5\)

分析

虽然，题目里面并没有限制我们操作的次数。但是可以很显然地观察到，对前缀无论做了多少次操作，都可以等价变换成执行了一次操作。

后缀也是同理的。

那么在前缀的操作中，如果我们想把第 \(i\) 个数字留下来，那么这个数字必须是前 \(i\) 个数字里的最小值。后缀也是同理。

假设第 \(i\) 个数字是前缀最大的，那么我们操作一下使得第一个数字是 \(a_i\)。现在我们直接对后缀操作一下，变成了某个我们不知道的数字 \(x\)。那么对于 \(\{a_i,x\}\) 这个数组来说，前缀操作和后缀操作一定有一个能只留下 \(a_i\)。然后又是后缀同理。

因此我们维护前缀 \(\min\) 和后缀 \(\max\)。只要 \(a_i\) 等于其中一个就必定可以留下来。

代码实现

void NeverSayNever() {
    int n; cin >> n;
    vector<int> vec(n);
    for(auto &x : vec) cin >> x;
    vector<int> pre(n), suf(n);
    pre[0] = vec[0],suf[n - 1] = vec[n - 1];
    for (int i = 1; i < n; ++i) pre[i] = min(pre[i - 1], vec[i]);
    for (int i = n - 2; i >= 0; --i) suf[i] = max(suf[i + 1], vec[i]);
    string ans;
    for (int i = 0; i < n; ++i) {
        if (pre[i] == vec[i] || suf[i] == vec[i]) ans.push_back('1');
        else ans.push_back('0');
    }
    cout << ans << endl;
}

日志

本页面创建于 2024/7/4 23:56