题目链接：2025 NOIP模拟赛(三) - 云兰阁

题面文件：PDF

赛后总结#

赛时成绩：0+100+100+40=240

T1：唐完了，最大值INF设为了1e9，但实际计算过程中会达到1e18的量级。加之神秘数据和捆绑测试直接爆零了。。

T2：本质为01背包+二分，但考场上打了一个神秘的dp做法。

T3：简单图论，在最短路的基础上做一些优化操作。

T4：组合数学，不会做，只做了特殊性质。

题目难度：橙+黄+绿+蓝

A. Longge 的信号塔 (tower)#

Description#

给定 $n$ 个信号频段，第 $i$ 个频段覆盖区间 $[l_i,r_i]$ ，代价为 $c_i$ 。

如果存在一种频段方案，所有频段包含的最小坐标 $L_{min}$ 和最大坐标 $R_{max}$ 。那么所有位于区间 $[L_{min},R_{max}]$ 的坐标都会被覆盖。

对于前 $s$ 个频段，需要构建一种方案使得网络可以覆盖当前所有频道覆盖的最大范围。在满足此要求的情况下，使得代价最小。请求出 $s$ 从 $1$ 到 $n$ 每一天所需的最小花费。

Solution#

显然，每次询问下，只需要覆盖最小坐标 $L_{min}$ 和最大坐标 $R_{max}$ 就可以覆盖整个区间，那么只存在两种情况，一种情况是如果存在 $[L_{min},R_{max}]$ 这一区间频段，只需要计算这一频段的代价即可。另一种情况只需要考虑维护两个分别满足覆盖最小坐标和最大坐标的最小区间代价计算。对于这两种情况选择最小代价的情况即可。

时间复杂度 $O(N)$ 。

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define NOI_IO
4
#define MULTI_CASES
5
#define ll long long
6
#define int ll
7
#define endl '\n'
8
#define vi vector<int>
9
#define PII pair<int, int>
10
const int MaxN = 2e5 + 100;
11
const int INF = 1e18;
12
const int mod = 1e9 + 7;
13
int T = 1, N, M;
14
// int a[MaxN];
15
struct node
16
{
17
    int l, r, w;
18
    int id;
19
} a[MaxN];
20
inline void Solve()
21
{
22
    cin >> N;
23
    int suml = INF, sumr = INF, sum = INF;
24
    // int sum=INF;
25
    int L = INF, R = 0;
26
    int l = 0, r = 0, id = 0;
27
    for (int i = 1; i <= N; i++)
28
    {
29
        cin >> a[i].l >> a[i].r >> a[i].w;
30
        L = min(L, a[i].l);
31
        R = max(R, a[i].r);
32
        if (a[i].l == L)
33
        {
34
            if (a[l].l == L)
35
            {
36
                if (a[i].w < suml)
37
                {
38
                    suml = a[i].w;
39
                    l = i;
40
                }
41
            }
42
            else
43
            {
44
                // cerr<<1<<endl;
45
                suml = a[i].w;
46
                l = i;
47
            }
48
        }
49
        if (a[i].r == R)
50
        {
51
            if (a[r].r == R)
52
            {
53
                if (a[i].w < sumr)
54

55
                {
56
                    sumr = a[i].w;
57
                    r = i;
58
                }
59
            }
60
            else
61
            {
62
                sumr = a[i].w;
63
                r = i;
64
            }
65
        }
66
        if (a[i].l == L && a[i].r == R)
67
        {
68
            if (a[id].l == L && a[id].r == R)
69
            {
70
                if (a[i].w < sum)
71
                {
72
                    sum = a[i].w;
73
                    id = i;
74
                }
75
            }
76
            else
77
            {
78
                sum = a[i].w;
79
                id = i;
80
            }
81
        }
82
        if (a[id].l != L || a[id].r != R)
83
        {
84
            sum = INF;
85
        }
86
        // cerr<<sum<<" "<<suml<<" "<<sumr<<endl;
87
        cout << min(sum, suml + sumr) << endl;
88
    }
89
    // cout << endl;
90
}
91
signed main()
92
{
93
#ifdef NOI_IO
94
    freopen("tower.in", "r", stdin);
95
    freopen("tower.out", "w", stdout);
96
#endif
97
    ios::sync_with_stdio(0);
98
    cin.tie(nullptr), cout.tie(nullptr);
99
#ifdef MULTI_CASES
100
    cin >> T;
101
    while (T--)
102
#endif
103
        Solve();
104
    return 0;
105
}

B. Longge 的双核服务器 (dualcore)#

Description#

给定 $n$ 个任务，第 $i$ 个任务需要 $s_i$ 的运算量来完成。

给定两个计算集群，需要将这 $n$ 个任务分配给这两个集群，且每个任务必须完整地分配给一个集群，不可拆分。

