「题解」CF1923D Slimes

Table of contents

• 题意
• 题解
• 代码

感觉比较好玩的一道题。

题意

有一排史莱姆，一个史莱姆能吃掉相邻的史莱姆当且仅当它的大小严格大于和它相邻的史莱姆。一个史莱姆吃掉另一个史莱姆后大小会加上被吃掉的史莱姆大小。求每个史莱姆最少经过多少次操作才能被吃掉。

link

题解

我们考虑一个史莱姆被吃掉的最优方案一定是把它前面或后面一段史莱姆合并成一个严格大于它草史莱姆然后把它吃掉。因为显然只有这些操作是有用的。

不难发现一段连续的史莱姆不能被合并成一个当且仅当这一段史莱姆大小都相等。否则一定有一个最大的史莱姆和一个比它小的史莱姆相邻，吃掉它之后就产生了一个严格大于其余史莱姆的史莱姆。

于是我们可以在前后分别二分这个连续段的长度。检查区间和只需要前缀和一下。检查一段大小是否都相等可以维护区间最大最小值看是否相等，但还有一个方法是考虑在 st 表合并两个区间的过程中，新的区间全相等当且仅当这两个区间分别全相等且两个区间中的元素也相等。这样可以剩下一倍常数。

整体复杂度 $O(n \log n)$。

代码

#include <bits/stdc++.h>

typedef long long ll;
const int MAX = 3e5 + 5;

ll n, T;
ll a[MAX], p[MAX];
bool st[25][MAX];

void build()
{
    for (int i = 1; i <= n; ++i) { st[0][i] = true; }
    for (int i = 1; (1 << i) <= n; ++i)
    {
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
        {
            st[i][j] = st[i - 1][j] and st[i - 1][j + (1 << (i - 1))] and a[j] == a[j + (1 << i) - 1];
        }
    }
}

bool qry(int l, int r)
{
    if (l == r) { return true; }
    int lg = log2(r - l + 1);
    return !(st[lg][l] and st[lg][r - (1 << lg) + 1] and a[l] == a[r]);
}

int search(int x)
{
    if (x != 1 and a[x - 1] > a[x]) { return 1; }
    if (x != n and a[x + 1] > a[x]) { return 1; }
    int l = 1, r = x - 1, ans = n + 1;
    while (l <= r)
    {
        int mid = l + ((r - l) >> 1);
        if (p[x - 1] - p[mid - 1] > a[x] and qry(mid, x - 1)) { ans = std::min(ans, x - mid); l = mid + 1; }
        else { r = mid - 1; }
    }
    l = x + 1, r = n;
    while (l <= r)
    {
        int mid = l + ((r - l) >> 1);
        if (p[mid] - p[x] > a[x] and qry(x + 1, mid)) { ans = std::min(ans, mid - x); r = mid - 1; }
        else { l = mid + 1; }
    }
    return ans == n + 1 ? -1 : ans;
}

void solve()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) { scanf("%lld", &a[i]); p[i] = a[i]; p[i] += p[i - 1]; }
    build();
    for (int i = 1; i <= n; ++i) { printf("%d ", search(i)); }
    printf("\n");
}

int main() { scanf("%lld", &T); while (T--) { solve(); } }