Codeforces Round 971 (Div. 4)

Lazy_boy_2024-09-042025-03-31

A. Minimize!

题目描述

You are given two integers a and b (a≤b). Over all possible integer values of c (a≤c≤b), find the minimum value of (c−a)+(b−c).

给定数字 $a$ , $b$ ,一个数 $c$ 的取值范围为 $[a,b]$ 求 $(c-a)+(b-c)$ 的最小值

解题思路

我们对等式化简 $(c-a)+(b-c) \to b-a$ 由此可见,等式的结果与 $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;
  std::cin >> a >> b;
  std::cout << b - a << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int Lazy_boy_ = 1;
  std::cin >> Lazy_boy_;
  while (Lazy_boy_--) solve();
  return 0;
}

B.osu!mania

osu!mania

题目描述

You are playing your favorite rhythm game, osu!mania. The layout of your beatmap consists of $n$ rows and 4 columns. Because notes at the bottom are closer, you will process the bottommost row first and the topmost row last. Each row will contain exactly one note, represented as a ‘#’.
For each note 1,2,…,n, in the order of processing, output the column in which the note appears.

给定 $n$ 行 4 列的字符串,从下向上处理字符串，输出该行字符串的 # 的位置

解题思路

中文题面说得很清楚,用STL中的find函数就可以了

参考代码

#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<std::string> s(n);
  for(int i = 0; i < n; i++) {
    std::cin >> s[i];
  }

  for(int i = n - 1; i >= 0; i--) {
    std::cout << s[i].find('#') + 1 << " \n"[i == 0];
  }
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int Lazy_boy_ = 1;
  std::cin >> Lazy_boy_;
  while (Lazy_boy_--) solve();
  return 0;
}

C.The Legend of Freya the Frog

The Legend of Freya the Frog

题目描述

Freya the Frog is traveling on the 2D coordinate plane. She is currently at point (0,0) and wants to go to point (x,y). In one move, she chooses an integer d such that 0≤d≤k and jumps d spots forward in the direction she is facing.

Initially, she is facing the positive x direction. After every move, she will alternate between facing the positive x direction and the positive y direction (i.e., she will face the positive y direction on her second move, the positive x direction on her third move, and so on).

What is the minimum amount of moves she must perform to land on point (x,y)?

在一个二维平面中,当前位置处于点 $(0,0)$ , 在给定一个数 $k$,每次移动的距离为 $d (0 \le d \le k) $,并且每次移动方向是在 $x$ 和 $y$ 轴正方向之间交替.
问需要就次移动到达点 $(x,y)$?

解题思路

分别考虑 $x$ 和 $y$ 两个方向，计算我们在每个方向上需要的跳转次数。我们在 $x$ 方向上需要的跳转数是 $\lceil \frac{x}{k} \rceil$ ，类似地，在 $y$ 方向上需要的跳转数是 $\lceil \frac{y}{k} \rceil$ 。现在，让我们试着将它们组合起来，求出跳转的总次数。让我们考虑以下几种情况：

$\lceil \frac{y}{k} \rceil \geq \lceil \frac{x}{k} \rceil$ .在这种情况下，需要在 $y$ 方向上进行 $\lceil \frac{y}{k} \rceil - \lceil \frac{x}{k} \rceil$ 次额外跳跃。在弗莱娅执行这些额外跳跃时，她会选择 $x$ 方向的 $d = 0$ 。总共需要 $2 \cdot \lceil \frac{y}{k} \rceil$ 次跳跃。

$\lceil \frac{x}{k} \rceil < \lceil \frac{y}{k} \rceil$ .我们可以使用与前一种情况相同的推理方法，但是有一个问题。由于弗莱娅一开始是朝向 $x$ 方向的，所以在最后一跳时，她不需要朝向 $y$ 方向跳。总共需要 $2 \cdot \lceil \frac{x}{k} \rceil - 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 x, y, k;
  std::cin >> x >> y >> k;

  x = (x + k - 1) / k;
  y = (y + k - 1) / k;

  std::cout << std::max(2 * x - 1, 2 * y) << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int Lazy_boy_ = 1;
  std::cin >> Lazy_boy_;
  while (Lazy_boy_--) solve();
  return 0;
}

D.Satyam and Counting

Satyam and Counting

题目描述

Satyam is given $n$ distinct points on the 2D coordinate plane. It is guaranteed that $0 \leq y_i \leq 1$ for all given points $(x_i, y_i)$. How many different nondegenerate right triangles$^{\text{∗}}$ can be formed from choosing three different points as its vertices?
Two triangles $a$ and $b$ are different if there is a point $v$ such that $v$ is a vertex of $a$ but not a vertex of $b$.
$^{\text{∗}}$A nondegenerate right triangle has positive area and an interior $90^{\circ}$ angle.

给出 $n$ 个点的坐标, 并且点的位置至多两行,数据范围:$(0 \le x_{i} \le n, 0 \le y_{i} \le 1)$,问这些点能组成多少个直角三角形?

解题思路

对于点 $(x,y)$形成直角三角形分为以下情况

以点 $(x,1-y)$ 为三角形的直角顶点,那么这个情况的三角形的个数为点 ($(x, 1-y)$ 的个数 -1)

以点 $(x,y)$ 为三角形的直角顶点,我们就需要判断点$(x-1,1-y)$ 和点 $(x+1,1-y)$ 是否存在,若存在则这样的三角形的个数为 $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> x(n, 0ll), y(n, 0ll), cnt(2, 0ll);
  std::vector vis(n + 1, std::array<int, 2>{0, 0});
  for(int i = 0; i < n; i++) {
    std::cin >> x[i] >> y[i];
    cnt[y[i]]++;
    vis[x[i]][y[i]] = 1;
  }

  int res = 0;
  for(int i = 0; i < n; i++) {
    if (vis[x[i]][1 - y[i]]) {
      res += cnt[1 - y[i]] - 1;
    }
    if (x[i] > 0 && x[i] < n && vis[x[i] - 1][1 - y[i]] && vis[x[i] + 1][1 - y[i]]) {
      res++;
    }
  }

  std::cout << res << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int Lazy_boy_ = 1;
  std::cin >> Lazy_boy_;
  while (Lazy_boy_--) solve();
  return 0;
}

A. Minimize!

题目描述

解题思路

参考代码

B.osu!mania

题目描述

解题思路

参考代码

C.The Legend of Freya the Frog

题目描述

解题思路

D.Satyam and Counting

题目描述

解题思路

参考代码

E.Klee’s SUPER DUPER LARGE Array!!!

题目描述

解题思路

参考代码

Lazy_boy_