ABC391(A-F)

A - Lucky Direction ¶

题目大意

给你一个长度为 \(1\) 或 \(2\) 的方向字符串 \(S\)，\(S\) 可能的取值是：

North: N
East: E
West: W
South: S
Northeast: NE
Northwest: NW
Southeast: SE
Southwest: SW

输出 \(S\) 的相反方向。

参考代码

C++

#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    unordered_map<char, char> mp = {{'S', 'N'}, {'N', 'S'}, {'W', 'E'}, {'E', 'W'}};
    string d;
    cin >> d;
    for(auto c : d)
        cout << mp[c];
    return 0;
}

B - Seek Grid ¶

题目大意

给你一个 \(N \times N(1 \le N \le 50)\) 二维矩阵 \(S\) 和一个 \(M \times M(1 \le M \le N)\) 的二维矩阵 \(T\)。已知在 \(S\) 存在一个 \(M \times M\) 的子矩阵等于 \(T\)，输出这个子矩阵的左上角的坐标。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<string> s(n), t(m);
    for (auto &ss : s)
        cin >> ss;
    for (auto &ss : t)
        cin >> ss;

    auto check = [&s, &t, m](int a, int b) -> bool
    {
        for(int i = 0; i < m; i++)
            for(int j = 0; j < m; j++)
                if(s[a+i][b+j] != t[i][j])
                    return false;
        return true;
    };

    for(int a = 0; a + m <= n; a++)
        for(int b = 0; b + m <= n; b++)
            if(check(a, b))
            {
                cout << a + 1 << ' ' << b + 1 << endl;
                return 0;
            }
    return 0;
}

C - Pigeonhole Query ¶

题目大意

有 \(N(2 \le N \le 10^6)\) 个鸽子和 \(N\) 个鸟笼，初始的时候，第 \(i\) 个鸽子在第 \(i\) 个鸟笼中。

给你 \(Q(1 \le Q \le 3 \times 10^5)\) 个询问，询问有两种类型：

1 Q H：将第 \(Q\) 个鸽子移动到第 \(H\) 个鸟笼中。
2：回答有多少个笼子中的鸽子数量大于 \(1\) 只。

参考代码

C++

#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

int main()
{
    int n, q;
    cin >> n >> q;
    vector<int> nest(n+1), cnt(n+1, 1);
    iota(nest.begin(), nest.end(), 0);
    int ans = 0;
    while(q--)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            int p, h;
            cin >> p >> h;
            int from = nest[p];
            if(--cnt[from] == 1)
                ans--;
            if(++cnt[h] == 2)
                ans++;
            nest[p] = h;
        }
        else
            cout << ans << endl;
    }
    return 0;
}

D - Gravity ¶

题目大意

有一个 \(10^9\) 行，\(W\) 列的网格。网格中有 \(N(1 \le W\le N \le 2 \times 10^5)\) 个 \(1 \times 1\) 的方块。初始的时候，第 \(i\) 个方块在 \((X_i, Y_i)\) 位置。

在时刻 \(t = 1, 2, ..., 10^{100}\)，每个方块都会按照以下规则移动：

如果网格的最底行一整行都有方块，则消除最底行的所有方块。
对于剩余的方块，按照从下往上的顺序依次进行以下操作：
- 若方块位于最底行，或其下方相邻单元格已有方块，则不进行任何操作。
- 否则，将方块移动到下方相邻单元格。

给你 \(Q(1 \le Q \le 2 \times 10^5)\) 个询问，每个询问给你两个整数 \(T_i(1 \le T_i \le 10 ^ 9)\) 和 \(A_i(1 \le A_i \le N)\)，你需要回答在第 \(T_i + 0.5\) 时刻第 \(A_i\) 个方块是否还在网格中。

解题思路

首先把所有同一列的方块按照 \(y\) 坐标排序，根据每一列有多少个方块，可以确定最终有多少行会被消除。每一行被消除的时间，是根据最靠上的方块的坐标决定的。所以只需要计算出每一行消除的时间，就能推算出这一行每个对应方块的消除时间。

参考代码

C++

#include <algorithm>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>

using namespace std;

int main()
{
    int n, w;
    cin >> n >> w;
    vector<vector<pair<int, int>>> col(w + 1);
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        col[x].push_back({y, i});
    }
    int len = n;
    for (int i = 1; i <= w; i++)
    {
        len = min(len, (int)col[i].size());
        sort(col[i].begin(), col[i].end());
    }
    vector<int> remove_time(n + 1, numeric_limits<int>::max());
    for (int i = 0; i < len; i++)
    {
        int max_y = 0;
        for (int x = 1; x <= w; x++)
        {
            auto [y, _] = col[x][i];
            max_y = max(max_y, y);
        }
        for (int x = 1; x <= w; x++)
        {
            auto [_, id] = col[x][i];
            remove_time[id] = max_y;
        }
    }
    int q;
    cin >> q;
    while (q--)
    {
        int t, a;
        cin >> t >> a;
        cout << (t >= remove_time[a] ? "No" : "Yes") << '\n';
    }
    return 0;
}

E - Hierarchical Majority Vote ¶

题目大意

对于一个长度为 \(3^n\) 的 \(01\) 序列 \(B = B_1\ B_2\cdots B_{3^n}\)，定义以下操作来获得长度为 \(3^{n-1}\) 的 \(01\) 序列 \(C = C_1\ C_2\cdots C_{3^{n-1}}\)：

从 \(B\) 序列的头部开始，每 \(3\) 个为一组，保留 \(3\) 个数字中的众数，插入到序列 \(C\) 的末尾。即对于 \(i = 1,2, ...,3^{n-1}\)，取出 \(B_{3i-2}, B_{3i-1}, B_{3i}\) 中出现次数最多的值作为 \(C_i\)。

