新生赛题解

A

由于序列单调不降，所以只要体力足够往下一列走就往走向下一列；否则，一直沿着当前列走直到体力不小于下一列所需的值。假设当前列还差体力值 $x$ 才能走到下一列，当前列的权值为 $y$ ，那么需要继续在当前列走 $\lceil x/y \rceil$ 次。 $\lceil x \rceil$ 表示对 $x$ 表示向上取整，模拟这个过程，直到走到第 $n$ 列时直接跳到最后一行，或者走到最后一行时停止即可。

时间复杂度为 $O(n)$ 。

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e6 + 10;
#define endl '\n'
int a[M], b[M], c[M];
void solve()
{
    int k, n;
    cin >> k >> n;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = a[1], x = 1, y = 1;//x，y分别表示当前所在行和列
    while (1)
    {
        // cout << x << ' ' << y << ' ' << ans << endl;
        if (x == k)//到达最后一行了直接退出
            break;
        if (y == n)//到达最后一列了，直接跳到最后一行
        {
            ans += (k - x) * a[n];
            break;
        }
        if (a[y + 1] - ans > 0)//不能直接走到下一列，只能先在当前列走
        {
            int t = min(k - x, (a[y + 1] - ans + a[y] - 1) / a[y]);//这里是在做向上取整
            ans += t * a[y];
            x += t;
            if (x == k)
                break;
            x++;
            y++;
            ans += a[y];
        }
        else//可以直接走到下一列
        {
            y++;
            x++;
            ans += a[y];
        }
    }
    cout << ans  << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}

B

由于每个数最多只有 $6$ 位，直接枚举交换哪两位复杂度是可以接受的，暴力即可。

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int M = 1e6 + 5;
const int mod = 1e9 + 7;
int a[M];
void solve()
{
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        string ans = s;
        int l = s.size();
        for (int i = 0; i < l; i++)
        {
            for (int j = i + 1; j < l; j++)
            {
                string t = s;
                swap(t[i], t[j]);
                ans = max(ans, t);
            }
        }
        sum += stoi(ans);//把字符串转换为整数的函数
    }
    cout << sum << endl;
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

C

题意没有弯弯绕绕，就是表面意思。对于 $i$ ，单独计算左右的贡献然后加起来即可。现在考虑左边的贡献应该如何计算，我们从 $i$ 出发，往左遍历，遇到不小于当前最大值的数字就把他加入，并将他更新为当前的最大值。

这样的策略是正确的，因为假设我们选择了一个下标 $j(1 \le j \le i)$ ， $a_j$ 是区间 $[i,j]$ 的最大值，那么对于该区间内的所有能选择的数，我们一定可以通过刚才描述的策略把他们选到，如果你遇到能选择的数却最不选择，得到的结果不会更优。（自己随便举几个例子）

现在的瓶颈在于原来的模拟是每一次 $O(n)$ 的，我们如果模拟 $n$ 次是不行的，我们需要快速计算当前字数左边中，离他最近且不低于他的数字所在的位置，这个是单调栈的模板，然后只需要做一次递推即可求解。右边的贡献计算同理。单调栈学习链接：https://www.luogu.com.cn/problem/P5788

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define endl '\n'
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int a[N];
pii b[N];
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<int> l(n + 2), r(n + 2);
    stack<pair<int, int>> p;
    // 左边最近的大于等于a[i]的下标
    for (int i = n; i >= 1; i--)
    {
        while (!p.empty() && a[i] >= p.top().first)
        {
            l[p.top().second] = i;
            p.pop();
        }
        p.push({a[i], i});
    }
    while (!p.empty())
        p.pop();
    // 右边最近的大于等于a[i]的下标
    for (int i = 1; i <= n; i++)
    {
        while (!p.empty() && a[i] >= p.top().first)
        {
            r[p.top().second] = i;
            p.pop();
        }
        p.push({a[i], i});
    }
    for (int i = n; i >= 1; --i)
        r[i] = r[r[i]] + 1;
    for (int i = 1; i <= n; ++i)
        l[i] = l[l[i]] + 1;
    for (int i = 1; i <= n; i++)
        cout << l[i] + r[i] - 1 << " ";
    cout << endl;
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

D

太难，略

E

首先把出现次数小于 $x$ 的数所在位置隔开，这些数字所在的区间一定不满足条件，于是原序列被划分成了若干个子段，每一段可以分开单独计算。

