Atcoder beginner contest 377

atcoder, 题解

A.Rearranging ABC

Rearranging ABC

题目描述

给定字符串,判断是否可以组成

解题思路

排个序就行了

参考代码

#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::sort(s.begin(), s.end());
	std::cout << (s == "ABC" ? "Yes" : "No") << endl;
}


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

B.Avoid Rook Attack

Avoid Rook Attack

题目描述

给出棋盘，其中放有的位置为 #, 在放有棋子的上下左右四个方向不能放棋子，问有多少个位置可以放棋子.

解题思路

模拟下即可

参考代码

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


	std::vector a(8, std::vector<int>(8, 1));
	for(int i = 0; i < 8; i++) {
		for(int j = 0; j < 8; j++) {
			if (s[i][j] == '#') {
				for(int l = 0; l < 8; l++) {
					a[i][l] = 0;
				}


				for(int l = 0; l < 8; l++) {
					a[l][j] = 0;
				}
			}
		}
	}
	int res = 0;
	for(auto i : a) {
		for(auto j : i) {
			res += j;
		}
	}


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


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

C.Avoid Knight Attack

Avoid Knight Attack

题目描述


给定 的棋盘和 个棋子位置,其中棋子能走的位置上图所示,问多少个位置可以放棋子,并且不被吃掉

解题思路

模拟，需要注意边界处理

参考代码

#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;


	int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2},
			dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};


	auto check = [&](int x, int y) {
		return 0 < x && x <= n && 0 < y && y <= n;
	};
	std::set<pii > se;
	for(int i = 0; i < m; i++) {
		int x, y;
		std::cin >> x >> y;
		se.insert({x, y});
		for(int j = 0; j < 8; j++) {
			int u = x + dx[j], v = y + dy[j];
			if (check(u, v)) se.insert({u, v});
		}
	}


	std::cout << n * n - se.size() << endl;


}


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

D.Many Segments 2

Many Segments 2

题目描述

给你两个长度分别为 、 和 的正整数序列，以及一个整数 。
求满足以下两个条件的整数对 的个数：

  • 对于每一个 ，区间 并不完全包含区间 。

解题思路

考虑 的同时，维护一个左边界，就是当前位置能最多往前多少是刚好不完全覆盖的，最后这个左边界需要取个 max ，因为如果前面的左边界更右，那后面的左边界也要和前面一样。

参考代码

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


	for(int i = 1; i <= m; i++) {
		a[i] = std::max(a[i], a[i - 1]);
	}


	int res = 0;
	for(int i = 1; i <= m; i++) {
		res += i - a[i] + 1;
	}


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


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

E.Permute K times 2

Permute K times 2

题目描述

给定长度为 的数组 ,将 替换为 操作 次,输出 次操作后的数组.

解题思路

在替换时，某个数多替换几轮就可能回到替换前的位置，那么我们就只需要找出环的大小即可，随后再取模即可

参考代码

#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, k;
	std::cin >> n >> k;
	std::vector<int> P(n);


	for(int i = 0; i < n; i++) {
		std::cin >> P[i], P[i]--;
	}


	auto qpow = [&](int a, int b, int p) {
		int res = 1;
		while (b) {
			if (b & 1) res = res * a % p;
			a = a * a % p;
			b >>= 1;
		}
		return res;
	};


	std::vector<bool> vis(n, false);
	for(int i = 0; i < n; i++) {
		if (vis[i]) continue;
		int j = i;
		std::vector<int> t;
		while (!vis[j]) {
			vis[j] = true, t.push_back(j);
			j = P[j];
		}


		int w = qpow(2, k, t.size());
		for(int x = 0; x < t.size(); x++) {
			P[t[x]] = t[(x + w) % t.size()];
		}
	}


	for(int i = 0; i < n; i++) std::cout << P[i] + 1 << " \n"[i == n - 1];
}


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