2023-11-05 NOIP 模拟赛题解

又是 jzyz 的多校联考，前三题搬的 JOI 2021 Final，最后一题是 zyc 自己出的，非常有特色

A. 方块游戏 / block

题面

题目来源：JOI 2021 Final 家庭菜园

题目描述

约翰最近爱上了玩一种类似俄罗斯方块的积木游戏，游戏中的积木是长为 $N$ 的一排，每次他可以选择一段 $[l,r]$ 满足 $1\le l \le r \le N$，从上方扔下这样一段积木，使得 $[l,r]$ 位置的积木高度都增加1。

给出积木目前的形状，形式为一个序列 $A$，$A_i$表示i处当前积木的高度。请你用最小的步数使得操作后存在一个整数 $k$，满足 $[A_1,A_2,...,A_k]$ 是一个严格单调递增的序列，$[A_k,A_{k+1},...,A_N]$ 是一个严格递减的序列。

请你输出最小的操作次数

输入格式

第一行一个整数 $N$，代表序列的长度。

第二行N个整数 $A_i$ 代表序列。

输出格式

一行一个整数代表最小操作次数。

输入输出样例

样例输入 #1

5
3 2 2 3 1

样例输出 #1

3

样例解释 #1

• 对 $[2,5]$ 进行操作，序列变为 $\lbrace3,3,3,4,2\rbrace$。
• 对 $[2,3]$ 进行操作，序列变为 $\lbrace3,4,4,4,2\rbrace$。
• 对 $[3,3]$ 进行操作，序列变为 $\lbrace3,4,5,4,2\rbrace$。

样例输入 #2

5
9 7 5 3 1

样例输出 #2

0

样例输入 #3

8
12 2 34 85 4 91 29 85

样例输出 #3

93

数据范围与约定

• 任务1，40pts，$N \le 2000$。
• 任务2，60pts，无额外限制
• 对于 $100\%$ 的数据，$1\le N \le 2\times 10^5,1 \le A_i \le 10^9$。

思路

一眼题

首先对原序列进行差分，得到序列 $b$

那么每个操作就相当于在 $b$ 序列中找出一个位置让其加 $x$，在该位置之后找另一个位置让其减 $x$

当然也可以只加 / 只减

最终的目标是要让 $b$ 的前半部分大于零，后半部分小于零，求最小代价

显然可以求出以下两个前缀 / 后缀和：

$$costa_i = \begin{cases} costa_{i - 1}, & a_i > 0 \\ costa_{i - 1} + |a_i| + 1, & a_i \le 0 \end{cases}$$

$$costb_i = \begin{cases} costb_{i + 1}, & a_i < 0 \\ costb_{i + 1} + |a_i| + 1, & a_i \ge 0 \end{cases}$$

那么答案显然为：

$$ans = \min \limits_{0 \le i < n} \lbrace costa_i + costb_{i + 1} \rbrace$$

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

代码

#include <bits/stdc++.h>
namespace solution
{
    typedef long long LL;
    const int MAXN = 2e5 + 5;
    const LL INF = 0x3f3f3f3f3f3f3f3f;
    int n;
    LL ans = INF;
    LL a[MAXN];
    LL b[MAXN];
    LL costa[MAXN], costb[MAXN];
    int main()
    {
        freopen("block.in", "r", stdin);
        freopen("block.out", "w", stdout);
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
            b[i - 1] = a[i] - a[i - 1];
        }
        for (int i = 1; i < n; i++)
        {
            if (b[i] <= 0)
            {
                costa[i] = costa[i - 1] - b[i] + 1;
            }
            else
            {
                costa[i] = costa[i - 1];
            }
        }
        for (int i = n - 1; i >= 1; i--)
        {
            if (b[i] >= 0)
            {
                costb[i] = costb[i + 1] + b[i] + 1;
            }
            else
            {
                costb[i] = costb[i + 1];
            }
        }
        for (int i = 0; i < n; i++)
        {
            ans = std::min(ans, std::max(costa[i], costb[i + 1]));
        }
        printf("%lld\n", ans);
        return 0;
    }
}
int main()
{
    solution::main();
    return 0;
}

B. 雪球 / snow

题面

来源：JOI 2021 Final 雪玉

题目描述

约翰的家里下雪了，你那里下雪了吗。

