AtCoder Beginner Contest 378

Lazy_boy_2024-11-222025-03-31

A.Pairing

题目描述

There are four balls, and the color of the $i$-th ball is $A_i$.
Find the maximum number of times you can perform this operation: choose two balls of the same color and discard both.

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  std::map<int, int> mp;
  for(int i = 0; i < 4; i++) {
    int x;
    std::cin >> x;
    mp[x]++;
  }

  int s = 0;
  for(auto [x, y] : mp) {
    s += y / 2;
  }
  std::cout << s << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

B.Garbage Collection

Garbage Collection

题目描述

In AtCoder City, $N$ types of garbage are collected regularly. The $i$-th type of garbage $(i=1,2,\dots,N)$ is collected on days when the date modulo $q_i$ equals $r_i$.
Answer $Q$ queries. In the $j$-th query $(j=1,2,\dots,Q)$, given that the $t_j$-th type of garbage is put out on day $d_j$, answer the next day on which it will be collected.
Here, if the $i$-th type of garbage is put out on a day when that type of garbage is collected, then the garbage will be collected on the same day.

解题思路

模拟

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int n;
  std::cin >> n;
  std::vector<pii > a(n);
  for(int i = 0; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    a[i] = {u, v};
  }

  int q;
  std::cin >> q;
  while (q--) {
    int t, d;
    std::cin >> t >> d;
    t--;
    auto [x, y] = a[t];
    int w = d / x * x + y;
    if (w < d) w += x;
    std::cout << w << endl;
  }
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

C.Repeating

Repeating

题目描述

You are given a sequence of $N$ positive numbers, $A = (A_1, A_2, \dots, A_N)$. Find the sequence $B = (B_1, B_2, \dots, B_N)$ of length $N$ defined as follows.

For $i = 1, 2, \dots, N$, define $B_i$ as follows:
- Let $B_i$ be the most recent position before $i$ where an element equal to $A_i$ appeared. If such a position does not exist, let $B_i = -1$.
  More precisely, if there exists a positive integer $j$ such that $A_i = A_j$ and $j < i$, let $B_i$ be the largest such $j$. If no such $j$ exists, let $B_i = -1$.

给你一个由 $N$ 个正数 $A = (A_1, A_2, \dots, A_N)$ 组成的数列。求长度为 $N$ 的序列 $B = (B_1, B_2, \dots, B_N)$ 的定义如下。

对于 $i = 1, 2, \dots, N$ ，定义 $B_i$ 如下：
- 设 $B_i$ 是在 $i$ 之前出现过与 $A_i$ 相同元素的最近位置。如果不存在这样的位置，则设为 $B_i = -1$ 。
  更确切地说，如果存在一个正整数 $j$ ，使得 $A_i = A_j$ 和 $j < i$ ，那么就让 $B_i$ 成为最大的 $j$ 。如果不存在这样的 $j$ , 则设 $B_i = -1$ .

解题思路

标记之前出现过的数的位置

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int n;
  std::cin >> n;
  std::vector<int> a(n + 2), b(n + 2);
  std::map<int, int> mp;
  for(int i = 1; i <= n; i++) std::cin >> a[i];
  b[1] = -1;
  mp[a[1]] = 1;
  for(int i = 2; i <= n; i++) {
    if (mp.find(a[i]) != mp.end()) {
      b[i] = mp[a[i]];
    }else {
      b[i] = -1;
    }
    mp[a[i]] = i;
  }

  for(int i = 1; i <= n; i++) std::cout << b[i] << " \n"[i == n];
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

D.Count Simple Paths

Count Simple Paths

题目描述

There is a grid of $H \times W$ cells. Let $(i, j)$ denote the cell at the $i$-th row from the top and the $j$-th column from the left.
Cell $(i, j)$ is empty if $S_{i,j}$ is ., and blocked if it is #.
Count the number of ways to start from an empty cell and make $K$ moves to adjacent cells (up, down, left, or right), without passing through blocked squares and not visiting the same cell more than once.
Specifically, count the number of sequences of length $K+1$, $((i_0, j_0), (i_1, j_1), \dots, (i_K, j_K))$, satisfying the following.

$1 \leq i_k \leq H$, $1 \leq j_k \leq W$, and $S_{i_k, j_k}$ is ., for each $0 \leq k \leq K$.
$|i_{k+1} - i_k| + |j_{k+1} - j_k| = 1$ for each $0 \leq k \leq K-1$.
$(i_k, j_k) \neq (i_l, j_l)$ for each $0 \leq k < l \leq K$.

有一个由 $H \times W$ 个单元格组成的网格。让 $(i, j)$ 表示从上往下第 $i$ 行，从左往上第 $j$ 列的单元格。
如果 $S_{i,j}$ 是 .，则单元格 $(i, j)$ 为空；如果是 # ，则单元格 $(i, j)$ 阻塞。
计算从一个空单元格开始，向相邻单元格（向上、向下、向左或向右）进行 $K$ 移动，而不经过被阻塞的方格，并且不多次访问同一单元格的方法的数目。
具体地说，计算满足以下条件的长度为 $K+1$ , $((i_0, j_0), (i_1, j_1), \dots, (i_K, j_K))$ 的序列的个数。

$1 \leq i_k \leq H$ 、 $1 \leq j_k \leq W$ 和 $S_{i_k, j_k}$ 为 .，每个 $0 \leq k \leq K$ 为 .。
$|i_{k+1} - i_k| + |j_{k+1} - j_k| = 1$ 为每个 $0 \leq k \leq K-1$ 。
每个 $0 \leq k < l \leq K$ 的 $(i_k, j_k) \neq (i_l, j_l)$ 。

解题思路

dfs暴搜

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void solve() {
  int n, m, k;
  std::cin >> n >> m >> k;
  std::vector<std::string> s(n);
  for(int i = 0; i < n; i++) std::cin >> s[i];

  auto check = [&](int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
  };

  int res = 0;

  std::vector vis(n, std::vector<bool>(m, false));
  std::function<void(int, int, int)> dfs = ([&](int x, int y, int val) {
    vis[x][y] = true;
    if (val == k) {
      res++;
      return;
    }
    for(int i = 0; i < 4; i++) {
      int u = x + dx[i], v = y + dy[i];
      if (check(u, v) && !vis[u][v] && s[u][v] == '.') {
        dfs(u, v, val + 1);
        vis[u][v] = false;
      }
    }
  });

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      if (s[i][j] == '.')
        dfs(i, j, 0), vis[i][j] = false;
    }
  }
  std::cout << res << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}