JoeyDDong.
EN
1 min read中文

AtCoder Beginner Contest 378 Summary

本文是 AtCoder Beginner Conteset（ABC）378 的总结笔记。

A - Pairing

Problem：A - Pairing

省略。

// Problem: https://atcoder.jp/contests/abc378/tasks/abc378_a

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

int f[4];

void solve() {
    for (int i = 0; i < 4; i++) {
        int c;
        cin >> c;
        f[c]++;
    }

    int res = 0;
    for (int i = 1; i <= 4; i++)
        res += f[i] / 2;

    cout << res << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

B - Garbage Collection

Problem：B - Garbage Collection

模拟题。

省略。

// Problem: https://atcoder.jp/contests/abc378/tasks/abc378_b

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 110;
int q[N], r[N];
int n, Q;

void solve() {
    // 读入数据
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> q[i] >> r[i];

    cin >> Q;
    for (int i = 1, t, d; i <= Q; i++) {
        cin >> t >> d;
        int tmp = d % q[t];

        // 如果 tmp 在 r[t] 前面，说明本轮就可以扔
        if (tmp <= r[t])
            cout << d + (r[t] - tmp) << endl;
        // 否则要等到下一轮才能扔
        else
            cout << d + q[t] - tmp + r[t] << endl;
    }
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

C - Repeating

Problem：C - Repeating

STL

输出一个数字前面，离他最近的相同数字的位置。没有就输出 -1。

思路非常的简单，使用一个 unordered_map 来存储每个数字的出现位置。

// Problem: https://atcoder.jp/contests/abc378/tasks/abc378_c

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

int n, a;
unordered_map<int, int> q;
void solve() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a;
        if (!q.count(a))
            cout << -1 << " ";
        else
            cout << q[a] << " ";

        q[a] = i;
    }
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

D - Count Simple Paths

Problem：D - Count Simple Paths

DFS。

一道非常标准的 DFS 题目。难度不大。

// Problem: https://atcoder.jp/contests/abc378/tasks/abc378_d

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 15;
string g[N];    // 存储网格
bool st[N][N];  // 存储遍历状态
int n, m, k;
int res;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x, int y, int k) {
    if (k == 0) {
        res++;
        return;
    }

    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];

        if (a < 1 || a > n || b < 1 || b > m)
            continue;
        if (g[a][b] == '#' || st[a][b])
            continue;

        st[a][b] = true;
        dfs(a, b, k - 1);
        st[a][b] = false;
    }
}

void solve() {
    // 读入数据，1-base
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> g[i];
        g[i] = " " + g[i];
    }

    // 对于每个点都 DFS 一遍
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (g[i][j] == '#')
                continue;

            st[i][j] = true;
            dfs(i, j, k);
            st[i][j] = false;
        }

    cout << res << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

E - Mod Sigma Problem

Problem：E - Mod Sigma Problem

推公式 + 树状数组BIT

题目：

给定一组长度为 NN 的序列 (A1,A2,...,AN)(A_1 , A_2 , ... , A_N)，给定一个正整数 MM。

求 ∑1≤l≤r≤N((∑l≤i≤rAi)modM) \sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right)。

约束条件：

1≤N≤2×1051 \leq N \leq 2 \times 10^5

1≤M≤2×1051 \leq M \leq 2 \times 10^5

0≤Ai≤1090 \leq A_i \leq 10^9

思路 ：

本题整体需要解决下面两个问题：

问题 1：公式化简

我们定义带模前缀和为 Si=(A1+A2+...+Ai) mod MS_i = (A_1+A_2+...+A_i) \bmod M

那么我们就可以将原公式转化为 ∑1≤l≤r≤N((∑l≤i≤rAi)modM)=∑1≤l≤r≤N(Sr−Sl−1) mod M \sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right) = \sum_{1 \leq l \leq r \leq N}(S_r - S_{l-1}) \bmod M

根据常用的知识点：

