ABC378(A-F)

A - Pairing ¶

题目大意

给你 $4$ 个球，第 $i$ 个球的颜色是 $A_i$。你可以执行以下操作任意次：

选择两个颜色相同的球，将他们丢弃。

问：最多能执行几次操作？

参考代码

C++

#include <iostream>
#include <unordered_set>

using namespace std;

int main()
{
    unordered_set<int> set;
    int ans = 0;
    for(int i = 0; i < 4; i++)
    {
        int x;
        cin >> x;
        auto it = set.find(x);
        if(it != set.end())
        {
            ans++;
            set.erase(it);
        }
        else
            set.insert(x);
    }
    cout << ans << endl;
    return 0;
}

B - Garbage Collection ¶

题目大意

某个城市有 $N(1 \le N \le 100)$ 种类型的垃圾，每一种类型的垃圾都有固定的回收时间。第 $i$ 种类型的垃圾的回收时间由 $q_i$ 和 $r_i$ 两个数字描述，表示会在第 $r_i, r_i + q_i, r_i + 2q_i, r_i + 3q_i, ...$ 天的晚上回收垃圾。其中 $0 \le r_i < q_i \le 10 ^ 9$

你需要回答 $Q(1 \le Q \le 100)$ 个询问，每个询问包括两个数字 $t$ 和 $d$，你需要回答：如果在第 $d$ 天的白天产生了类型为 $t$ 的垃圾，则这个垃圾下一次被回收是在第几天？注意：因为垃圾回收总是在晚上，所有有可能当天的垃圾可以被当天回收。

解题思路

求出 $k = \lfloor \frac{d}{q_t} \rfloor$，$x = d \bmod q_t$，如果 $x \le r_t$，则答案就是 $r_t + kq_t$。否则答案就是 $r_t + (k+1)q_t$。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n;
    vector<int> q(n+1), r(n+1);
    for(int i = 1; i <= n; i++)
        cin >> q[i] >> r[i];
    cin >> m;
    while(m--)
    {
        int t, d;
        cin >> t >> d;
        int x = d % q[t], k = d / q[t];
        if(x > r[t])
            k++;
        cout << r[t] + k * q[t] << endl;
    }
    return 0;
}

C - Repeating ¶

题目大意

给你一个长度为 $N(2 \le N \le 2 \times 10 ^ 5)$ 的序列 $A = (A_1, A_2, ..., A_N)$。

对于每个 $i = 1, 2, ..., N$，回答以下问题：

是否存在 $1 \le j < i$ 满足 $A_j = A_i$？如果存在这样的 $j$，输出最大的 $j$。如果不存在这样的 $j$，输出 -1

解题思路

用哈希表存一下每个数字上一次出现的坐标即可。

参考代码

C++

#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    int n;
    cin >> n;
    unordered_map<int, int> last;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        auto it = last.find(x);
        if(it == last.end())
        {
            cout << -1 << ' ';
            last[x] = i;
        }
        else
        {
            cout << it->second << ' ';
            it->second = i;
        }
    }
    return 0;
}

D - Count Simple Paths ¶

题目大意

给你一个 $H \times W(1 \le H, W \le 10)$ 的网格，每个格子要么是 # 表示有障碍物，要么是 . 表示没有障碍物。

问：有多少条满足以下条件的路径？

从任意一个没有障碍物的格子出发。
每一步可以移动到上下左右的相邻格子中。
不能进入有障碍物的格子。不能进入到已经走过的格子。
路径长度为 $K$（移动恰好 $K$ 次）。

解题思路

dfs 模板题。

参考代码

C++

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

using namespace std;

const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<string> g(n);
    for (int i = 0; i < n; i++)
        cin >> g[i];
    int ans = 0;

    auto in_graph = [n, m](int r, int c) -> bool
    { return r >= 0 && r < n && c >= 0 && c < m; };

    auto dfs = [&in_graph, &g, &ans, k](auto &self, int r, int c, int dep) -> void
    {
        if (dep == k)
        {
            ans++;
            return;
        }
        g[r][c] = '#';
        for (int i = 0; i < 4; i++)
        {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (in_graph(nr, nc) && g[nr][nc] == '.')
                self(self, nr, nc, dep + 1);
        }
        g[r][c] = '.';
    };

    for (int r = 0; r < n; r++)
        for (int c = 0; c < m; c++)
            if (g[r][c] == '.')
                dfs(dfs, r, c, 0);
    cout << ans << endl;
    return 0;
}

E - Mod Sigma Problem ¶

题目大意

给你一个长度为 $N(1 \le N \le 2 \times 10 ^ 5)$ 的序列 $A = (A_1, A_2, ..., A_N)$ 和一个整数 $M(1 \le M \le 2 \times 10 ^ 5)$。求出 $\sum\limits_{1 \le l \le r \le N}((\sum\limits_{l \le i \le r}A_i) \bmod M)$

解题思路

