AtCoder Beginner Contest 367

Lazy_boy_2024-08-252025-03-31

A Shout Everyday

题目

In the Kingdom of AtCoder, residents are required to shout their love for takoyaki at
A o’clock every day.
Takahashi, who lives in the Kingdom of AtCoder, goes to bed at
B o’clock and wakes up at C o’clock every day (in the 24-hour clock). He can shout his love for takoyaki when he is awake, but cannot when he is asleep. Determine whether he can shout his love for takoyaki every day. Here, a day has 24 hours, and his sleeping time is less than 24 hours.

给定一个整数时间 A,一个人在B时间睡觉,C时间起床(24小时制),问A是否不在睡觉时间

解题思路

我们可以先判断B，C这个时间段是否是跨越两天的，若是跨越两天， A < B && A > C 才会不在这个时间段
若未跨越两天 A < B || A > C 满足不在 B，C 时间段

参考代码

#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 a, b, c;
  std::cin >> a >> b >> c;
  if (b > c) {
    if (a >= b || a <= c) {
      std::cout << "No" << endl;
    } else {
      std::cout << "Yes" << endl;
    }
  } else {
    if (a >= b && a <= c) {
      std::cout << "No" << endl;
    } else {
      std::cout << "Yes" << endl;
    }
  }
}

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

B Cut .0

题目

A real number $X$ is given to the third decimal place.
Print the real number $X$ under the following conditions.

The decimal part must not have trailing 0s.
There must not be an unnecessary trailing decimal point.

一个实数 $X$ 已精确到小数点后第三位。
请在下列条件下打印实数 $X$ 。

小数部分不能有尾数 “0”。
小数点后不能有多余的尾数。

参考代码

#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::string s, t("");
  std::cin >> s;
  int cnt = 0, f = 0;
  for(auto i : s) {
    if (cnt == 3) {
      break;
    }
    cnt += f;
    if (i == '.') f = 1;
    t = t + i;
  }

  while (t.back() == '0') t.pop_back();
  if (t.back() == '.') t.pop_back();
  std::cout << t << endl;
}

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

C Enumerate Sequences

题目

Print all integer sequences of length $N$ that satisfy the following conditions, in ascending lexicographical order.

The $i$-th element is between $1$ and $R_i$, inclusive.
The sum of all elements is a multiple of $K$.

按升序排列打印所有满足以下条件的长度为 $N$ 的整数序列。

第 $i$ 个元素介于 $1$ 和 $R_i$ 之间。
所有元素之和是 $K$ 的倍数。

解题思路

由于每个数都介于$1$和 $R_i$之间，我们可以遍历每个位置的每个数，显然$DFS$可以做到
那么回溯条件是什么呢？
显然是走到第$N$个数，那么答案就只需要验证下这$N$个数的和是否为$K$的倍数

参考代码

#include<bits/stdc++.h>

using VI = std::vector<int>;
#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, k;
  std::cin >> n >> k;
  VI a(n);
  std::vector<VI> ans;
  for(int i = 0; i < n; i++) {
    std::cin >> a[i];
  }

  VI w(n, 1ll);
  std::function<void (int)> dfs = ([&] (int u) {
    if (u == n) {
      int res = 0;
      for(auto i : w) res += i;
      if (res % k == 0) ans.push_back(w);
      return;
    }
    for(int i = 1; i <= a[u]; i++) {
      w[u] = i;
      dfs(u + 1);
    }
    return;
  });

  dfs(0);

  std::sort(ans.begin(), ans.end(), [&] (VI aa, VI bb) { return aa < bb; });

  for(auto q : ans) {
    for(auto i : q) {
      std::cout << i << ' ';
    }
    std::cout << endl;
  }
}

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

D Pedometer

题目

Problem Statement

There are $N$ rest areas around a lake.
The rest areas are numbered $1$, $2$, …, $N$ in clockwise order.
It takes $A_i$ steps to walk clockwise from rest area $i$ to rest area $i+1$ (where rest area $N+1$ refers to rest area $1$).
The minimum number of steps required to walk clockwise from rest area $s$ to rest area $t$ ($s \neq t$) is a multiple of $M$.
Find the number of possible pairs $(s,t)$.

解题思路

参考代码

#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, M;
  std::cin >> N >> M;

  std::vector<int> A(N);
  std::vector<int> pre(N + 1);
  for(int i = 0; i < N; i++) std::cin >> A[i], pre[i + 1] = pre[i] + A[i];

  std::map<int, int> cnt;
  int ans = 0;

  const int L = pre[N];

  for(int i = 0, j = 0; i < N; i++) {
    ans += cnt[(pre[i] - L % M + M) % M];
    ans += cnt[pre[i] % M]++;
  }

  std::cout << ans << endl;
}

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