Codeforces Round 987 (Div. 2)题解 A~D

A- Penchick and Modern Monument

由于给定的数是非递增的，所以 $h_{[}i]\ge h[i+1]$，如果 $h[i]>h[i+1]$ 那么二者至少要改其一。因为最终要求的数是非递减的，所以最终数组内都是同一种数的方案是可行的。枚举最后会成为数组中的哪一个数即可。

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

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


    int ans = INF;
    for (int i = 1; i <= n; i++) {
        int sum = 0;
         
        for (int j = 1; j <= n; j++) 
            if (h[j] != h[i]) sum ++;
         
        ans = min(sum, ans);
    }

    cout << ans << endl;
}

B- Penchick and Satay Sticks

假设 $1\sim i-1$ 已经放好了，如果 $p[i]\ne i$ 的话，现在要把 $i$ 位置放好，当且仅当 $p[i+1]=i$ 并且 $p[i]=i+1$ 时才能放好。

void solve () {
    int n;
    cin >> n;
    vector <int> p(n + 1);

    for (int i = 1; i <= n; i++) cin >> p[i];


    for (int i = 1; i <= n; i++) {
        if (p[i] == i) continue;

        // 找到 i 在哪
        int pos = -1;
        for (int j = i + 1; j <= n; j++) {
            if (p[j] == i) {
                pos = j;
                break;
            }
        }

        if (p[i] - p[pos] == 1) {
            swap (p[i], p[pos]);
        } else {
            cout << "NO" << endl;
            return;
        }
    }

    cout << "YES" << endl;
}

C-Penchick and BBQ Buns

这是一道构造题，先思考一个问题，是否存在 $(x,y)$ 使得 $x,y,x+y$ 都是平方数？答案是勾股数。

再思考一个问题，是否存在 $(x,y,z)$ 使得 $x,y,z,x+y,y+z,x+y+z$ 都是平方数？我打了个表发现是没有的。

回到这个问题，也就是说，最多我们用三份相同的调料包，不可能用四份及以上的调料包。

当 $n$ 是偶数的时候，显然可以相邻地放两个相同的数。

当 $n$ 是奇数的时候，最小的一组勾股数是 $9,16,25$ 至少需要 $n\ge 26$ 时才能出现。

当 $n$ 是大于 $26$ 的奇数，我们可以在 $1,10,26$ 处放同一个数，然后再在 $23,27$ 处放同一个数，剩下的数就一直相邻放即可。

当 $n$ 是小于 $26$ 的奇数，不存在答案。

void solve () {
    int n;
    cin >> n;
    if (n < 27) {
        if (n & 1) cout << "-1" << endl;
        else {
            for (int i = 1; i <= n; i += 2) {
                cout << i << ' ' << i << ' ';
            }
            cout << endl;
        }
    } else {
        vector <int> a(n + 1, 0);

        if (n & 1) {
            a[1] = 1;
            a[10] = 1;
            a[26] = 1;
            a[23] = 2;
            a[27] = 2;
            int bnt = 3;

            for (int i = 2; i <= n; ) {
                if (a[i]) {
                    i ++;
                    continue;
                }
                a[i] = bnt;
                a[i + 1] = bnt;
                bnt ++;
                i += 2;
            }

            for (int i = 28; i <= n; i += 2) {
                a[i] = bnt;
                a[i + 1] = bnt;
                bnt ++;
            }

            for (int i = 1; i <= n; i++) {
                cout << a[i] << ' ';
            }
            cout << endl;
        } else {
            for (int i = 1; i <= n; i += 2) {
                cout << i << ' ' << i << ' ';
            }
            cout << endl;
        }
    }
}

D-Penchick and Desert Rabbit

兔子可以往后跳到比它当前更低的树，也可以往前跳到当前比它更高的树。

这预示着，操作是可逆的、互通的。

设集合 $A$ 是兔子在 $i$ 树能跳到的所有树的集合，显然从 $A$ 内的任意一棵树都一定能跳到 $i$ 树。

现在的问题就是，我们怎样地遍历才能不超时、不缺漏地合并所有集合？

让我们推演一下：

对于一棵最高的树 $p_1$，它可以直接跳到它后面所有的树上，所以直接遍历即可。

然后找到次高的树 $p_2$，需要判断是否这棵树能跳到最高的树后面，如果可以的话，那么从 $p_2\sim p_1$ 都可以合并。

不断重复这个过程，又因为每个数只会被合并一次，所以时间是 $O(n)$ 的。

如何找到最高、次高、$\cdots$ 的位置？由于值域是 $1\sim n$，所以可以开一个 $O(n)$ 的桶。

看似上面一直说合并集合，实际上我们可以发现，当前最高的树只能往右边跳，我们只要维护上一个集合的左端点，以及维护上一个集合的最小值即可。

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

    vector <int> a(n + 1);
    vector <int> v[n + 1]; // 桶排序
    vector <int> ans (n + 1); // 用来计答案

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

    int l = n + 1, minn = INF; // 最开始上个集合的左端点是 n + 1，最小值无穷大。

    for (int i = n; i >= 1; i--) {

        for (int j = v[i].size() - 1; j >= 0; j--) { // 遍历所有大小为 i 的桶
            if (v[i][j] >= l) continue; // 如果这个值在上个集合内部就跳过
            ans[v[i][j]] = i; // 首先将答案初始化为自身

            if (i > minn) { // 如果当前的值大于上个集合内部的最小值
                for (int k = v[i][j]; k < l; k++) { // 那么它能去的最大值就是上个集合的最大值
                    ans[k] = ans[l]; // ans[l] 是上个集合内最大值，上个集合内所有数的答案都是 ans[l]
                    minn = min(minn, a[k]); // 更新最小值
                }
                l = v[i][j]; // 更新左端点
            } else {
                int temp = INF; // 如果无法访问到上一个集合内部
                for (int k = v[i][j]; k < l; k++) { // 那么后续的集合肯定无法访问到上一个集合内部
                    ans[k] = ans[v[i][j]]; // 此时新开一个集合
                    temp = min(temp, a[k]);
                }
                minn = temp; 
                l = v[i][j];
            }
        }

    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }

    cout << endl;

}