每个段中的数字，在整个数组出现的次数都不小于 $x$ ，而 $\sqrt{n} \leq x$ ，所以剩余的数的种类不会超过 $\sqrt{n}$ 种。

考虑模拟暴力过程，从当前端点开始，往后跳跃到当前数字后面第 $x$ 次出现的位置，如果发现跳跃的这一段位置中有新数字被加入，则对右端点取最大值并继续执行上述过程；否则直接停止，当前右端点就是满足条件的最小右端点。

如果新加入的数字后面已经不足 $x$ 个，直接判为 $-1$ 。

例如， $n=4,x=2$ ，序列为 $\{1,2,1,2,\}$ ，假设左端点为 $1$ ，右端点从 $1$ 更新为 $3$ ，此时发现新数字 $2$ 被加入，于是继续跳跃扩展右端点到 $4$ 。

而我们在跳跃过程中只关注每种数第一次出现的位置，然后进行跳跃，可以倒序枚举左端点，存储每个数出现的位置，用 set 维护当前左端点右边每种数第一次出现的位置，然后模拟上述跳跃过程。跳跃次数与数字的种类有关，而每个段中剩余数字不会超过 $\sqrt{n}$ ，且根号并不会跑满，该做法可以接受。

时间复杂度为 $O\left(\frac{n^2}{x}\right)$ 。

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define endl '\n'
const int M = 1e6 + 5, N = 1e6 + 5;
int a[M], b[M];

void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i], b[i] = a[i] ;
    sort(b + 1, b + 1 + n);
    int cnt = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;
    vector<int> c(cnt + 1);
    for (int i = 1; i <= n; ++i)
        c[a[i]]++;//每个数出现的次数
    int st = 1;
    vector<vector<int>> pos(n + 2);
    vector<int> gto(n + 2, 1e9);//第i个数需要往右跳跃所到的位置
    vector<int> ans(n + 2, -1);
    auto fun = [&](int x, int y) -> void//处理某个段
    {
        for (int i = x; i <= y; ++i)
            pos[a[i]].clear();
        set<int> p;
        for (int i = y; i >= x; --i)
        {
            if (pos[a[i]].size())
                p.erase(pos[a[i]].back());
            pos[a[i]].push_back(i);
            p.insert(i);
            if (pos[a[i]].size() >= m)
                gto[i] = pos[a[i]][pos[a[i]].size() - m];
            int r = i;
            // cout << "L=" << i << ":";
            // for (auto v : p)
            // {
            //     cout << v << ' ';
            // }
            // cout << endl;
            // cout<<i<<' '<<gto[i]<<endl;
            // cout<<i<<"  goto="<<gto[i]<<endl;
            for (auto v : p)
            {
                if (v <= r)
                    r = max(r, gto[v]);
                if (r == 1e9)
                {
                    r = -1;
                    break;
                }
            }
            ans[i] = r;
        }
    };
    for (int i = 1; i <= n; ++i)
    {
        if (c[a[i]] < m)//出现次数小于m的地方进行分段
        {
            int l = st, r = i - 1;
            if (l <= r)
                fun(l, r);
            st = i + 1;
        }
    }
    if (st <= n)
        fun(st, n);//最后一段单独处理
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << ' ';
    cout << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;

    cin >> T;
    while (T--)
    {
        solve();
    }
}

F

先判断 $-1$ ， $m$ 个标记点，多源 bfs 求出每个点 $i$ 与 $m$ 个标记点的最短距离，记为 $f(i)$ 。

设 $dis(i,j)$ 表示结点 $i$ 与 $j$ 的距离。

对于每次询问：

当 $dis(x,y)＞f(y)$ 时显然不能获得冠军，输出 $-1$ 。
当 $dis(x,y)＜f(y)$ 时，说明小明是唯一冠军，直接输出 $0$ 。
下面就是 $dis(x,y)＝f(y)$ ：

也就是说从 $x$ 到 $y$ 的路径中，一定会存在一个点 $z$ ，使得 $x$ 与某个运动员(具体是哪个运动员不关心)第一次在 $z$ 相遇。

既然是第一次相遇，说明 $x$ 到 $z$ 之前的路径是 $x$ 一个人走过来的，那么前面路径上面的所有点 $i$ 都满足 $dis(x,i)\neq f(i)$ 。因为如果两者相等，说明两者必会在点 $i$ 相遇，与 $z$ 是第一次相遇的位置矛盾。

在 $z$ 相遇以后，后面小明就可以与那个运动员保持步调一致，路径上后面的所有点 $j$ 都满足 $dis(x,j)=f(j)$ 。