在第 $t$ 秒时，集群一可以获得总共 $t\times f$ 的算力资源，集群二可以获得总共 $t\times w$ 的算力资源。

需要求解最小的时间 $T$ ，使得存在一种将任务划分为集合 $S_1$ 和集合 $S_2$ 方案，满足：

$\sum_{j\in S_1}s_j\le T\times f \ 且\ \sum_{k\in S_2}s_k\le T\times w$

Solution#

由于任务不可拆分，这是一个典型的 0/1 背包问题 或 子集和问题 (Subset Sum Problem) 的变种。

首先，我们需要知道哪些 $x$ 值是可以由若干个 $a_i$ 相加得到的。

定义 mp[j]：

mp[j] = true 表示运算量之和 $j$ 是可以达到的。
mp[j] = false 表示无法凑出和为 $j$ 的任务组合。

那么可以写出状态转移方程：

对于第 $i$ 个任务（大小为 $a_i$ ），我们从大到小更新 $j$ （从 $Sum$ 到 $a_i$ ）：

$mp[j] = mp[j] \lor mp[j - a_i]$

这里使用倒序遍历是为了保证每个物品在每个状态计算中只被使用一次（0/1 背包的空间优化写法）。

计算完 DP 数组后，mp 数组中所有值为 true 的下标 $s$ 即为可能的集群一的任务总量 $x$ 。

我们遍历 $s$ 从 $0$ 到 $Sum$ ：

如果 mp[s] 为 true：
计算 $t_1 = \lceil \frac{s}{w} \rceil$ 。
计算 $t_2 = \lceil \frac{Sum - s}{f} \rceil$ 。
当前方案耗时 $ans_{curr} = \max(t_1, t_2)$ 。
更新全局最小值： $ans = \min(ans, ans_{curr})$ 。

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define NOI_IO
4
#define MULTI_CASES
5
#define ll long long
6
#define int ll
7
#define endl '\n'
8
#define vi vector<int>
9
#define PII pair<int, int>
10
const int MaxN = 1e6 + 100;
11
const int INF = 1e18;
12
const int mod = 1e9 + 7;
13
int T = 1, N, M;
14
int a[MaxN];
15
bool mp[MaxN];
16
inline void Solve()
17
{
18
    int w, f;
19
    cin >> w >> f;
20
    cin >> N;
21
    int sum = 0;
22
    for (int i = 1; i <= N; i++)
23
    {
24
        cin >> a[i];
25
        sum += a[i];
26
    }
27
    mp[0] = 1;
28
    for (int i = 1; i <= N; i++)
29
    {
30
        int x = a[i];
31
        for (int s = sum; s >= x; s--)
32
        {
33
            mp[s] = mp[s] | mp[s - x];
34
        }
35
    }
36
    int ans = INF;
37
    for (int s = 0; s <= sum; s++)
38
    {
39
        if (!mp[s])
40
            continue;
41
        int t1 = (s + w - 1) / w;
42
        int t2 = (sum - s + f - 1) / f;
43
        ans = min(ans, max(t1, t2));
44
        mp[s] = 0;
45
    }
46
    cout << ans << endl;
47
}
48
signed main()
49
{
50
#ifdef NOI_IO
51
    freopen("dualcore.in", "r", stdin);
52
    freopen("dualcore.out", "w", stdout);
53
#endif
54
    ios::sync_with_stdio(0);
55
    cin.tie(nullptr), cout.tie(nullptr);
56
#ifdef MULTI_CASES
57
    cin >> T;
58
    while (T--)
59
#endif
60
        Solve();
61
    return 0;
62
}

根据您提供的题目、代码以及参考格式，为您撰写的题解如下：

C. Longge 的情报网络 (network)#

Description#

给出一个由 $N$ 个情报小组构成的网络，第 $i$ 个小组包含若干名特工（代号在 $1$ 到 $M$ 之间）。

根据协议，若两个小组 $X$ 和 $Y$ 拥有至少一名共同特工，则可以将这两个小组进行“融合”操作，融合后的新小组包含原两个小组的所有成员。

求最少需要进行多少次“融合”操作，使得特工 $1$ 和特工 $M$ 最终处于同一个小组中。如果无法实现，输出 $-1$ 。

Solution#

本题可以抽象为一个图论中的最短路问题。

我们将每一个“小组”看作图中的一个节点。如果两个小组之间存在共同的特工，说明它们之间可以进行一次融合操作，即这两个节点之间存在一条权值为 $1$ 的边。

题目要求最少的操作次数，实际上就是求从“包含特工 $1$ 的小组集合”到“包含特工 $M$ 的小组集合”的最短距离。

由于直接暴力建图（两两判断小组是否有公关成员）的时间复杂度可能达到 $O(N^2)$ ，无法通过。我们可以利用特工编号作为中间媒介进行优化 BFS (广度优先搜索)：

