Atcoder beginner contest 367

atcoder, 题解

A Shout Everyday

题目

给定一个整数时间 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

题目

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

  • 小数部分不能有尾数 "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

题目

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

  • 第 个元素介于 和 之间。
  • 所有元素之和是 的倍数。

解题思路

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

参考代码

#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

题目

解题思路

参考代码

#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;
}
Built with MDFriday ❤️