约翰的家是一条直线。有 $N$ 个雪球在直线上，这 $N$ 个雪球编号为 $1 \sim N$，第 $i$ 个雪球在第 $A_i$ 个点上。刚开始，整条数轴覆盖满了雪，接下来 $Q$ 天将会刮起大风，第 $j$ 天的风力强度为 $W_j$，如果 $W_j$ 为正数，所有雪球都朝右移动 $W_j$ 个单位长度，如果 $W_j$ 为负数，所有雪球都朝左移动 $-W_j$ 个单位长度。

当一个区间 $[a,a+1]$ 被雪覆盖时，雪球滚上去雪球的质量会加一，这一个区间里的雪也会被清空。刚开始每一个雪球的质量均为 $0$，而这 $Q$ 天里也没有再下雪。

你想问这 $Q$ 天结束后每个雪球的质量是怎样的。

输入格式

第一行两个整数 $N,Q$ 代表雪球个数和下雪天数。

第二行 $N$ 个整数 $A_i$ 代表这 $N$ 个雪球的初始位置。

接下来 $Q$ 行每行一个整数 $W_j$ 代表每一天的风力强度。

输出格式

$N$ 行每行一个整数代表这 $Q$ 天结束后每一个雪球的质量。

样例 #1

样例输入 #1

4 3
-2 3 5 8
2
-4
7

样例输出 #1

5
4
2
6

样例 #2

样例输入 #2

1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

样例输出 #2

3000000000000

样例 #3

样例输入 #3

10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6

样例输出 #3

14
8
7
9
11
10
9
8
5
10

提示

样例 1 解释：

雪球初始位置为 $-2,3,5,8$，初始质量为 $0,0,0,0$。

• 第一天过后，雪球位置为 $0,5,7,10$，质量为 $2,2,2,2$。
• 第二天过后，雪球位置为 $-4,1,3,6$，质量为 $4,4,2,3$。
• 第三天过后，雪球位置为 $3,8,10,13$，质量为 $5,4,2,6$。

数据规模与约定

• Subtask 1（33 pts）：$N,Q \le 2000$。
• Subtask 2（67 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N,Q \le 2 \times 10^5$，$|A_i|,|W_j| \le 10^{12}$，$A_i<A_{i+1}$。

思路

本题中有一个非常强的性质：雪球之间的相对位置不会改变

那么我们考虑虚拟一个雪球放在原点，那么这个雪球在移动过程中的最左端到达的位置加上 $a_x$ 就是第 $x$ 个点在移动过程中到达的最左端的位置，右端同理

由于运动是连续的，每个雪球的贡献一定是以 $a_x$ 为中心的一段距离

显然如果当前雪球运动过程的最左端与当前雪球左边的雪球的最右端相遇了，当前雪球的左侧就不可能继续产生贡献，右端同理

那么考虑维护雪球之间的距离

我们将雪球之间的距离从大到小排序

每次询问是，我们更新原点那个虚拟雪球的最左端与最右端，然后检查它们的和是否超过了当前雪球的距离，如果超过了，那么就累加答案，否则继续

即有核心代码：

for (int i = 1; i <= q; i++)
{
    scanf("%lld", &w[i]);
    now += w[i], L = std::max(L, -now), R = std::max(R, now);
    while (L + R >= node[tot].val && tot < n)
    {
        if (w[i] < 0)
        {
            ans[node[tot].pos] += R;
            ans[node[tot].pos + 1] += a[node[tot].pos + 1] - (a[node[tot].pos] + R);
        }
        if (w[i] > 0)
        {
            ans[node[tot].pos + 1] += L;
            ans[node[tot].pos] += a[node[tot].pos + 1] - L - a[node[tot].pos];
        }
        tot++;
    }
}

其实就是在检查当前点最左端是否与当前点左边的点的最右端相遇

相遇之后以最后一次操作的风的方向分类讨论即可

注意在最后累加没有相遇的点的答案，以及计算第一个点和最后一个点的答案

代码