数据预处理：建立倒排索引，记录每个特工分别属于哪些小组。
初始化：找出所有包含特工 $1$ 的小组，将它们的距离 dis 设为 $0$ ，并全部加入 BFS 队列。
搜索过程：
- 取出队首小组 $u$ 。
- 遍历小组 $u$ 中的所有特工 $s$ 。为防止重复搜索，应当记录特工 $s$ 是否已被访问过。
- 如果特工 $s$ 未被访问，则通过倒排索引找到特工 $s$ 所属的所有小组 $v$ 。
- 如果小组 $v$ 未被访问，则更新 dis[v] = dis[u] + 1 并加入队列。
- 一旦遇到包含特工 $M$ 的小组，当前的 dis 即为答案。

时间复杂度为 $O(\sum A_i)$ ，即输入数据的大小，足以通过本题。

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define NOI_IO
4
// #define MULTI_CASES
5
#define ll long long
6
#define int ll
7
#define endl '\n'
8
#define vi vector<int>
9
#define PII pair<int, int>
10
const int MaxN = 2e5 + 100;
11
const int INF = 1e9;
12
const int mod = 1e9 + 7;
13
int T = 1, N, M;
14
vi a1, aM;
15
vi G1[MaxN]; // G1[i] 存储第 i 个小组包含的特工
16
vi id[MaxN]; // id[x] 存储包含特工 x 的小组编号
17
bool ed[MaxN]; // 标记是否为包含特工 M 的目标小组
18
int dis[MaxN]; // 记录到达第 i 个小组的最少融合次数
19
bool vis[MaxN]; // 记录特工是否被访问过，避免重复搜索
20
inline void Solve()
21
{
22
    memset(dis, -1, sizeof dis);
23
    cin >> N >> M;
24

25
    bool hm1 = 0, h1 = 0, hm = 0;
26
    for (int i = 1; i <= N; i++)
27
    {
28
        int x;
29
        cin >> x;
30
        bool f1 = 0, fm = 0;
31
        for (int j = 1; j <= x; j++)
32
        {
33
            int agent;
34
            cin >> agent;
35
            G1[i].push_back(agent);
36
            id[agent].push_back(i); // 建立倒排索引
37
            if (agent == 1)
38
                f1 = 1;
39
            if (agent == M)
40
                fm = 1;
41
        }
42
        if (f1)
43
            a1.push_back(i), h1 = 1;
44
        if (fm)
45
            aM.push_back(i), ed[i] = 1, hm = 1;
46

47
        // 特判：如果同一个小组既有 1 又有 M，不需要融合，次数为 0
48
        if (f1 && fm)
49
        {
50
            cout << 0 << endl;
51
            return;
52
        }
53
    }
54

55
    if (!h1 || !hm)
56
    {
57
        cout << -1 << endl;
58
        return;
59
    }
60

61
    queue<int> q;
62
    // 将所有包含特工 1 的小组入队，距离为 0
63
    for (auto y : a1)
64
    {
65
        dis[y] = 0;
66
        q.push(y);
67
    }
68

69
    while (!q.empty())
70
    {
71
        int x = q.front(); // x 是小组编号
72
        q.pop();
73

74
        // 遍历该小组内的所有特工
75
        for (auto y : G1[x])
76
        {
77
            if (vis[y]) // 如果该特工已经被作为跳板使用过，跳过
78
                continue;
79
            vis[y] = 1;
80

81
            // 遍历该特工所属的所有其他小组
82
            for (auto v : id[y])
83
            {
84
                if (dis[v] != -1) // 如果小组 v 已访问过
85
                    continue;
86

87
                dis[v] = dis[x] + 1; // 距离 + 1（代表融合 1 次）
88

89
                if (ed[v]) // 如果到达了包含特工 M 的小组
90
                {
91
                    cout << dis[v] << endl;
92
                    return;
93
                }
94
                q.push(v);
95
            }
96
        }
97
    }
98
    cout << -1 << endl;
99
}
100
signed main()
101
{
102
#ifdef NOI_IO
103
    freopen("network.in", "r", stdin);
104
    freopen("network.out", "w", stdout);
105
#endif
106
    ios::sync_with_stdio(0);
107
    cin.tie(nullptr), cout.tie(nullptr);
108
#ifdef MULTI_CASES
109
    cin >> T;
110
    while (T--)
111
#endif
112
        Solve();
113
    return 0;
114
}

D. Longge 的量子矩阵 (matrix)#

待更新

2025.11.22 NOIP 模拟赛总结&题解

赛后总结#

A. Longge 的信号塔 (tower)#

Description#

Solution#

Code#

B. Longge 的双核服务器 (dualcore)#

Description#

Solution#

Code#

C. Longge 的情报网络 (network)#

Description#

Solution#

Code#

D. Longge 的量子矩阵 (matrix)#