2024.09.17模拟赛总结

破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了破防了

$ T1 $

怎么每次 $ rfy $ 模拟赛，$ T1 $ 都这么难。
想了大半场比赛，结果还没做出来，要是换成 $ T2 $ 应该能过。

$ T2 $

一直在想 $ T1 $，结果 $ T2 $ 只打了个暴力，$ T2 $ 相对 $ T1 $ 还是容易的。
设 $ f_{i, x, y} $ 表示前 $ i $ 个数，$ 1 $ 抽出 $ x $ 个，$ 2 $ 抽出 $ y $ 个的车数和最后一辆车的装载量（是 $ pair $ 类型，甚至没有看到 $ a_i = 1/2 $）。
然后转移先不考虑抽出的装载，只考虑在原序列中的装载，抽出的到最后再计算。
则 $ f_{i, x, y} = min(f_{i - 1, x - 1, y}[x > 0], f_{i - 1, x, y - 1}[y > 0], f[i - 1][x][y] + a[i]) $， $ + a_i $ 可以重载运算符一下，$ x, y $ 的范围用前缀和预处理出前 $ i $ 个数中 $ 1/2 $ 的个数。
最后答案在 $ f[n][x][y] $ 统计即可。
注意到会 $ MLE $，所以需要开个滚动数组优化一下空间。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define need(x) (bool)x.flow + x.cnt_car
#define sum(x) x.cnt_car * w + x.flow

using namespace std;

const int N = 410;

int n, w;
int a[N], sum1[N], sum2[N];
struct sb
{
    int cnt_car, flow;
} f[2][N][N];

sb operator + (sb a, int b)
{
    return {a.flow + b >= w ? a.cnt_car + 1 : a.cnt_car, a.flow + b == w ? 0 : a.flow + b > w ? b : a.flow + b};
}

sb mn(sb a, sb b)
{
    return a.cnt_car >= inf ? b : b.cnt_car >= inf ? a : sum(a) > sum(b) ? b : a;
}

int main()
{
    freopen("pack.in", "r", stdin);
    freopen("pack.out", "w", stdout);

    cin >> n >> w;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    for (int i = 1; i <= n; i ++ )
        sum1[i] = sum1[i - 1] + (a[i] == 1),
        sum2[i] = sum2[i - 1] + (a[i] == 2);
    // for (int i = 1; i <= n; i ++ ) cout << sum1[i] << ' ' << sum2[i] << '\n';
    memset(f, 0x3f, sizeof f);
    f[0][0][0] = {0, 0};
    for (int i = 1; i <= n; i ++ )
    {
        for (int x = 0; x <= sum1[i]; x ++ )
            for (int y = 0; y <= sum2[i]; y ++ )
            {
                f[i & 1][x][y] = {inf, inf};
                if (x && a[i] == 1) f[i & 1][x][y] = mn(f[i & 1][x][y], f[(i - 1) & 1][x - 1][y]);
                if (y && a[i] == 2) f[i & 1][x][y] = mn(f[i & 1][x][y], f[(i - 1) & 1][x][y - 1]);
                f[i & 1][x][y] = mn(f[i & 1][x][y], f[(i - 1) & 1][x][y] + a[i]);
                // cout << (f[(i - 1) & 1][x][y] + a[i]).cnt_car << '\n';
            }
    }

    // cout << inf * 10 << '\n';
    // for (int x = 0; x <= sum1[n]; x ++ )
    //     for (int y = 0; y <= sum2[n]; y ++ )
    //         cout << f[n & 1][x][y].cnt_car*w+f[n&1][x][y].flow << "\n"[y != sum2[n]];
    int res = inf, mi = inf;
    for (int x = 0; x <= sum1[n]; x ++ )
        for (int y = 0; y <= sum2[n]; y ++ )
        {
            auto tmp = f[n & 1][x][y];
            // cout << tmp.cnt_car << ' ' << tmp.flow << '\n';
            int tx = x, ty = y;
            while (tx || ty)
            {
                if (tx && (!ty || tmp.flow + 2 > w)) tx -- , tmp = tmp + 1;
                else ty -- , tmp = tmp + 2;
            }
            // cout << tmp.cnt_car << ' ' << tmp.flow << '\n';
            // cout << need(tmp) << '\n';
            if (mi > need(tmp))
            {
                mi = need(tmp);
                res = x + y;
            }
            else if (mi == need(tmp)) res = min(res, x + y);
        }

    cout << res << '\n';

    return 0;
}

$ T3 $

$ T4 $