Codeforces Round 971 (Div.4) • santisify Site

A. Minimize!#

题目描述#

{% tabs A %}

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)$ 的最小值

{% endtabs %}

解题思路#

我们对等式化简 $(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;
}

cpp

B.osu!mania#

osu!mania ↗

题目描述#

{% tabs B %}

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 列的字符串,从下向上处理字符串，输出该行字符串的 # 的位置

{% endtabs %}

解题思路#

中文题面说得很清楚,用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;
}

cpp

C.The Legend of Freya the Frog#

The Legend of Freya the Frog ↗

题目描述#

{% tabs C %}

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)$ ?

{%endtabs %}

解题思路#

分别考虑 $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;
}

cpp

D.Satyam and Counting#

Satyam and Counting ↗

题目描述#

{% tabs D%}

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)$ ,问这些点能组成多少个直角三角形?

{% endtabs %}

解题思路#

对于点 $(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;
}

cpp