Atcoder beginner contest 374

atcoder, 题解

A.Takahashi san 2

Takahashi san 2

题目描述

判断字符串末尾是否有 san 这个后缀

参考代码

#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;
	std::cin >> s;
	std::string t = s.substr(s.size() - 3);
	std::cout << (t == "san" ? "Yes" : "No") << endl;
}


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

B.Unvarnished Report

Unvarnished Report

题目描述

给定字符串 和 ,若字符串 和字符串 完全相等,则输出 否则输出 和 第一个不相同的位置.

解题思路

首先判断两个字符串是否相同,

若相同直接输出

否则用 遍历一次字符串

参考代码

#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 >> t;
	if (s == t) {
		std::cout << 0 << endl;
		return;
	}
	for(int i = 0; i < std::max(s.size(), t.size()); i++) {
		if (s[i] != t[i]) {
			std::cout << i + 1 << endl;
			break;
		}
	}
}


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

C.Separated Lunch

Separated Lunch

题目描述

给出一个数 , 和一个长度为 的数组 , 将这个数组划分为 , 两个部分,使得这两个部分的和 和 中的最大值最小

数据范围:
,

解题思路

瞄一眼中文题面, 有点像 背包, 但是你可以发现数据范围好像不能用背包，有没有其他方法呢?

好像 的范围比较小，我们可以使用 来搜索每一种情况，最多为 ,那么怎么判断哪种情况最优?只需要满足 和 的差值最小，答案即为差值最小时的最大值。

参考代码

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




	std::vector<int> f(n, 0);
	int mi = inf, ans = inf;
	std::function<void(int)> dfs = ([&](int u) {
		if (u >= n) {
			int s = 0;
			for(int i = 0; i < n; i++) {
				if (f[i]) {
					s += a[i];
				}
			}
			if (mi >= abs(w - s - s)) {
				mi = abs(w - s - s);
				ans = std::min(ans, std::max(s, w - s));
			}
			return;
		}
		f[u] = 1;
		dfs(u + 1);
		f[u] = 0;
		dfs(u + 1);
	});


	dfs(0);


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


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

D.Laser Marking

Laser Marking

题目描述

在一个平面上给出 条线段的起始点和终点 现在要使用激光打印机打印这些线段,在打印线段时的移动速度为每秒 个单位长度, 不打印的时候的移动速度为每秒 个单位长度, 问打印这些线段的最短时间为多少？

解题思路

由于一个线段可以从两个端点中的任意一个开始打印，看来这个题又和上面一个题一样使用 ,循环初始到达线段,先移动到其中一个端点,再移动到另一个端点，答案记录下来，再, 函数中的参数 , , , 表示在此之前是从点 移动到了 .其实 只传当前位置就行了,只是个人方便识别.

参考代码

hypot()函数详解：
hypot(x, y) 返回的是浮点型数据类型,值为 即将作为直角三角形的两条直角边的斜边。
hypot(x,y,z) 返回类型同上值为 

#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, s, t;
	std::cin >> n >> s >> t;
	std::vector<int> A(n), B(n), C(n), D(n);
	for(int i = 0; i < n; i++)
		std::cin >> A[i] >> B[i] >> C[i] >> D[i];


	std::vector<bool> vis(n, false);
	double ans = INFINITY, w = 0;
	auto check = [&]() -> bool {
		for(int i = 0; i < n; i++) if (!vis[i]) return false;
		return true;
	};


	std::function<void(int, int, int, int)> dfs = ([&](int x, int y, int u, int v) -> void {
		if (check()) {
			ans = std::min(ans, w);
//			std::cout << ans << endl;
			return;
		}


		for(int i = 0; i < n; i++) {
			if (!vis[i]) {
				vis[i] = true;
				auto t1 = std::hypot(u - A[i], v - B[i]) / s;
				auto t2 = std::hypot(u - C[i], v - D[i]) / s;
				auto tt = std::hypot(A[i] - C[i], B[i] - D[i]) / t;
				w += tt, w += t1;
				dfs(A[i], B[i], C[i], D[i]);
				w -= t1, w += t2;
				dfs(C[i], D[i], A[i], B[i]);
				w -= t2, w -= tt;
				vis[i] = false;
			}
		}
	});


	for(int i = 0; i < n; i++) {
		vis[i] = true;
		auto t1 = std::hypot(A[i], B[i]) / s;
		auto t2 = std::hypot(C[i], D[i]) / s;
		auto tt = std::hypot(A[i] - C[i], B[i] - D[i]) / t;
		w = t1 + tt;
		dfs(A[i], B[i], C[i], D[i]);
		w = t2 + tt;
		dfs(C[i], D[i], A[i], B[i]);
		vis[i] = false;
	}
	std::cout << fix(16) << ans << endl;
}


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