#include <bits/stdc++.h>
namespace solution
{
    typedef long long LL;
    const int MAXN = 2e5 + 5;
    LL n, q;
    LL now, L, R, tot;
    LL a[MAXN], w[MAXN], ans[MAXN];
    struct Node
    {
        LL val, pos;
        Node(LL _val = 0, LL _pos = 0) : val(_val), pos(_pos) {}
    };
    bool operator<(const Node &a, const Node &b)
    {
        return a.val < b.val;
    }
    Node node[MAXN];
    int main()
    {
        scanf("%lld%lld", &n, &q);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
        }
        for (int i = 1; i <= n; i++)
        {
            node[i].val = a[i + 1] - a[i], node[i].pos = i;
        }
        tot = 1;
        std::sort(node + 1, node + n);
        for (int i = 1; i <= q; i++)
        {
            scanf("%lld", &w[i]);
            now += w[i], L = std::max(L, -now), R = std::max(R, now);
            while (L + R >= node[tot].val && tot < n)
            {
                if (w[i] < 0)
                {
                    ans[node[tot].pos] += R;
                    ans[node[tot].pos + 1] += a[node[tot].pos + 1] - (a[node[tot].pos] + R);
                }
                if (w[i] > 0)
                {
                    ans[node[tot].pos + 1] += L;
                    ans[node[tot].pos] += a[node[tot].pos + 1] - L - a[node[tot].pos];
                }
                tot++;
            }
        }
        while (tot < n)
        {
            ans[node[tot].pos] += R, ans[node[tot].pos + 1] += L;
            tot++;
        }
        ans[1] += L, ans[n] += R;
        for (int i = 1; i <= n; i++)
        {
            printf("%lld\n", ans[i]);
        }
        return 0;
    }
}
int main()
{
    solution::main();
    return 0;
}

C. 遥控机器人 / robot

来源：JOI 2021 Final ロボット

题面

题目描述

给定一个 $N$ 点无向图，这 $N$ 个点编号为 $1 \sim N$，由 $M$ 条边连接，这 $M$ 条边编号为 $1 \sim M$，分别连接点 $A_i$ 与点 $B_i$。这 $M$ 条边染上了颜色，第 $i$ 条边的颜色为 $C_i$，保证 $C_i \in [1,M]$ 但不保证 $C_i$ 互不相等。

你很智能，如果我说一种颜色 $L$，满足下面这些要求的话：

• 存在一条边的颜色为 $L$ 且一个端点为你现在在的点。
• 不存在大于等于两条边满足颜色为 $L$ 且一个端点为你现在在的点。

你就会移动到这条边走向对面的端点，否则你就会原地不动。

你现在在点 $1$ 处，我要你移动到点 $N$ 处，我可以告诉你一些颜色你按照这些颜色走。但这个图有可能不满足能从 $1$ 走向 $N$ 这个条件，因此我要改变一些边的颜色。改变第 $i$ 条边的颜色使其变为另一个在区间 $[1,M]$ 里的数需要的代价为 $P_i$，我想问，至少需要多少代价才能让你成功移动到点 $N$？

输入格式

第一行两个整数 $N,M$ 代表无向图点数和边数。

接下来 $M$ 行每行四个整数 $A_i,B_i,C_i,P_i$ 描述一条边。

输出格式

一行一个整数代表最小代价，如果无法到达输出 $-1$。

样例 #1

样例输入 #1

4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2

样例输出 #1

3

样例 #2

样例输入 #2

5 2
1 4 1 2
3 5 1 4

样例输出 #2

-1

样例 #3

样例输入 #3

5 7
2 3 7 1
1 4 5 1
4 5 3 1
3 4 7 1
2 4 3 1
3 5 6 1
1 2 5 1

样例输出 #3

1

提示

样例 1 解释

我可以进行如下操作：

• 将第 $4$ 条边的颜色改为 $4$，代价 $1$。
• 将第 $6$ 条边的颜色改为 $2$，代价 $2$。

总代价 $3$，然后我如下使唤你：

• 我说“颜色 $2$！”你从点 $1$ 移动到点 $2$。
• 我说“颜色 $4$！”你从点 $2$ 移动到点 $4$。

样例 2 解释

很遗憾，即使如此智能的你也到达不了第 $N$ 个点。

数据规模与约定

• Subtask 1（34 pts）：$N \le 1000$，$M \le 2000$。
• Subtask 2（24 pts）：$P_i=1$。
• Subtask 3（42 pts）：无特殊限制。

对于 $100\%$ 的数据，$2 \le N \le 10^5$，$1 \le M \le 2 \times 10^5$，$1 \le A_i<B_i \le N$，$1 \le C_i \le M$，$1 \le P_i \le 10^9$，保证图无重边。

思路

一眼不会

赛后看题解会了

