题解：P17717 [LAOI Round 21] 拼积木 / block

wsy_I · 2026-10-21 13:27:27 · 题解

来一个比较完整详细的题解吧。

正解

首先，假如 t 变成了 1，到下一个位置 x 就会变成 a_x，也就相当于直接从 a_x 开始做。

因此我们定义一个极小的区间 [l,r]，其含义为：[l,r] 这个区间中计算出来的 t，当且仅当计算到位置 r 的时候值为 1 的一个区间。那么我们容易发现，每一个合法的区间都是有若干极小的区间构成的。

假设我们现在已经求出了对于所有 l 的一个极小区间，设其右端点为 nxt_l，那么可以设 dp_i 表示 i 为右端点合法的区间数，有：

也就是统计上一个极小区间对于 nxt_i 为结尾的贡献，加上 [i,nxt_i] 这个区间的贡献，感觉这一部分比较显然。

那么如何求出所有极小区间呢？暴力即可！为什么这是对的？不妨分类讨论。

这里单调递减，所以我们分类讨论。首先是长度 <2 的一个极小区间，这些极小区间的代价之和显然是 O(n) 的。除此之外考虑长度 >2 的极小区间个数，也就是一步没有被除成 1，b_i 至少为 b_{i+1} 的两倍。由于序列单调递减这个性质很好，所以最多只会有 \log V 个这样的区间。所以这一部分的贡献为 O(n\log V)。

有总时间复杂度 O(n\log V)，并且显然跑不满，因此可以轻易通过。空间复杂度 O(n)。

代码

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++ )
#define per(i, l, r) for(int i = (l); i >= (r); i -- )
#define frein(s) freopen(s, "r", stdin)
#define freout(s) freopen(s, "w", stdout)
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e6 + 5;
int T, n, a[N], nxt[N], dp[N];

signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while(T -- ) {
        cin >> n;
        rep(i, 1, n) cin >> a[i];
        rep(i, 0, n) nxt[i] = dp[i] = 0;
        rep(i, 1, n) {
            int t = a[i];
            if(a[i] == 1) {
                nxt[i] = i;
                continue;;
            }
            rep(j, i + 1, n) {
                t = max(t, a[j]) / min(t, a[j]);
                if(t == 1) {
                    nxt[i] = j;
                    break;
                }
            }
        }
        int ans = 0;
        rep(i, 1, n) {
            dp[nxt[i]] += dp[i - 1] + 1; 
            ans += dp[i];
        }
        cout << ans << endl;
    }
    return 0;
} 

部分分解法

\sum n\leq 5\times 10^2

枚举每一个区间，从左到右扫描，依次判断是否为合法区间。时间复杂度 O(n^3)。

\sum n\leq 5\times 10^3

对上一个做法的略微优化。我们枚举左端点，然后从左向右扫描右端点，假如遇到 t=1 的情况就形成一个合法区间。

相较于上一个做法避免了计算重复的前缀，因此时间复杂度优化到了 O(n^2)。

特殊性质 A