链接：https://atcoder.jp/contests/abc437

A – Feet

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int a, b;
    cin >> a >> b;
    cout << a * 12 + b << endl;
}

B – Tombola

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> a(n, vector<int>(m));
    for (auto &v : a)
        for (auto &x : v)
            cin >> x;

    map<int, int> cnt;
    while (q--)
    {
        int x;
        cin >> x;
        ++cnt[x];
    }

    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int cur = 0;
        for (int j = 0; j < m; ++j)
        {
            if (cnt[a[i][j]])
                ++cur;
        }

        ans = max(ans, cur);
    }

    cout << ans << endl;
}

C – Reindeer and Sleigh 2

算法：

    模拟。

思路：

    定义所有驯鹿的集合 \(U\)，坐雪橇的驯鹿 \(S\)，拉雪橇的驯鹿 \(T\)。

    找到满足以下条件且使得最多的驯鹿坐雪橇：

\(\sum_{i \in S} W_i \le \sum_{i \in T} P_i\)

    其中：

\(\sum_{i \in S} W_i = \sum_{i \in U} W_i – \sum_{i \in T} W_i\)

    那么原式等于：

\(\sum_{i \in U} W_i – \sum_{i \in T} W_i \le \sum_{i \in T} P_i\)

    移项得：

\(\sum_{i \in U} W_i \le \sum_{i \in T} P_i + \sum_{i \in T} W_i\)

    此时问题转换为：找到满足 \(P_i + W_i\) 小于总的 \(W_i\) 且驯鹿数量最多的个数。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    ll sum = 0;
    for (int i = 0; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        a[i] = x + y;
        sum += x;
    }

    ranges::sort(a, greater<>());

    ll cur = 0;
    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        cur += a[i];
        ++ans;
        if (cur >= sum)
            break;
    }

    cout << n - ans << endl;
}

D – Sum of Differences

算法：

    排序，二分，前缀和，贡献法。

思路：

    在本网站别处有详细讲解，不过多赘述。

    全区间函数值求和问题 – MiyanLog

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;
    vector<ll> a(n + 1), b(m + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= m; ++i)
        cin >> b[i];

    ranges::sort(a);
    ranges::sort(b);

    vector<ll> sum(m + 1, 0);
    for (int i = 1; i <= m; ++i)
        sum[i] = sum[i - 1] + b[i];

    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        auto it = upper_bound(b.begin() + 1, b.end(), a[i]);

        int cnt = it - b.begin() - 1;

        ans = (ans + (cnt * a[i] - sum[cnt]) % MOD) % MOD;
        ans = (ans + (sum[m] - sum[cnt]) - (m - cnt) * a[i]) % MOD;
    }

    cout << ans << endl;
}

E – Sort Arrays

算法：

    \(dfs\)，图论，字典树。

思路：

    观察到 \(i\) 序列是由 \(x\) 序列添加一个数字 \(y\) 构造而成。

    不难想到建图，将 \(x\) 序列到 \(i\) 序列建一条边权为 \(y\) 的边。

    那么答案就是前序遍历，遍历的时候每个节点优先枚举边权小的节点。

    但是这种情况会有一个 \(bug\)，一个点 \(u\) 可能会有很多边权相等的节点 \(v_i\)，这些节点在遍历时不好处理，要寻求其他的方法。

    考虑将点优化成点集，即一个点集里会有很多边权相同的点，将这些点看成一个点集，并赋予一个 \(id\)，使用这些点集的 \(id\) 建图，使用一个结构存储每个点集下都有什么节点。

    遍历的时候优先考虑边权小的节点，这里可以使用字典树优化，由于边权的值域很大且是离散的，可以将字典树的第二维换成 \(map\) 以使得优化。

关键代码：

void miyan()
{
    int n;
    cin >> n;

    int idx = 1;
    vector<int> id(n + 1);
    vector<map<int, int>> tr(n + 1);
    vector<vector<int>> g(n + 1);
    for (int v = 1; v <= n; ++v)
    {
        int u, w;
        cin >> u >> w;

        int pu = id[u];

        if (!tr[pu].count(w))
            tr[pu][w] = idx++;

        int pv = tr[pu][w];
        id[v] = pv;
        g[pv].push_back(v);
    }

    auto dfs = [&](auto &&self, int u) -> void
    {
        for (auto x : g[u])
            cout << x << ' ';

        for (auto [x, y] : tr[u])
            self(self, y);
    };

    dfs(dfs, 0);
}

F – Manhattan Christmas Tree 2

算法：

    线段树，曼哈顿距离。