因此可以二分第一次的相遇点与起点 $x$ 的距离，设当前距离为 $mid$ ，倍增求出从 $x$ 到 $y$ 的这条路径上面走 $mid$ 步所到达的点，设为 $t$ ，判断 $dis(x,t)$ 与 $f(t)$ 是否相等即可。

总的时间复杂度为 $O(q \log^2 n)$

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int M = 2e5 + 5;
int fa[M][22], dep[M];
vector<int> f[M];
inline void dfs(int x, int t)
{
    fa[x][0] = t;
    dep[x] = dep[t] + 1;
    for (auto to : f[x])
        if (to != t)
            dfs(to, x);
}
inline int lca(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--)
    {
        if (dep[fa[x][i]] >= dep[y])
            x = fa[x][i];
    }
    if (x == y)
        return x;
    for (int i = 20; i >= 0; i--)
    {
        if (fa[x][i] != fa[y][i])
        {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}
int dis(int x, int y)
{
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}

void solve()
{
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        f[x].push_back(y);
        f[y].push_back(x);
    }
    dfs(1, 0);
    for (int j = 1; (1 << j) <= n; ++j)
        for (int i = 1; i <= n; ++i)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    vector<int> vis(n + 3, 1e9);
    queue<int> p;
    for (int i = 1; i <= m; ++i)
    {
        int x;
        cin >> x;
        vis[x] = 0;
        p.push(x);
    }
    while (!p.empty())//多源bfs预处理
    {
        int x = p.front();
        p.pop();
        for (auto to : f[x])
        {
            if (vis[to] > vis[x] + 1)
            {
                vis[to] = vis[x] + 1;
                p.push(to);
            }
        }
    }
    auto check = [&](int mid, int s, int t) -> bool//从s出发，往t走mid步，能否到达一个vis值为mid的点
    {
        int L = mid; // 距离
        int lc = lca(s, t);
        int d1 = min(dep[s] - dep[lc], mid);
        mid -= d1;
        for (int i = 0; i <= 20; i++)
        {
            if (1 << i & d1)
            {
                s = fa[s][i];
            }
        }
        if (mid)
        {
            int d2 = dep[t] - dep[lc] - mid;
            swap(s, t);
            for (int i = 0; i <= 20; i++)
            {
                if (1 << i & d2)
                {
                    s = fa[s][i];
                }
            }
        }
        return vis[s] == L;
    };
    while (q--)
    {
        int s, t;
        cin >> s >> t;
        int dist = dis(s, t);

        if (dist > vis[t])
            cout << -1 << endl;
        else
        {
            int ans = dist, l = 0, r = dist;
            while (l <= r)
            {
                int mid = l + r >> 1;
                if (check(mid, s, t))
                {
                    ans = mid;
                    r = mid - 1;
                }
                else
                    l = mid + 1;
            }
            cout << dist - ans << endl;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        f[i].clear();
        dep[i] = 0;
        for (int j = 0; j <= 20; ++j)
            fa[i][j] = 0;
    }
}
signed main()
{
    ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

G

原问题转化一下，即：

把 $n$ 个数分为两组，每组的极差（最大值与最小值的差）不能超过 $k$ ，最小化 $k$ 。

问题等价于最小化两组极差的最大值。

设第一组的最小、最大值分别为 $x_1,y_1$ ，第二组的最小、最大值分别为 $x_2,y_2$ 。

这里假设 $y_1 \leq y_2$ ，于是 $x_1 \leq y_1 \leq y_2,x_2 \leq y_2$

结论：当取最优解时，必有 $y_1 \leq x_2$ ，即 $x_1 \leq y_1 \leq x_2 \leq y_2$ 。（两组之间一定不会有重叠部分）

证明：

设 $x_1,y_1,x_2,y_2$ 四个数经排序后从小到大为 $a,b,c,d,a\leq b \leq c \leq d$

当 $y_1 \leq x_2$ 时，此时两组极差的最大值为 $k_1=max(b-a,d-c)$
当 $y_1 > x_2$ 时，存在两类情况：
- 若 $x_1 \le x_2$ ，则排序为 $a=x_1,\ b=x_2,\ c=y_1,\ d=y_2$ 。此时两组极差的最大值为 $k_2=\max(c-a,\ d-b)$
- 若 $x_1 > x_2$ ，则排序为 $a=x_2,\ b=x_1,\ c=y_1,\ d=y_2$ 。此时两组极差的最大值为 $k_3=\max(c-b,\ d-a)=d-a$
这三类情况中，显然第三类是最大的（因为第二组覆盖的值域包含了第一组覆盖的值域，这种情况肯定不是我们想要的）。
因此只要讨论前两种情况，因为 $a\leq b \leq c \leq d$ ，所以 $b-a \le c-a ,d-c \le d-b$ ，即 $k_1=max(b-a,d-c) \leq k_2=\max(c-a,\ d-b)$
因此 $k_1 \leq k_2$ ，所以 $y_1 \leq x_2$ 时最优，即两组的值域部分不会有重叠。

因此只需要枚举 $y_1$ 所在位置， $y_1$ 以及它前面的数分到第一组， $y_1$ 后面的数分到第二组，对二者取最大值，再与答案取最小即可。

时间复杂度为 $O(n \log n)$ ，来自排序。

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int a[N];
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 1e9;
    sort(a + 1, a + n + 1);
    for (int i = 1; i < n; i++)
        ans = min(ans, max(a[i] - a[1], a[n] - a[i + 1]));
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

H

签到，略

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
int w(string s)
{
    int n = s.size();
    int a = 0, b = 0, c = 0;
    for (int i = 0; i + 3 < n; ++i)
        if (s.substr(i, 4) == "fire")
            a++;
    for (int i = 0; i + 4 < n; ++i)
        if (s.substr(i, 5) == "water")
            b++;
    for (int i = 0; i + 3 < n; ++i)
        if (s.substr(i, 4) == "wind")
            c++;
    return a + b * c;
}
signed main()
{
    int T = 1;
    cin >> T;
    while (T--)
    {
        int x, y;
        cin >> x >> y;
        string a, b;
        cin >> a >> b;
        cout << (w(a) > w(b) ? "YES" : "NO") << '\n';
    }
    return 0;
}

I

直接根据向量偏移一下即可。


#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
    int T = 1;
    cin >> T;
    while (T--)
    {
        int x1, y1, x2, y2, x3, y3;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
        cout << (x1 + x2 - x3) << " " << (y1 + y2 - y3) << '\n';
    }
    return 0;
}

J

题目太长，略

K

两种解法。

方法一：参考 pdf 题解，我只提供代码。

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int M = 1e6 + 5;
int a[M], b[M];
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> sum(n + 4), cnt(n + 4);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        int t = 0;
        if (a[i] == k)
            t = 0;
        else if (a[i] > k)
            t = 1;
        else
            t = -1;
        cnt[i] = cnt[i - 1] + (t == 0 ? 1 : 0); // 统计前i个数中k的个数
        sum[i] = t + sum[i - 1];
    }
    vector<vector<int>> pos(2 * n + 4);
    pos[n].push_back(0);
    for (int i = 1; i <= n; i++)
        pos[sum[i] + n].push_back(i); // 由于sum可能为负数，所以整体平移n
    int res = 0;
    for (int i = 0; i <= 2 * n; ++i)
    {
        for (int j = 0, L = pos[i].size(); j < L; ++j) // L表示pos[i]的大小
        {
            int x = pos[i][j];
            int l = j, r = L - 1, ans = -1;
            while (l <= r)
            {
                int mid = l + r >> 1;
                if (cnt[pos[i][mid]] - cnt[x]) // 判段区间内是否有k，只有至少有一个k才符合要求
                {
                    ans = mid;
                    r = mid - 1;
                }
                else
                    l = mid + 1;
            }
            if (ans != -1) // 找到了才加
                res += pos[i].size() - ans;
        }
    }
    cout << res << endl;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

