AtCoder Beginner Contest 050

pangyou3s / 2024-08-24 / 原文

基本上独立做出来了。

A - Addition and Subtraction Easy

模拟。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int A, B;
	char C;
	cin >> A >> C >> B;
	if (C == '+') cout << A + B;
	else cout << A - B;
	return 0;
}

B - Contest with Drinks Easy

模拟。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int N, M;
	cin >> N;
	vector<int> T(N), P(110), X(110);
	for (int i = 0; i < N; i++) cin >> T[i];
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> P[i] >> X[i];
	}
	for (int i = 0; i < M; i++) {
		int t = T[P[i] - 1];
		T[P[i] - 1] = X[i];
		i64 ans = 0;
		for (int i = 0; i < N; i++) ans += T[i];
		cout << ans << "\n";
		T[P[i] - 1] = t;
	}
	return 0;
}

C - Lining Up

观察发现，当 $N$ 为奇数时，$0$ 就是中间位，且必定只有 $1$ 个，否则错误。且其他数字一定具有对称性，即相差绝对值为 $k$ 的人可以站在中间位置的两边。用哈希表记录，但凡发现哈希值不为 $2$ 的，一定错误。

观察得到结论，假若情形成立，答案为 $\rm 2^{ans}$，其中 $\rm ans$ 为哈希值为 $2$（即成对）的个数。这里可以使用带模数的快速幂来实现。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const int mod = 1e9 + 7;
int p[100005];

i64 qmi(i64 m, i64 k, i64 p) { //快速幂模板，熟练记忆。
	i64 res = 1;
	while (k) {
		if (k & 1) res = res * m % p;
		m = m * m % p;
		k >>= 1;
	}
	return res % p;
}


int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int N;
	cin >> N;
	vector<int> A(N);
	
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		p[A[i]]++;
	}
	
	bool flag = true;
	if (N % 2 == 1) {
		if (p[0] != 1) {
			flag = false;
		}
		for (int i = 2; i <= N - 1; i += 2) {
			if (p[i] != 2) {
				flag = false;
				break;
			}
		}
	} else {
		for (int i = 1; i <= N - 1; i += 2) {
			if (p[i] != 2) {
				flag = false;
				break;
			}
		}
	}
	
	int ans = 0;
	for (int i = 1; i < N; i++) {
		if (p[i] == 2) ans++;
	}
	if (flag) cout << qmi(2, ans, mod);
	else cout << 0;
	return 0;
}