预处理出前缀和，等价于求出 $\sum\limits_{1 \le l \le r \le N}((s[r]-s[l-1]) \bmod M)$，因为要模 $M$，首先将每个前缀和模 $M$ ，这样可以保证 $0 \le s[i] < M$，于是我们可以将模 $M$ 减法进行拆分： $$ s[r]-s[l-1] = \left{ \begin{matrix} s[r] - s[l-1], & \text{if} s[l-1] \le s[r] \ s[r] - s[l-1] + M, & \text{if} s[l-1] > s[r] \end{matrix} \right. $$ 这样，在固定 $r$ 的时候，只需要求出前面有多少个 $s[l-1]$ 比 $s[r]$ 小（树状数组维护每个数字出现的次数即可），同时预处理出前缀和的前缀和，再把剩下的 $M$ 补上就好。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

struct FenwickTree
{
    int n;
    vector<int> t;

    FenwickTree(int n) : n(n + 1), t(n + 2) {}

    int lowbit(int x) const { return x & -x; }

    void add(int x, int k)
    {
        x++;
        for (; x <= n; x += lowbit(x))
            t[x] += k;
    }

    int prefix(int x) const
    {
        x++;
        int sum = 0;
        for (; x; x -= lowbit(x))
            sum += t[x];
        return sum;
    }

    int query(int l, int r) const { return prefix(r) - prefix(l - 1); }
};

int main()
{
    int n, m;
    cin >> n >> m;
    FenwickTree t(m);
    LL ans = 0, sum = 0;
    LL sr = 0;
    for (int i = 1; i <= n; i++)
    {
        int a;
        cin >> a;
        sr = (sr + a) % m;
        LL cnt = t.query(sr + 1, m);
        ans += i * sr - sum + cnt * m;
        sum += sr;
        t.add(sr, 1);
    }
    cout << ans << endl;
    return 0;
}

F - Add One Edge 2 ¶

题目大意

给你一棵 $N(3 \le N \le 2 \times 10 ^ 5)$ 个点的树，你可以在任意两点间添加恰好一条边，这会导致图中存在一个环。问：有多少种加边的方式可以让恰好添加一条边的图满足以下条件？

加边后的图仍然是简单图。
图中环上所有的点的度数都是 $3$

解题思路

加上去的边一定是环上的边，而加边会让两个点的度数都 $+1$，所以一定是在两个度数为 $2$ 的两个点之间加边。

先考虑简单的情况，设有一个点 $w$，且 $w$ 有孩子 $u$ 和 $v$，如果 $d[u] = 2$ 且 $d[v] = 2$ 且 $d[w] = 3$，那么就可以连上 $u$ 和 $v$ 的边满足条件。进一步可以发现，如果 $w$ 有 $2$ 个度数为 $2$ 的孩子，就有 $1$ 种连线方案，如果有 $3$ 个度数为 $2$ 的孩子，就有 $3$ 种连线方案。

但这种做法还不够完善。一般的，设 $u$ 和 $v$ 的 lca 是 $w$，如果 $w$ 到 $u$ 以及 $w$ 到 $v$ 这两条路径的节点度数都是 $3$，且 $d[u] = 2$ 且 $d[v] = 2$，连上 $u$ 和 $v$ 的边也是满足条件的。为了处理这种情况，只需要把所有度数为 $3$ 且相邻的点合并成 $1$ 个，然后枚举这些度数为 $3$ 的节点有多少个度数为 $2$ 的孩子就可以。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> edge(n + 1);
    vector<int> deg(n + 1);
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }
    vector<int> p(n + 1);
    for(int u = 1; u <= n; u++)
        p[u] = u;

    auto dfs_for_merge = [&edge, &p, &deg](auto &self, int u, int fa) -> void
    {
        for(auto v : edge[u])
        {
            if(v == fa)
                continue;
            if(deg[u] == 3 && deg[v] == 3)
                p[v] = p[u];
            self(self, v, u);
        }
    };

    dfs_for_merge(dfs_for_merge, 1, 0);
    vector<int> two_deg_child_cnt(n + 1);
    for(int u = 1; u <= n; u++)
    {
        int pu = p[u];
        if(pu != u)
        {
            for(auto v : edge[u])
                if(deg[v] == 2)
                    two_deg_child_cnt[pu]++;
        }
        else if(deg[u] == 3)
        {
            for(auto v : edge[u])
                if(deg[v] == 2)
                    two_deg_child_cnt[u]++;
        }
    }
    LL ans = 0;
    for(int u = 1; u <= n; u++)
    {
        LL c = two_deg_child_cnt[u];
        ans += c * (c - 1) / 2;
    }
    cout << ans << endl;
    return 0;
}

最后更新: 2024-12-26
创建日期: 2024-12-26

ABC378(A-F)

A - Pairing¶

B - Garbage Collection¶

C - Repeating¶

D - Count Simple Paths¶

E - Mod Sigma Problem¶

F - Add One Edge 2¶

A - Pairing ¶

B - Garbage Collection ¶

C - Repeating ¶

D - Count Simple Paths ¶

E - Mod Sigma Problem ¶

F - Add One Edge 2 ¶