首先可以发现如下性质：每条边的颜色只会被更改一次（如果要更改多次，那么为什么不一开始就更改好呢）

考虑一个点到另一个点的花费，可以分为以下几种情况：

1. 所需要的颜色唯一，花费为 $0$
2. 改变当前边的颜色，花费为 $P_i$
3. 改变其他所有边（与当前边出发点相同，颜色相同）的边的颜色

但是注意不能直接这样统计

考虑以下情况

我们走路径 $a \rightarrow b \rightarrow c$，且在 $a \rightarrow b$ 的时候使用方法 2 修改， $b \rightarrow c$ 的时候使用方法 3 修改，那么此时就无需更改 $a \rightarrow b$ 这条边的颜色（因为已经修改过了），或者可以看作 $a \rightarrow b$ 时没有花费代价

这种情况不太好处理

我们可以建立一个对于每个点 $u$ 和 $u$ 连出的边的颜色建立虚点

例如有点 $u$，连有边 $(u, v, c, p)$

我们建立一个虚点 $x$

之后连如下三种边：

1. $(u, x, 0, 0)$
2. $(x, v, 0, sumP_{u, c} - p)$
3. $(v, x, 0, 0)$

那么情况一可以通过走边 $1, 2$ 解决，情况二直接走原图的边，情况三可以走边 $3, 2$ 解决

那么直接建图跑最短路即可

代码

#include <bits/stdc++.h>
namespace solution
{
    typedef long long LL;
    const int MAXN = 1e6 + 5;
    const LL INF = 0x3f3f3f3f3f3f3f3f;
    int n, m;
    int tot = 0;
    LL sum[MAXN], col[MAXN];
    struct Edge
    {
        int from, to, color;
        LL dis;
        Edge(int _from, int _to, int _color, LL _dis) : from(_from), to(_to), color(_color), dis(_dis) {}
    };
    std::vector<Edge> edge;
    std::vector<int> g[MAXN];
    void addEdge(int u, int v, int c, LL d)
    {
        g[u].push_back(edge.size());
        edge.push_back(Edge(u, v, c, d));
    }
    void build()
    {
        tot = n;
        for (int u = 1; u <= n; u++)
        {
            for (auto &i : g[u])
            {
                auto &e = edge[i];
                if (e.color == 0)
                {
                    continue;
                }
                sum[e.color] += e.dis;
            }
            auto tmp = g[u];
            for (auto &i : tmp)
            {
                auto e = edge[i];
                if (e.color == 0)
                {
                    continue;
                }
                if (col[e.color] == 0)
                {
                    col[e.color] = ++tot;
                    addEdge(u, col[e.color], 0, 0);
                }
                addEdge(col[e.color], e.to, 0, sum[e.color] - e.dis);
                addEdge(e.to, col[e.color], 0, 0);
            }
            for (auto &i : g[u])
            {
                auto &e = edge[i];
                sum[e.color] = 0, col[e.color] = 0;
            }
        }
    }
    struct Node
    {
        LL id, dis;
        Node(LL _id = 0, LL _dis = 0) : id(_id), dis(_dis) {}
    };
    bool operator>(const Node a, const Node b)
    {
        return a.dis > b.dis;
    }
    LL dist[MAXN];
    bool vis[MAXN];
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> q;
    void dijkstra()
    {
        std::memset(dist, 0x3f, sizeof(dist));
        dist[1] = 0, q.push(Node(1, 0));
        while (!q.empty())
        {
            auto u = q.top();
            q.pop();
            if (vis[u.id] == true)
            {
                continue;
            }
            vis[u.id] = true;
            for (auto &i : g[u.id])
            {
                auto &e = edge[i];
                if (u.dis + e.dis < dist[e.to])
                {
                    dist[e.to] = u.dis + e.dis;
                    q.push(Node(e.to, dist[e.to]));
                }
            }
        }
    }
    int main()
    {
        freopen("robot.in", "r", stdin);
        freopen("robot.out", "w", stdout);
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++)
        {
            int u, v, c, d;
            scanf("%d%d%d%d", &u, &v, &c, &d);
            addEdge(u, v, c, d), addEdge(v, u, c, d);
        }
        build();
        dijkstra();
        printf("%lld\n", dist[n] == INF ? -1 : dist[n]);
        return 0;
    }
}
int main()
{
    solution::main();
    return 0;
}