给你一个长度为 \(3^N(1 \le N\le 13)\) 的 \(01\) 序列 \(A = A_1\ A_2\cdots A_{3^N}\)，在对 \(A\) 进行 \(N\) 次操作之后，会得到一个长度为 \(1\) 的序列 \(A' = A'_1\)。

现在，你可以将 \(A\) 序列中的任意位置从 \(0\) 改成 \(1\) 或者从 \(1\) 改成 \(0\)，问：最少要修改多少个位置，才能使 \(A'_1\) 的值发生变化？

解题思路

首先对 \(A\) 进行 \(N\) 次操作得到结果 \(A'_1\)，同时保留每一次操作操作的中间结果。这一步操作的时间复杂度是 \(3^1 + 3^2 + \cdots + 3^N = 3 \times\frac{1-3^N}{1-3} = \frac{3}{2}\times(3^N-1)\)，这样的话，完全可以从结果开始倒推，暴力搜索可以得到结果。

参考代码

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<string> s(n + 1);
    cin >> s[0];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < (int)s[i - 1].size(); j += 3)
        {
            int c = s[i - 1][j] + s[i - 1][j + 1] + s[i - 1][j + 2] - 3 * '0';
            s[i] += c > 1 ? '1' : '0';
        }
    }
    char oc = s[n][0];

    auto dfs = [&s, oc](auto &self, int i, int j) -> int
    {
        if (s[i][j] != oc)
            return 0;
        if (i == 0)
            return 1;
        int cost[3] = {self(self, i - 1, 3 * j), self(self, i - 1, 3 * j + 1), self(self, i - 1, 3 * j + 2)};
        sort(cost, cost + 3);
        return cost[0] + cost[1];
    };

    cout << dfs(dfs, n, 0) << endl;
    return 0;
}

F - K-th Largest Triplet ¶

题目大意

给你三个长度为 \(N(1 \le 2 \times 10 ^5)\) 的正整数序列 \(A = (A_1, A_2, ..., A_N)\)，\(B = (B_1, B_2, ..., B_N)\) 和 \(C = (C_1, C_2, ..., C_N)\)，其中 \(1 \le A_i, B_i, C_i \le 10 ^ 9\)。

对于所有满足 \(1 \le i, j, k \le N\) 的整数三元组 \((i, j, k)\)，一共有 \(N ^ 3\) 个三元组，每个三元组 \((i, j, k)\) 都可以计算出 \(A_iB_j + B_jC_k + C_kA_i\) 的值，求出第 \(K(1 \le K \le \min(N^3, 5 \times 10 ^ 5))\) 大的值。

解题思路

首先将三个序列按降序排序。可以发现，如果固定 \(i\) 和 \(j\) 的值，则 \(k\) 越小的对应值会越大，反之 \(k\) 越大的对应值就会越小。

因此可以维护一个大顶堆，每次从大顶堆中取出 \((i, j, k)\)，然后将 \((i+1, j, k)\)，\((i, j+1, k)\) 和 \((i, j, k + 1)\) 加入堆中。这样一定能找出第 \(K\) 大的值。至多会在堆中加入 \(3K\) 个元素，时间复杂度为 \(O(K\log K)\)

参考代码

C++

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>

using namespace std;
using LL = long long;

struct Node
{
    int i, j, k;
    LL val;
    bool operator<(const Node &other) const { return val < other.val; }
};

int main()
{
    int n;
    LL m;
    cin >> n >> m;
    vector<LL> a(n), b(n), c(n);
    for (auto &x : a)
        cin >> x;
    for (auto &x : b)
        cin >> x;
    for (auto &x : c)
        cin >> x;
    sort(a.begin(), a.end(), greater<int>());
    sort(b.begin(), b.end(), greater<int>());
    sort(c.begin(), c.end(), greater<int>());
    unordered_set<LL> vis;

    auto tag = [m](int i, int j, int k) -> LL
    { return i * m * m + j * m + k; };

    auto val = [&a, &b, &c](int i, int j, int k) -> LL
    { return a[i] * b[j] + a[i] * c[k] + b[j] * c[k]; };

    priority_queue<Node> heap;
    heap.push({0, 0, 0, val(0, 0, 0)});
    vis.insert(tag(0, 0, 0));
    for (int s = 1; s < m; s++)
    {
        auto [i, j, k, v] = heap.top();
        heap.pop();
        if (i + 1 < n && !vis.count(tag(i + 1, j, k)))
        {
            heap.push({i + 1, j, k, val(i + 1, j, k)});
            vis.insert(tag(i + 1, j, k));
        }
        if (j + 1 < n && !vis.count(tag(i, j + 1, k)))
        {
            heap.push({i, j + 1, k, val(i, j + 1, k)});
            vis.insert(tag(i, j + 1, k));
        }
        if (k + 1 < n && !vis.count(tag(i, j, k + 1)))
        {
            heap.push({i, j, k + 1, val(i, j, k + 1)});
            vis.insert(tag(i, j, k + 1));
        }
    }
    cout << heap.top().val;
    return 0;
}

最后更新: 2025-06-17
创建日期: 2025-06-17

ABC391(A-F)

A - Lucky Direction¶

B - Seek Grid¶

C - Pigeonhole Query¶

D - Gravity¶

E - Hierarchical Majority Vote¶

F - K-th Largest Triplet¶

A - Lucky Direction ¶

B - Seek Grid ¶

C - Pigeonhole Query ¶

D - Gravity ¶

E - Hierarchical Majority Vote ¶

F - K-th Largest Triplet ¶