题解：CF2171H Shiori Miyagi and Maximum Array Score

梨花诗 · 2026-04-28 17:29:58 · 题解

感觉像简单一点的士兵。

首先，很显然的朴素 DP 状态就是 f_{i,j}，表示填完 1 到 i 且 a_i = j 时的最大得分，这个复杂度是 \mathcal{O}(nm) 的。

考虑怎么优化，我们发现转移 i \to i + 1 的时候，真正变化的点并不多。

具体分析一下：首先 a_i 显然可以写成 i + k\ (k \ge 0)。题目要求的条件是 i^x \mid (i + k)，此时若要产生收益（即 x \ge 1），那么 k 必须是 i 的倍数，这就是个典型的调和级数。

但是现在的形式还是很丑陋，转移时存在一个整体右移的平移操作（理论上平衡树应该能做，但是太麻烦了且常数大，而且我也不会写）。那么根据刚才的灵感，我们可以重新设计状态，用 f_{i, k} 表示 a_i = i + k 时的最大值。

转移方程就变成了 f_{i,k} = \max\limits_{j \le k}(f_{i-1,j}) + \text{Cost}(i, i+k)。

此时，操作变成了一个区间取 \max 加上更新少量单点。但进一步观察发现：更新单点时，转移只需要查询前缀最大值，所以不用写区间取 \max 也是对的了。

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i ++ )
#define repf(i, a, b) for(int i = (a); i >= (b); i -- )
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
const int P = 998244353;
int n, m;
#define ls cur << 1
#define rs cur << 1 | 1
int t[N << 2];
void build(int cur, int l, int r)
{
    t[cur] = 0;
    if(l == r) return;
    int mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
}
inline int Cost(int b, int x)
{
    int res = 0;
    while(x % b == 0)
    {
        res ++;
        x /= b;
    }
    return res;
}
int query(int cur, int l, int r, int x, int y)
{
    if(x <= l && r <= y) return t[cur];
    int mid = l + r >> 1; int mx = 0;
    if(x <= mid) mx = query(ls, l, mid, x, y);
    if(y > mid) mx = max(mx, query(rs, mid + 1, r, x, y));
    return mx;
}
void modify(int cur, int l, int r, int x, int val)
{
    if(l == r)
    {
        t[cur] = max(t[cur], val); return;
    }
    int mid = l + r >> 1;
    if(x <= mid) modify(ls, l, mid, x, val);
    else modify(rs, mid + 1, r, x, val);
    t[cur] = max(t[ls], t[rs]);
}
int main()
{
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while(T -- )
    {
        cin >> n >> m; build(1, 0, m - n);
        rep(i, 2, n)
        {
            vector<pair<int, int> > p;
            for(int k = 0; k <= m - n; k += i)
            {
                int C = Cost(i, k + i) + query(1, 0, m - n, 0, k);
                p.push_back({k, C});
            }
            for(auto x : p) modify(1, 0, m - n, x.first, x.second);
        }
        cout << query(1, 0, m - n, 0, m) << '\n';
    }
    return 0;
}