CF1995C Squaring 题解

题目链接：Squaring

题意：

多组数据，给定长度为 $n$ 的序列 $a$

每次可以让一个 $a_i \gets a_i^2$ ，其中 $1 \le i \le n$ 。

求使得序列 $a$ 单调不降的最小操作数。

数据范围：

$1 \le \sum n \le 2\times 10^5,~1 \le a_i \le 10^6$ 。

显然我们不能直接计算出操作后的数有多大

但是可以发现，如果 $a_i < a_{i+1}$ ，后者的操作数肯定是不超过前者的

因此我们可以计算每个位置相对于前者的增量，然后求一遍前缀和就可以了

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e5 + 15))

int a[N], op[N];
void solve()
{
    int n; cin >> n;
    rep(i, 1, n) { cin >> a[i], op[i] = 0; }
    rep(i, 2, n) if(a[i - 1] > 1 && a[i] == 1)
        return cout << "-1\n", void(0);
    rep(i, 2, n)
    {
        int x = a[i - 1], y = a[i], d = 0;
        while(x != 1 && x * x <= y) { --d, x *= x; }
        while(y < x) { ++d, y *= y; }
        up(op[i], max(0ll, op[i - 1] + d));
    }
    int res = 0;
    rep(i, 1, n) res += op[i];
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}

---

题外话：

下次打 CodeForces 得早睡。