[补题记录] Atcoder Beginner Contest 308（C~E）

URL：https://atcoder.jp/contests/abc308

目录

C

Problem/题意

Thought/思路

Code/代码

D

Problem/题意

Thought/思路

Code/代码

E

Problem/题意

Thought/思路

Code/代码

---

C

Problem/题意

给出n个（a，b）数对，定义成功率为 a / (a + b)，按照成功率降序排序，输出数对编号。

Thought/思路

坑：当成功率相同时，要求编号小的在前。

Code/代码

#include "bits/stdc++.h"
 
#define int long long
 
int n;
struct node {
	int id;
	int a, b;
	bool operator < (const node &t) const {
		if (a * (t.a + t.b) == t.a * (a + b)) return id < t.id; // 按原顺序比较
		else return a * (t.a + t.b) > t.a * (a + b);
	}
};
 
signed main() {
	std::cin >> n;
	std::vector  rate(n + 1);
 
	for (int i = 1; i <= n; ++ i) {
		std::cin >> rate[i].a >> rate[i].b;
		rate[i].id = i;
	}
 
	std::sort(rate.begin() + 1, rate.end());
 
	for (int i = 1; i <= n; ++ i) {
		std::cout << rate[i].id << " ";
	}
}

D

Problem/题意

给一个n * m的矩阵，由小写字母组成，问是否能从（1，1）走到（n，m）。行走规则是：按照“s、n、u、k、e”循环的顺序来走，也就是一开始从s出发，下一步只能走到n；当走到e，下一步只能走到s。

Thought/思路

简单bfs。

能走到的地方标记为1，其实就是vis。

Code/代码

#include "bits/stdc++.h"
 
int n, m, vis[507][507];
char mp[507][507];
 
const char path[6] = {'s', 'n', 'u', 'k', 'e'};
const int dx[5] = {0, 1, 0, -1, 0};
 
bool check(int x, int y, char target) {
	if (x < 1 or x > n or y < 1 or y > m or vis[x][y] or target != mp[x][y])
		return false;
	else
		return true;
}
 
bool bfs() {
	std::queue int, int>> q;
	q.push({1, 1});
	if (mp[1][1] != 's') return false;
 
	while (!q.empty()) {
		auto top = q.front(); q.pop();
		int x = top.first, y = top.second;
 
		if (vis[x][y]) continue;
		else vis[x][y] = 1;
 
		char next = '#';
		for (int i = 0; i < 5; ++ i) {
			if (path[i] == mp[x][y]) {
				next = path[i + 1 == 5 ? 0 : i + 1];
				break;
			}
		}
 
		//std::cout << "next = " << next << "\n";
 
		for (int i = 0; i <= 3; ++ i) {
			int nx = x + dx[i], ny = y + dx[i + 1];
			if (check(nx, ny, next)) {
				q.push({nx, ny});
			}
		}
	}
 
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			// std::cout << vis[i][j] << " \n"[j == m];
		}
	}
 
	if (vis[n][m] == 1) return true;
	else return false;
}
 
signed main(){
	std::cin >> n >> m;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			std::cin >> mp[i][j];
		}
	}
 
	if(bfs()) {
		std::cout << "Yes";
	} else {
		std::cout << "No";
	}
 
 
}

E

Problem/题意

给一个数组 a，由 0、1、2 组成；给一个字符串 s，由 M、E、X 组成。

在 s 中选择 s[i] s[j] s[k] = M E X 的子序列串，求 mex(ai, aj, ak) 的和。

Thought/思路

因为 MEX 的顺序固定，因此考虑以 E 作为出发点，假设数组 a 中仅有 1，那么每个 E 的位置能贡献的答案就是 ans += M_pre * X_rep * Mex(1, 1, 1)，即 前缀M的数量 × 后缀X的数量 × 1。

但是该题数组 a 中包含 0、1、2，那么只需要对 M 和 X 都多考虑 0 和 2 的情况即可，也就是多维护两个前缀 {M, 0}、{M, 2} 和两个后缀 {X, 0}、{X, 2} 。

Code/代码

#include "bits/stdc++.h"
 
#define int long long
 
int n, a[200005];
std::string s;
std::mapint, int>, int> pre[200005];
// pre[2][{'M', 0}]：1~2之间，M 对应 a 为 0 的情况有多少种
std::mapint, int>, int> rep[200005];
 
int Mex(int a, int b, int c) {
	std::bitset <4> st;
	st[a] = st[b] = st[c] = 1;
	for (int i = 0; i <= 3; ++ i) {
		if (st[i] == 0) 
			return i;
	}
	return 0;
}
 
signed main() {
	std::cin >> n;
	for (int i = 1; i <= n; ++ i) std::cin >> a[i];
	std::cin >> s;
	s = "#" + s;
	
	for (int i = 1; i <= n; ++ i) {
		for (auto &c : {'M', 'E', 'X'}) 
			for (int j = 0; j <= 2; ++ j) 
				pre[i][{c, j}] = pre[i - 1][{c, j}] + (c == s[i] and j == a[i]);
	}
 
	for (int i = n; i >= 1; -- i) {
		for (auto &c : {'M', 'E', 'X'}) 
			for (int j = 0; j <= 2; ++ j) 
				rep[i][{c, j}] = rep[i + 1][{c, j}] + (c == s[i] and j == a[i]);
	}
 
	int ans = 0;
	for (int i = 2; i <= n - 1; ++ i) {
		if (s[i] == 'E') {
			for (int j = 0; j <= 2; ++ j) { // M
				for (int k = 0; k <= 2; ++ k) { // X
					int mex = Mex(j, a[i], k);
					ans += mex * (pre[i - 1][{'M', j}] * rep[i + 1][{'X', k}]);
				}
			}
		}
	}
 
	std::cout << ans;
 
}