思路：

    曼哈顿距离有一个经典利用绝对值和 \(max\) 的关系进行分类讨论的技巧：

    由于 \(|x| + |y| = max(x + y, x – y, – x + y, – x – y)\)

    那么 \(|x – x1| + |y – y1|\) 有以下四种情况：

• \((x – x1) + (y – y1) = x + y – (x1 + y1)\)
• \((x – x1) – (y – y1) = x – y – (x1 – y1)\)
• \(– (x – x1) + (y – y1) = – (x – y) + (x1 – y1)\)
• \(– (x – x1) – (y – y1) = – (x + y) + (x1 + y1)\)

    其中 \(x, y\) 为常量，\(x1, y1\) 为变量，定义 \(S1 = x1 + y1, S2 = x1 – y1\)

    代入原式得：

• \(x + y – min(S1)\)
• \(x – y – min(S2)\)
• \(– (x – y) + max(S2)\)
• \(– (x + y) + max(S1)\)

    开一颗线段树，维护 max(S1), max(S2), min(S1), min(S2) 即可。

关键代码：

vector<ll> s1, s2;

struct Node
{
    int l, r;
    ll max_s1, max_s2, min_s1, min_s2;
} tr[N << 2];

void pushup(int u)
{
    tr[u].max_s1 = max(tr[u << 1].max_s1, tr[u << 1 | 1].max_s1);
    tr[u].max_s2 = max(tr[u << 1].max_s2, tr[u << 1 | 1].max_s2);
    tr[u].min_s1 = min(tr[u << 1].min_s1, tr[u << 1 | 1].min_s1);
    tr[u].min_s2 = min(tr[u << 1].min_s2, tr[u << 1 | 1].min_s2);
}

void build(int u, int l, int r)
{
    if (l == r)
    {
        tr[u] = {l, r, s1[l], s2[l], s1[l], s2[l]};
        return;
    }

    tr[u] = {l, r};
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

ll query_max_s1(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].max_s1;

    int mid = tr[u].l + tr[u].r >> 1;
    ll ans = INT_MIN;
    if (l <= mid)
        ans = max(ans, query_max_s1(u << 1, l, r));
    if (r > mid)
        ans = max(ans, query_max_s1(u << 1 | 1, l, r));
    return ans;
}

ll query_max_s2(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].max_s2;

    int mid = tr[u].l + tr[u].r >> 1;
    ll ans = INT_MIN;
    if (l <= mid)
        ans = max(ans, query_max_s2(u << 1, l, r));
    if (r > mid)
        ans = max(ans, query_max_s2(u << 1 | 1, l, r));
    return ans;
}

ll query_min_s1(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].min_s1;

    int mid = tr[u].l + tr[u].r >> 1;
    ll ans = INT_MAX;
    if (l <= mid)
        ans = min(ans, query_min_s1(u << 1, l, r));
    if (r > mid)
        ans = min(ans, query_min_s1(u << 1 | 1, l, r));
    return ans;
}

ll query_min_s2(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].min_s2;

    int mid = tr[u].l + tr[u].r >> 1;
    ll ans = INT_MAX;
    if (l <= mid)
        ans = min(ans, query_min_s2(u << 1, l, r));
    if (r > mid)
        ans = min(ans, query_min_s2(u << 1 | 1, l, r));
    return ans;
}

void update(int u, int x, ll val1, ll val2)
{
    if (tr[u].l == x && tr[u].r == x)
    {
        tr[u].max_s1 = val1;
        tr[u].max_s2 = val2;
        tr[u].min_s1 = val1;
        tr[u].min_s2 = val2;
        return;
    }

    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid)
        update(u << 1, x, val1, val2);
    else
        update(u << 1 | 1, x, val1, val2);
    pushup(u);
}

void miyan()
{
    int n, Q;
    cin >> n >> Q;

    vector<pii> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i].first >> a[i].second;

    s1.resize(n + 1);
    s2.resize(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        s1[i] = a[i].first + a[i].second;
        s2[i] = a[i].first - a[i].second;
    }

    build(1, 1, n);

    while (Q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            ll i, x, y;
            cin >> i >> x >> y;

            update(1, i, x + y, x - y);
        }
        else
        {
            ll L, R, x, y;
            cin >> L >> R >> x >> y;

            ll max_s1 = query_max_s1(1, L, R);
            ll max_s2 = query_max_s2(1, L, R);
            ll min_s1 = query_min_s1(1, L, R);
            ll min_s2 = query_min_s2(1, L, R);

            ll ans1 = x + y - min_s1;
            ll ans2 = x - y - min_s2;
            ll ans3 = -x + y + max_s2;
            ll ans4 = -x - y + max_s1;

            cout << max({ans1, ans2, ans3, ans4}) << endl;
        }
    }
}

G – Colorful Christmas Tree

    还没补。