A - Pairing

给定四个整数，统计其中可以组成多少对数值相同的数。由于数值范围仅为 1 到 4，我们可以直接使用数组记录每个数字出现的频率，最后将每个数字的出现次数除以 2 并累加即可。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> freq(5, 0);
    for (int i = 0; i < 4; ++i) {
        int val;
        std::cin >> val;
        freq[val]++;
    }
    int pairs = 0;
    for (int i = 1; i <= 4; ++i) {
        pairs += freq[i] / 2;
    }
    std::cout << pairs << std::endl;
    return 0;
}

B - Garbage Collection

对于每一类垃圾，其收集周期为 $q_i$，在该周期的第 $r_i$ 天进行收集。给定第 $d$ 天，我们需要找到最小的 $x \ge d$，使得 $x \equiv r_i \pmod{q_i}$。

计算逻辑：首先计算 $d \pmod{q_i}$。如果其余数小于等于 $r_i$，则当前周期的第 $r_i$ 天即为答案；否则，需要到下一个周期的第 $r_i$ 天。

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    std::vector<std::pair<int, int>> rules(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> rules[i].first >> rules[i].second;
    }
    int q;
    std::cin >> q;
    while (q--) {
        int t, d;
        std::cin >> t >> d;
        --t;
        int mod = rules[t].first;
        int rem = rules[t].second;
        int current_rem = d % mod;
        if (current_rem <= rem) {
            std::cout << d + (rem - current_rem) << "\n";
        } else {
            std::cout << d + (mod - current_rem + rem) << "\n";
        }
    }
    return 0;
}

C - Repeating

给定一个序列，要求输出每个元素在上一次出现的位置。如果没有出现过，则输出 -1。我们可以使用哈希表（std::map 或 std::unordered_map）来存储每个数值最后一次出现的索引。

#include <iostream>
#include <vector>
#include <map>

int main() {
    int n;
    std::cin >> n;
    std::map<int, int> last_pos;
    for (int i = 1; i <= n; ++i) {
        int a;
        std::cin >> a;
        if (last_pos.find(a) != last_pos.end()) {
            std::cout << last_pos[a] << (i == n ? "" : " ");
        } else {
            std::cout << -1 << (i == n ? "" : " ");
        }
        last_pos[a] = i;
    }
    std::cout << std::endl;
    return 0;
}

D - Manuscript

在 $H \times W$ 的网格中，从任意空白格子出发，寻找长度为 $K$ 且不重复经过格子的路径总数。由于 $H, W$ 最大为 10，$K$ 最大为 11，数据规模很小，可以直接对每个起点进行深度优先搜索（DFS）。

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

int H, W, K;
std::vector<std::string> grid;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

long long dfs(int r, int c, int step, std::vector<std::vector<bool>>& vis) {
    if (step == K) return 1;
    vis[r][c] = true;
    long long res = 0;
    for (int i = 0; i < 4; ++i) {
        int nr = r + dx[i], nc = c + dy[i];
        if (nr >= 0 && nr < H && nc >= 0 && nc < W && grid[nr][nc] == '.' && !vis[nr][nc]) {
            res += dfs(nr, nc, step + 1, vis);
        }
    }
    vis[r][c] = false;
    return res;
}

int main() {
    std::cin >> H >> W >> K;
    grid.resize(H);
    for (int i = 0; i < H; ++i) std::cin >> grid[i];
    long long total = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (grid[i][j] == '.') {
                std::vector<std::vector<bool>> vis(H, std::vector<bool>(W, false));
                total += dfs(i, j, 0, vis);
            }
        }
    }
    std::cout << total << std::endl;
    return 0;
}

E - Modulo Sigma Problem

计算 $\sum_{1 \le l \le r \le N} (\sum_{i=l}^r A_i \pmod M)$。设前缀和 $S_i = (\sum_{j=1}^i A_j) \pmod M$。则区间和取模的结果为： $(S_r - S_{l-1} + M) \pmod M$。 这个式子可以拆解为： - 如果 $S_r \ge S_{l-1}$，结果为 $S_r - S_{l-1}$。 - 如果 $S_r < S_{l-1}$，结果为 $S_r - S_{l-1} + M$。

整体求和可以表示为： $\sum_{r=1}^N (r \cdot S_r - \sum_{i=0}^{r-1} S_i + M \cdot \text{count}(S_i > S_r))$。 我们可以使用树状数组（Fenwick Tree）动态维护前缀和中各个值出现的次数，从而在 $O(\log M)$ 时间内求出 $\text{count}(S_i > S_r)$。

#include <iostream>
#include <vector>

using namespace std;

struct FenwickTree {
    int size;
    vector<int> tree;
    FenwickTree(int n) : size(n), tree(n + 1, 0) {}
    void update(int i, int delta) {
        for (++i; i <= size; i += i & -i) tree[i] += delta;
    }
    int query(int i) {
        int sum = 0;
        for (++i; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }
};

int main() {
    int n;
    long long m;
    cin >> n >> m;
    vector<long long> s(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        long long a;
        cin >> a;
        s[i] = (s[i - 1] + a) % m;
    }
    FenwickTree ft(m + 1);
    long long total_sum = 0;
    long long current_prefix_sum = 0;
    for (int r = 0; r <= n; ++r) {
        long long count_greater = r - ft.query(s[r]);
        total_sum += (long long)r * s[r] - current_prefix_sum + count_greater * m;
        current_prefix_sum += s[r];
        ft.update(s[r], 1);
    }
    cout << total_sum << endl;
    return 0;
}

F - Add One Edge 2

题目要求通过添加一条边形成一个三正则图。这等价于找到两个度数为 2 的点，它们之间的路径上所有点的度数均为 3。 我们可以将所有度数为 3 的点看作连通分量的内部节点，而度数为 2 的点作为与这些分量相邻的"叶子"。 对于每一个由度数为 3 的点构成的连通分量，计算它连接了多少个度数为 2 的点（设为 $C$），则该分量对答案的贡献为 $C(C-1)/2$。

#include <iostream>
#include <vector>

using namespace std;

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

    vector<bool> visited(n + 1, false);
    long long ans = 0;

    for (int i = 1; i <= n; ++i) {
        if (degree[i] == 3 && !visited[i]) {
            vector<int> q;
            q.push_back(i);
            visited[i] = true;
            long long deg2_count = 0;
            int head = 0;
            while(head < q.size()){
                int u = q[head++];
                for(int v : adj[u]){
                    if(degree[v] == 2) deg2_count++;
                    else if(degree[v] == 3 && !visited[v]){
                        visited[v] = true;
                        q.push_back(v);
                    }
                }
            }
            ans += deg2_count * (deg2_count - 1) / 2;
        }
    }
    cout << ans << endl;
    return 0;
}