赛后总结

赛时成绩：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

#include <bits/stdc++.h>
using namespace std;
#define NOI_IO
// #define MULTI_CASES
#define ll long long
#define int ll
#define endl '\n'
#define vi vector<int>
#define PII pair<int, int>
const int MaxN = 2e5 + 100;
const int INF = 1e9;
const int mod = 1e9 + 7;
int T = 1, N, M;
int a[MaxN];
map<int, int> mp;
inline void Solve()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        int x, y;
        cin >> x >> y;
        mp[x] += y;
    }
    for (auto cnt : mp)
    {
        int x = cnt.first, y = cnt.second;
        if (y >= 2)
        {
            mp[x * 2] += y / 2;
            mp[x] = y % 2;
        }
    }
    int ans = 0;
    for (auto cnt : mp)
    {
        ans += cnt.second;
    }
    cout << ans << endl;
}
signed main()
{
#ifdef NOI_IO
    freopen("merging.in", "r", stdin);
    freopen("merging.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);
#ifdef MULTI_CASES
    cin >> T;
    while (T--)
#endif
        Solve();
    return 0;
}

C2

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct node{
    int c,s;
}t[100005];
map<int,int>a;
signed  main(){
      freopen("merging.in","r",stdin);
      freopen("merging.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t[i].s>>t[i].c;
    }
    for(int i=1;i<=n;i++){
        while(t[i].s%2==0){
            t[i].s/=2;
            t[i].c*=2;
        }
        a[t[i].s]+=t[i].c;
    }
    int ans=0;
    for(auto i:a){
        int x=i.second;
        while(x>0){
            ans+=x%2;
            x/=2;
        }
    }
    cout<<ans;
}

B. 龙哥的速递 (delivery)

Description

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

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

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

Solution

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

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

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

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

同理解决水平线段，可以发现时间复杂度为 $O(n)$。

Code

#include <bits/stdc++.h>
using namespace std;
#define NOI_IO
#define MULTI_CASES
#define ll long long
#define int ll
#define endl '\n'
#define vi vector<int>
#define PII pair<int, int>
const int MaxN = 2e5 + 100;
const int INF = 1e18;
const int mod = 1e9 + 7;
int T = 1, N, M;
int a[MaxN];
inline void Solve()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> a[i];
    }
    int sum1 = 0, sum2 = 0;
    int min1 = INF, min2 = INF;
    int cnt1 = 0, cnt2 = 0;
    int cntx = 0, cnty = 0;
    int ans = INF;
    for (int i = 1; i <= N; i++)
    {
        if (i % 2 == 1)
        {
            cnt1++;
            sum1 += a[i];
            if (min1 > a[i])
            {
                min1 = a[i];
                cntx = N - cnt1;
            }
            else
            {
                cntx = N - cnt1;
            }
        }
        else
        {
            cnt2++;
            sum2 += a[i];
            if (min2 > a[i])
            {
                min2 = a[i];
                cnty = N - cnt2;
            }
            else
            {
                cnty = N - cnt2;
            }
        }
        if (i != 1)
            ans = min(ans, sum1 + cntx * min1 + sum2 + cnty * min2);
    }
    cout << ans << endl;
}
signed main()
{
#ifdef NOI_IO
    freopen("delivery.in", "r", stdin);
    freopen("delivery.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);
#ifdef MULTI_CASES
    cin >> T;
    while (T--)
#endif
        Solve();
    return 0;
}