Codeforces Round 971 (Div.4)

codeforces, 题解

A. Minimize!

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).

给定数字 , ,一个数 的取值范围为 求 的最小值

{% endtabs %}

解题思路

我们对等式化简 由此可见,等式的结果与 的值无关

参考代码

#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

题目描述

{% tabs B %}

You are playing your favorite rhythm game, osu!mania. The layout of your beatmap consists of 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.

给定 行 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;
}

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

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

{%endtabs %}

解题思路

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

  • .在这种情况下，需要在 方向上进行 次额外跳跃。在弗莱娅执行这些额外跳跃时，她会选择 方向的 。总共需要 次跳跃。
  • .我们可以使用与前一种情况相同的推理方法，但是有一个问题。由于弗莱娅一开始是朝向 方向的，所以在最后一跳时，她不需要朝向 方向跳。总共需要 次跳跃。

参考代码

#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

题目描述

{% tabs D%}

Satyam is given distinct points on the 2D coordinate plane. It is guaranteed that for all given points . How many different nondegenerate right triangles can be formed from choosing three different points as its vertices?
Two triangles and are different if there is a point such that is a vertex of but not a vertex of .
A nondegenerate right triangle has positive area and an interior angle.

给出 个点的坐标, 并且点的位置至多两行,数据范围:,问这些点能组成多少个直角三角形?

{% endtabs %}

解题思路

对于点 形成直角三角形分为以下情况

  • 以点 为三角形的直角顶点,那么这个情况的三角形的个数为点 ( 的个数 -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;
}
Built with MDFriday ❤️