方法二：

设： $b_i=\left\{ \begin{aligned} & -1,&& a_i < k \\ & 0, && a_i = k \\ & 1, && a_i > k \end{aligned} \right.$

于是原问题等价为：序列 $\{b_1,b_2,...\dots b_n\}$ 有多少个子区间 $[L,R]$ ，使得区间中至少存在一个 $0$ ，且区间和 $\sum_{i=L}^{R} b_i$ 的值为 $0$ 。

如果没有区间至少有一个 $0$ 的限制，这是一个经典的问题：预处理序列 $\{b_1,b_2,...\dots b_n\}$ 的前缀和，设为 $\{S_1,S_2,...\dots S_n\}$ 。对于一个给定的右端点 $R$ ，左端点 $L$ 满足条件当且仅当 $S_R-S_{L-1}=0$ 。

可以在顺序遍历枚举右端点的时候，维护每个 $S_i$ 出现的次数，对于当前枚举右端点的 $R$ ，让答案加上目前序列中 $S_R$ 出现的次数即可。

但是加上了每个区间至少有一个 $0$ 的限制呢？注意我们实际上只关心每个区间是否有 $0$ ，而不关心具体有多少个 $0$ ，因此对于当前枚举的右端点R，我们只需要知道上一个 $b_i$ 为 $0$ 的位置（也就是上一个 $a_i$ 为 $k$ 的位置），假设这个位置为 $x$ ，那么其实是在做这样的一次查询：

在 $x-1$ 的前面位置 $i(0\leq i \leq x-1)$ ，有多少 $i$ 满足 $S_i=S_R$ ？满足这个条件的 $i$ 加一之后其实就是我们要找的左端点。
设 $cnt(i,j)$ 表示 $\{S_0,S_1,S_2,...\dots S_i\}$ 中 $j$ 出现的次数，即查询 $cnt(x-1,S_R)$ 。

但是我们会枚举 $n$ 次右端点，难道我们需要开二维数组来维护 $cnt$ 吗？这样时间和空间复杂度都是 $O(n^2)$ 的，不可接受。

实际上，我们有 $n$ 次询问，每一次询问都可以表示成一个二元组 $x,y$ ，然后查询 $cnt(x,y)$ ，我们将所有的查询按 $x$ 升序排序之后，然后再遍历，并维护每个 $S_i$ 出现的次数，假如当前遍历到的位置为 $i$ ，我们需要把所有询问中（这 $n$ 次询问）满足 $x=i$ 的询问拿出来即可（可以用二维 vector 预处理实现），这样我们就不用 $O(n^2)$ 维护了（有点类似背包的滚动数组）。

实际处理也并不需要对所有询问的左端点排序，因为从小到大枚举就相当于给所有元素按左端点排好序了，这样最终的时间复杂度为 $O(n)$ 。

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int M = 1e6 + 5;
int a[M], b[M];
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> sum(n * 2 + 4);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        int t = 0;
        if (a[i] == k)
            t = 0;
        else if (a[i] > k)
            t = 1;
        else
            t = -1;
        sum[i] = t + sum[i - 1];
    }
    vector<vector<int>> query(n + 4);
    int pos = -1;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == k)
            pos = i;
        if (pos == -1)
            continue;
        query[pos - 1].push_back(sum[i]);//查询：sum数组中，pos-1的前面有多少个数等于sum_i
    }
    vector<int> cnt(2*n + 4);
    int ans = 0;
    for (int i = 0; i <= n; i++)
    {
        cnt[sum[i] + n]++;//由于sum可能是负数，我们在处理的时候给所有值往右偏移n个单位，这样得到的数字都为非负数了
        for (auto x : query[i])
            ans += cnt[x + n];
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

L

签到，略

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
    int T = 1;
    cin >> T;
    while (T--)
    {
        int a, b;
        cin >> a >> b;
        cout << (a + b == 350234 ? "YES" : "NO") << '\n';
    }
    return 0;
}

