Atcoder beginner contest 375 • santisify Site

A.Seats#

题目描述#

给定字符串 $s$ 其中字符串只含有 # 和 . ,# 表示当前位置有人, .表示当前位置无人. 问:有多少个位置满足左右有人，当前位置无人的.

参考代码#

#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::string s;
	std::cin >> s;
	int ct = 0;
	for(int i = 1; i < n - 1; i++) {
		if (s[i] == '.' && s[i] != s[i + 1] && s[i + 1] == s[i - 1])
			ct++;
	}
	std::cout << ct << endl;
}

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

cpp

B.Traveling Takahashi Problem#

Traveling Takahashi Problem ↗

题目描述#

给定 $n$ 个点，从点 $(0,0)$ 出发依次经过这些点,然后回到原点的代价. 从点 $(a,b)$ 移动到点 $(c,d)$ 的代价是 $\sqrt{(a-c)^{2} + (b-d)^{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() {
	double s = 0;
	int n;
	std::cin >> n;
	int x = 0, y = 0;
	for(int i = 0; i < n; i++) {
		int u, v;
		std::cin >> u >> v;
		s += std::hypot(u - x, y - v);
		x = u, y = v;
	}
	s += std::hypot(x, y);
	std::cout << fix(16) << s << endl;
}

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

cpp

C.Spiral Rotation#

Spiral Rotation ↗

题目描述#

题意太复杂，直接说重点，在 $N * N$ 的矩阵中,每个单元格都涂成黑色或白色。如果 $A_{i, j} =$ 则 $(i, j)$ 单元格为黑色；如果是 $A_{i, j} =$ .，则为黑色。.”，则为白色。

依次对 $i = 1, 2, \ldots, \frac{N}{2}$ 进行以下操作:

对于 $i$ 和 $N + 1 - i$ 之间的所有整数对 $x, y$ ，将单元格 $(y, N + 1 - x)$ 的颜色替换为单元格 $(x, y)$ 的颜色。同时对所有这些单元格对 $x, y$ 进行替换。最后打印这个矩阵。

解题思路#

稍加推理就可以发现对于每次操作 $i$ 都是在对以 $(i,i)$ 为左上角，大小为 $(N-i+1)*(N-i+1)$ 的子矩阵进行顺时针旋转 $90^{\circ}$

参考代码#

TLE code

#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 a = 0; a < n / 2; a++) {
		auto t = s;
		for(int i = a; i < n - a; i++) {
			for(int j = a; j < n - a; j++) {
				t[i][j] = s[n - j - 1][i];
			}
		}
		s = t;
	}

	for(auto i : s) {
		std::cout << i << endl;
	}
}

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

cpp

AC code

#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> A(N), B(N, std::string(N, ' '));
	for(int i = 0; i < N; i++)std::cin >> A[i];
	for(int d = 0; d < N / 2; d++) {
		for(int t = 0; t < (d + 1) % 4; t++) {
			for(int x = d; x < N - d; x++) {
				B[x][d] = A[x][d];
				B[x][N - d - 1] = A[x][N - d - 1];
				B[d][x] = A[d][x];
				B[N - d - 1][x] = A[N - d - 1][x];
			}
			for(int x = d; x < N - d; x++) {
				A[d][N - x - 1] = B[x][d];
				A[N - d - 1][N - x - 1] = B[x][N - d - 1];
				A[x][N - d - 1] = B[d][x];
				A[x][d] = B[N - d - 1][x];
			}
		}
	}
	for(auto i : A) {
		std::cout << i << endl;
	}
}

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

cpp

D.ABA#

ABA ↗

题目描述#

给你一个由大写英文字母组成的字符串 $S$ 。求满足以下两个条件的整数三元组 $(i, j, k)$ 的个数：

$1 \leq i < j < k \leq |S|$
将 $S_i$ 、 $S_j$ 和 $S_k$ 按此顺序连接而成的长度为 $3$ 的字符串是一个回文字符串。

这里， $|S|$ 表示 $S$ 的长度， $S_x$ 表示 $S$ 的 $x$ -th字符。

解题思路#

这个其实就是前缀和维护当前位置前的每个字母个数和当前位置后的每个字母个数

参考代码#

#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::vector ct(26, std::vector<int>(s.size() + 1, 0ll));
	for(int i = 0; i < s.size(); i++) {
		ct[s[i] - 'A'][i]++;
	}

	for(int i = 0; i < 26; i++) {
		for(int j = 1; j < s.size(); j++) {
			ct[i][j] += ct[i][j - 1];
		}
	}
	int ans = 0;
	for(int i = 1; i < s.size() - 1; i++) {
		for(int j = 0; j < 26; j++) {
			ans += ct[j][i - 1] * (ct[j][s.size() - 1] - ct[j][i]);
		}
	}

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

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

cpp