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

题面文件：PDF

赛后总结#

赛时成绩：10+100+30=140

T1：已经不是人类了，求解时应为 +=但写错为了 =导致直接炸了。

T2：简单题。

T3：最短路+dp求解，但赛时做法假了。

T4：不会做。

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

A. 李大厨的合并艺术 (merging)#

Description#

给定 $n$ 种不同尺寸的面团，尺寸为 $s_i$ ，数量为 $c_i$ 。

可以进行任意顺序任意次数次操作，选择任意两团尺寸相同的面团，如果尺寸为 $K$ ，那么将其合并为尺寸为 $2K$ 的新面团。

要求使得最后的面团数量尽可能小。

Solution#

S1#

考虑贪心做法，对于面团能合并的要尽可能合并。所以按照尺寸从小到大排序，依次合并，最后统计剩余个数即可。

时间复杂度 $O(nlog_2n)$ ，可以极限通过。

S2#

考虑在S1的想法上优化，我们可以先把面团拆分至不可拆分，然后再依次合并即可。

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

Code#

C1#

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
int a[MaxN];
15
map<int, int> mp;
16
inline void Solve()
17
{
18
    cin >> N;
19
    for (int i = 1; i <= N; i++)
20
    {
21
        int x, y;
22
        cin >> x >> y;
23
        mp[x] += y;
24
    }
25
    for (auto cnt : mp)
26
    {
27
        int x = cnt.first, y = cnt.second;
28
        if (y >= 2)
29
        {
30
            mp[x * 2] += y / 2;
31
            mp[x] = y % 2;
32
        }
33
    }
34
    int ans = 0;
35
    for (auto cnt : mp)
36
    {
37
        ans += cnt.second;
38
    }
39
    cout << ans << endl;
40
}
41
signed main()
42
{
43
#ifdef NOI_IO
44
    freopen("merging.in", "r", stdin);
45
    freopen("merging.out", "w", stdout);
46
#endif
47
    ios::sync_with_stdio(0);
48
    cin.tie(nullptr), cout.tie(nullptr);
49
#ifdef MULTI_CASES
50
    cin >> T;
51
    while (T--)
52
#endif
53
        Solve();
54
    return 0;
55
}

C2#

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
int n;
5
struct node{
6
    int c,s;
7
}t[100005];
8
map<int,int>a;
9
signed  main(){
10
      freopen("merging.in","r",stdin);
11
      freopen("merging.out","w",stdout);
12
    ios::sync_with_stdio(0);
13
    cin.tie(0);
14
    cout.tie(0);
15
    cin>>n;
16
    for(int i=1;i<=n;i++){
17
        cin>>t[i].s>>t[i].c;
18
    }
19
    for(int i=1;i<=n;i++){
20
        while(t[i].s%2==0){
21
            t[i].s/=2;
22
            t[i].c*=2;
23
        }
24
        a[t[i].s]+=t[i].c;
25
    }
26
    int ans=0;
27
    for(auto i:a){
28
        int x=i.second;
29
        while(x>0){
30
            ans+=x%2;
31
            x/=2;
32
        }
33
    }
34
    cout<<ans;
35
}

B. 龙哥的速递 (delivery)#

Description#

给定一个二维平面，你需要从 $(0.0)$ 移动到 $(n,n)$ 每次移动需要满足以下条件：

只能进行向上或向右的移动
开始时可以向上或右移动，且每次必须移动一段距离。
移动之后必须改变方向，之后重复上述过程。
最多只会改变 $n-1$ 次方向，也就意味着路径最多由 $n$ 条线段组成。

每次转向之后的直线运动会有不同的单位通行费 $c_i$ ，请求出最小的总花费。

Solution#

不难发现，由于终点位于 $(n,n)$ ，所以向上向右两种操作是对称的，只需要考虑一种情况然后同理对称考虑即可。这里将第一次移动认为是向上移动来考虑。

由于”移动之后必须改变方向“，所以最终的路径一定是一条竖直水平线段交替出现的折线，那么也就意味着如果 $i$ 是奇数，一定会是向上移动。同理 $i$ 是偶数，一定会是向右移动。

之后考虑如何求解最小值。既然我们已知路径中所有竖直水平的线段长度之和一定为 $n$ ，那么就需要考虑如何分配使得总通行费最小。考虑贪心地选择单位通行费最小的路段，并尽可能让其分配到的长度最长。

那么其可以分配的最长长度是什么？我们已知每次转向后必须移动一段距离，那么我们让除去刚才那个路段之外的所有路段只移动一单位，那么最小路段分配到的长度就会达到最长的长度。

同理解决水平线段，可以发现时间复杂度为 $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
inline void Solve()
16
{
17
    cin >> N;
18
    for (int i = 1; i <= N; i++)
19
    {
20
        cin >> a[i];
21
    }
22
    int sum1 = 0, sum2 = 0;
23
    int min1 = INF, min2 = INF;
24
    int cnt1 = 0, cnt2 = 0;
25
    int cntx = 0, cnty = 0;
26
    int ans = INF;
27
    for (int i = 1; i <= N; i++)
28
    {
29
        if (i % 2 == 1)
30
        {
31
            cnt1++;
32
            sum1 += a[i];
33
            if (min1 > a[i])
34
            {
35
                min1 = a[i];
36
                cntx = N - cnt1;
37
            }
38
            else
39
            {
40
                cntx = N - cnt1;
41
            }
42
        }
43
        else
44
        {
45
            cnt2++;
46
            sum2 += a[i];
47
            if (min2 > a[i])
48
            {
49
                min2 = a[i];
50
                cnty = N - cnt2;
51
            }
52
            else
53
            {
54
                cnty = N - cnt2;
55
            }
56
        }
57
        if (i != 1)
58
            ans = min(ans, sum1 + cntx * min1 + sum2 + cnty * min2);
59
    }
60
    cout << ans << endl;
61
}
62
signed main()
63
{
64
#ifdef NOI_IO
65
    freopen("delivery.in", "r", stdin);
66
    freopen("delivery.out", "w", stdout);
67
#endif
68
    ios::sync_with_stdio(0);
69
    cin.tie(nullptr), cout.tie(nullptr);
70
#ifdef MULTI_CASES
71
    cin >> T;
72
    while (T--)
73
#endif
74
        Solve();
75
    return 0;
76
}

2025.11.23 NOIP 模拟赛总结&题解

赛后总结#

A. 李大厨的合并艺术 (merging)#

Description#

Solution#

S1#

S2#

Code#

C1#

C2#

B. 龙哥的速递 (delivery)#

Description#

Solution#

Code#