M

这类模型似乎也是典中典了，我们先仅考虑 $h_1$ 和 $h_2$ 的关系，如果 $h_1>h_2$ ，那么我们无论如何都必须在第二个位置执行最少 $h_1-h_2$ 次，那么不妨直接对第二个位置进行 $h_1-h_2$ 次操作，这样带来的影响是：区间 $[2,x+1]$ 的数都被加了 $h_1-h_2$ 次，操作完后 $h_1,h_2$ 的大小关系已经满足条件了，然后依次往后做同样的操作即可。

显然，这里的区间操作我们可以用差分来维护，设 $d_i=h_i-h_{i-1}$ ，那么对区间 $[L,R]$ 的所有数字加上 $x$ 等价于 $d_{R+1}-=x,d_L+=x$ 。


#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int M = 1e6 + 5;
int a[M];
void solve()
{
    int n, x;
    cin >> n >> x;
    vector<int> d(2 * n + 2); // 差分数组
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        d[i] = a[i] - a[i - 1];
    }
    int ans = 0; // 总操作次数
    for (int i = 1; i <= n; i++)
    {
        if (d[i] < 0)
        {
            int cnt = abs(d[i]); // 操作次数
            ans += cnt;
            d[i] = 0;
            d[i + x] -= cnt; // 更新差分数组
        }
    }
    cout << ans << endl;
}
signed main()
{
    ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

目录

A

B

C

D

E

F

G

H

I

J

K

方法一：参考 pdf 题解，我只提供代码。

方法二：

L

M