(Sr−Sl−1)modM=Sr−Sl−1+{0(Sl−1≤Sr)M(Sl−1>Sr) (S_r - S_{l-1}) \mathbin{\mathrm{mod}} M = S_r - S_{l-1} + \begin{cases} 0 & (S_{l-1} \leq S_r) \\ M & (S_{l-1} > S_r)\end{cases}

，我们就可以将 mod 符号从公式中去除掉，原公式转化为：

∑r=1N∑l=1r(Sr−Sl−1)modM=∑r=1N(Sr×r−∑l=1rSl−1+M×Xr) \sum_{r=1}^N \sum_{l=1}^r (S_r - S_{l-1}) \mathbin{\mathrm{mod}} M = \sum_{r=1}^N \left( S_r \times r - \sum_{l=1}^r S_{l-1} + M \times X_r \right)

备注：照理说前缀和中，SiS_i 是单调递增的，为什么会出现逆序对呢？

本题中使用的是带模前缀和，所以真实的 SiS_i 值会呈现周期性的变化，当超过 MM 时候，又会跳回到一个比较小的数值范围，所以就可能出现 Si>Sj,(i<j)S_i > S_j, (i < j) 的情况出现，就对应了本题中需要加入一个偏置 M 把结果“扳正”的情况。

从上面公式可以发现，公式最后可以被拆成 3 个部分：

  • ∑r=1N(Sr×r)\sum_{r=1}^N(S_r \times r)：直接使用预处理好的带模前缀和计算，时间复杂度为 O(N)O(N)

  • −∑r=1N∑l=1rSl−1- \sum_{r=1}^N\sum_{l=1}^r S_{l-1}：类似于前缀和的前缀和，拆开之后可以发现下图规律。化简结果为：−∑l=1N(Sl−1×(N+1−l))- \sum_{l=1}^N (S_{l-1}\times (N+1-l))。时间复杂度 O(N)O(N)。

    image-20241227153446971

  • M×∑r=1NXrM\times \sum_{r=1}^N X_r：问题就转化为，如何快速求出带模前缀和 s 的所有逆序对数量？ 使用树状数组 BIT 来解决。

问题 2：使用 BIT 求逆序对

逆序对的定义是：找到所有的 (i,j)(i,j) 使得 i<ji < j 并且 a[i]>a[j]a[i] > a[j]。

如何使用 BIT 求逆序对的数量呢？

假设从左向右遍历数组，当处理到 s[i]s[i] 的时候，数组 s[1],s[2],...,s[i−1]{s[1] , s[2] , ... , s[i-1]} 都已经被放入了 BIT 中。将数字 s[i]s[i] 作为 index，将出现次数作为 BIT 内存的值。我们可以很容易就求出，已经存入的数字中，比 s[i]s[i] 小的数字有 query(s[i])query(s[i]) 个。相应的，比 s[i]s[i] 大的数字数量为 i−1−query(s[i])i-1-query(s[i])

这一步的时间复杂度为 O(Nlog⁡N)O(N\log N)

总结：

本题的整体思路为：首先将公式进行推到化简，可以发现分别求出三个部分的值就可以得出最终的结果。最麻烦的是如何求整体的逆序对数量，这里使用了 BIT 的数据结构。

整体的时间复杂度为 O(2×N+Nlog⁡N)O(2\times N + N\log N)。

// Problem: https://atcoder.jp/contests/abc378/tasks/abc378_e

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10;
int n, m;
int a[N];   // 储存原数组
int s[N];   // 储存：带模前缀和
int tr[N];  // BIT

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

// 更新 BIT 的值
void add(int x, int k) {
    x++;
    for (int i = x; i <= N; i += lowbit(i))
        tr[i] += k;
}

// 求前x个数的数量和
int sum(int x) {
    x++;
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

void solve() {
    // 读入数据
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        // 预处理带模前缀和
        s[i] = (s[i - 1] + a[i]) % m;
    }

    LL res = 0;
    // 计算公式的第一部分
    for (int r = 1; r <= n; r++)
        res += 1ll * s[r] * r;
    // 计算公式的第二部分
    for (int l = 1; l <= n; l++)
        res -= 1ll * s[l - 1] * (n - l + 1);

    // 计算逆序对
    LL cnt = 0;
    for (int i = 1; i <= n; i++) {
        cnt += (i - 1 - sum(s[i]));
        add(s[i], 1);
    }
    // 计算公式第三部分
    res += 1ll * m * cnt;

    // 输出结果
    cout << res << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

F - Add One Edge 2

Problem：F - Add One Edge 2

题目：

给定一个树，有 N 个节点，N-1 条边。

给树增加一条边，能把树变成恰好带一个环的图。

请问有多少个图满足条件：简单图，环上的所有顶点读数为 3。

约束条件：

3≤N≤2×1053 \leq N \leq 2 \times 10^5

1≤ui,vi≤N1 \leq u_i, v_i \leq N

思路：

这道题目结论比较暴力：

​ 直接找度数为 33 的连通块，然后向外找度数为 22 的点。假设度数为 22 的点数量为 cntcnt，那么这些度数为 22 的点直接两两相连，都能形成题目要求的环。形成环的数量为 cnt×(cnt−1)/2cnt\times (cnt-1) / 2

由于是把所有的点都看过，所以极限状态下的时间复杂度为 O(2N)O(2N)。

image-20241227172545381 
// Problem: https://atcoder.jp/contests/abc378/tasks/abc378_f

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10, M = 4e5 + 10;
int h[N], e[M], ne[M], idx;  // 存储图
int n;
int deg[N];  // 记录度数
bool st[N];  // 记录是否被看过
int cnt;     // 记录点的数量
LL res;      // 记录结果

// 建图加边
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

// DFS
void dfs(int now, int fa = 0) {
    // 如果当前点度数不为 3
    if (deg[now] != 3) {
        // 如果度数是 2，就计数
        cnt += (deg[now] == 2);
        return;
    }

    // 此点标记
    st[now] = true;
    // 看一下周围的点
    for (int i = h[now]; i != -1; i = ne[i]) {
        int next = e[i];
        // 如果是来时的点就跳过
        if (next == fa)
            continue;
        // 向下搜
        dfs(next, now);
    }
}

void solve() {
    // h 数组初始化
    memset(h, -1, sizeof h);

    // 读入数据，同时预处理各个节点的度数
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
        deg[u]++, deg[v]++;
    }

    // 依次遍历每个节点
    for (int i = 1; i <= n; i++) {
        // 度数不为 3，直接跳过
        if (deg[i] != 3)
            continue;
        // 如果这个点已经看过了，跳过
        if (st[i])
            continue;

        // 计算当前连通块，周围度数为 2 的点的数量
        cnt = 0;
        dfs(i);
        res += 1ll * cnt * (cnt - 1) / 2;
    }

    // 输出结果
    cout << res << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}
Programming#Algorithm#Programming Contest#AtCoder#ABC
Back to articles ←