AtCoder Beginner Contest 237题解

2023-10-11 12:21:28

AtCoder Beginner Contest 237

A - Not Overflow

题目描述：给你一个在long long范围的整数，判断其是否在int范围内。

思路：根据题意模拟即可

时间复杂度：\(O(1)\)

参考代码：

void solve() {
	long long n;
	cin >> n;
	if (n >= INT_MIN && n <= INT_MAX) cout << "Yes" << '\n';
	else cout << "No" << '\n';
	return;
}

B - Matrix Transposition

题目描述：给你一个\(n \times m\)的矩阵\(A\)，输出\(A^T\)。

思路：根据题意模拟即可。

时间复杂度：\(O(nm)\)

参考代码：

void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>>a(n + 1, vector<int>(m + 1, 0));
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) cin >> a[i][j];
	}
	for (int j = 1; j <= m; ++j) {
		for (int i = 1; i <= n; ++i) cout << a[i][j] << ' ';
		cout << '\n';
	}
	return;
}

C - kasaka

题目描述：给你一个字符串\(s\)，问是否可以通过在\(s\)的前面增加字符a，使得字符串变成回文串。

思路：在字符串\(s\)两边删除相同数量的字符a，然后将右边多余的字符a也删去，判断剩下的字符串是否是回文即可。

时间复杂度：\(O(n)\)

参考代码：

void solve() {
	string s;
	cin >> s;
	int n = s.size();
	string t = s;
	reverse(t.begin(), t.end());
	if (s == t) {
		cout << "Yes" << '\n';
		return;
	}
	int lr = 0, rs = n - 1;
	while (lr < rs && s[lr] == s[rs] && s[rs] == 'a') ++lr, --rs;
	while (lr < rs && s[rs] == 'a') --rs;
	t = s.substr(lr, rs - lr + 1);
	s = t;
	reverse(t.begin(), t.end());
	if (s == t) {
		cout << "Yes" << '\n';
		return;
	}
	cout << "No" << '\n';
	return;
}

D - LR insertion

题目描述：有一个集合\(S\)，初始时只有元素\(0\)，现在你需要依次放入\(1 \sim n\)，放入第\(i\)个数时会告诉你一个命令，表示将第\(i\)个数字放在第\(i - 1\)个数字的左边还是右边，让你输出最终序列。

思路：比较明显的链表操作，可以使用数组模拟链表即可。当然注意到第\(i\)个数字只与第\(i - 1\)个数字有关，且要么放在其左边要么放在其右边，抽象成树形结构就是二叉树，故该序列就等价于该二叉树的中序遍历。

时间复杂度：\(O(n)\)

数组模拟链表：

void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	s = ' ' + s;
	vector<vector<int>>res(n + 1, vector<int>(2, -1));
	for (int i = 1; i <= n; ++i) {
		if (s[i] == 'L') {
			int dx = res[i - 1][0];
			if (dx != -1) {
				res[dx][1] = i;
				res[i][0] = dx;
			}
			res[i][1] = i - 1;
			res[i - 1][0] = i;
		}
		else {
			int dx = res[i - 1][1];
			if (dx != -1) {
				res[dx][0] = i;
				res[i][1] = dx;
			}
			res[i][0] = i - 1;
			res[i - 1][1] = i;
		}
	}
	int head = 0;
	for (int i = 0; i <= n; ++i) {
		if (res[i][0] != -1) continue;
		head = i;
		break;
	}
	while (head != -1) {
		cout << head << ' ';
		head = res[head][1];
	}
	cout << '\n';
	return;
}

中序遍历：

void solve() {
	int n;
	cin >> n;
	vector<vector<int>>a(n + 2, vector<int>(2, 0));
	string s;
	cin >> s;
	for (int i = 1; i <= n; ++i) {
		if (s[i - 1] == 'L') a[i][0] = i + 1;
		else a[i][1] = i + 1;
	}
	auto dfs = [&](auto dfs, int u)->void {
		if (a[u][0] != 0) dfs(dfs, a[u][0]);
		cout << u - 1 << ' ';
		if (a[u][1] != 0) dfs(dfs, a[u][1]);
		return;
	};
	dfs(dfs, 1);
	cout << '\n';
	return;
}

题目描述：有\(n\)座山编号\(1 \sim n\)，第\(i\)座山有一个高度\(h_i\)。有\(m\)个索桥连接一些山，这些索桥是双向的。若从高度高的山到高度低的山，假设这两座山编号为\(x , y\)，则可获得价值\(h_x - h_y\)；若从高度低的山到高度高的山，则获得价值为\(2(h_x - h_y) (h_x < h_y)\)。你有初始价值\(0\)，然后从\(1\)号山出发，你可以在任意山结束，问你最终能获得的最大价值。

思路：我们可以假设正向边是正权，反向边是负权，我们可以使用BFS，然后保证每一座山至少访问一次，再在之后的广搜中使用更大的价值更新当前点。最终遍历所有点取其价值的最大值。

时间复杂度：\(O(n + m)\)

参考代码：

void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>>graph(n + 1);
	vector<int>H(n + 1, 0);
	for (int i = 1; i <= n; ++i) cin >> H[i];
	int u, v;
	vector<long long>dis(n + 1, 0);
	vector<bool>vis(n + 1, 0);
	for (int i = 1; i <= m; ++i) {
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	queue<int>q;
	q.push(1);
	vis[1] = true;
	while (!q.empty()) {
		u = q.front();
		q.pop();
		for (auto v : graph[u]) {
			long long dx = dis[u] + (H[u] >= H[v] ? H[u] - H[v] : 2ll * (H[u] - H[v]));
			if (vis[v] == false) dis[v] = dx, vis[v] = true, q.push(v);
			if (dis[v] < dx) {
				dis[v] = dx;
				q.push(v);
			}
		}
	}
	long long res = 0;
	for (int i = 1; i <= n; ++i) res = max(res, dis[i]);
	cout << res << '\n';
	return;
}

F - |LIS| = 3

题目描述：你需要构造一个LIS = 3的长度为\(n\)的数组\(a\)，且对于任意的\(a_i\)满足\(1 \leq a_i \leq m\)。问这样的\(a\)的方案数。对998244353取模。

数据范围：\(3 \leq n \leq 1000 , 3 \leq m \leq 10\)。

思路：比较明显的dp，定义状态\(f_{i , j ,k , r}\)表示对于前\(i\)个数字，LIS为子集(j , k , r)的方案数。转移方程为：

\[\begin{align} f_{i , j , k , r} & = \sum\limits_{x = 0}^{j}f_{i - 1, x , k , r} + \sum\limits_{x = j + 1}^{k}f_{i - 1 , j , x , r} + \sum\limits_{x = k + 1}^{r} f_{i-1 , j , k , x} \end{align} \]

初始条件\(f_{0 , m , m , m} = 1\)。

最终答案为：

\[\sum\limits_{i = 0}^{m - 1}\sum\limits_{j = 0}^{m - 1}\sum\limits_{k = 0}^{m - 1} f_{n , i , j , k} \]

时间复杂度：\(O(nm^4)\)

参考代码：

const int mod = 998244353;
void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<vector<vector<int>>>>f(n + 1, vector<vector<vector<int>>>(m + 1, vector<vector<int>>(m + 1, vector<int>(m + 1, 0))));
	f[0][m][m][m] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= m; ++j) {
			for (int k = 0; k <= m; ++k) {
				for (int r = 0; r <= m; ++r) {
					int dx = f[i][j][k][r];
					if (dx == 0) continue;
					for (int x = 0; x < m; ++x) {
						if (x <= j) f[i + 1][x][k][r] = (f[i + 1][x][k][r] + dx) % mod;
						else if (x <= k) f[i + 1][j][x][r] = (f[i + 1][j][x][r] + dx) % mod;
						else if (x <= r)f[i + 1][j][k][x] = (f[i + 1][j][k][x] + dx) % mod;
					}
				}
			}
		}
	}
	int res = 0;
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < m; ++j)
			for (int k = 0; k < m; ++k)
				res = (res + f[n][i][j][k]) % mod;
	cout << res << '\n';
	return;
}

G - Range Sort Query

题目描述：给你一个长度为\(n\)的排列\(P\)，有\(m\)次操作，每次操作给你三个数字op lr rs。含义如下：

op = 1表示将区间[lr , rs]内的元素按照升序排列
op = 2表示将区间[lr , rs]内的元素按照降序排列

最后问元素\(x\)所在的位置的下标。（下标从\(1\)开始编号）。

思路：此题与P2824 [HEOI2016/TJOI2016]排序的题目描述无不同考虑到这题的询问，需要寻求一种在线的解法，赛时找了博客 HEOI2016/TJOI2016]排序中的代码进行了魔改。涉及线段树合并和分裂的相关知识，可以找寻相关博客学习。

时间复杂度：\(O((n + m)logn + nlogn)\) 后一个\(nlogn\)是求解答案时需要的最坏复杂度

参考代码：

#include<bits/stdc++.h>
using ll = long long;
const int maxn = 300010;

struct Tree {
	Tree* ls, * rs;
	int l, r, v;
	Tree() {
		ls = rs = NULL;
		l = r = v = 0;
	}
	inline void pushup() { if (this->l != this->r) this->v = (this->ls ? this->ls->v : 0) + (this->rs ? this->rs->v : 0); else this->v = 1; }
};

struct OP {
	int l, r;
	bool up;
	Tree* rot;

	inline bool operator<(const OP& _others) const {
		return this->r < _others.r;
	}

	OP(int _l = 0, int _r = 0, bool _up = 0, Tree* _rot = 0) {
		l = _l; r = _r; up = _up; rot = _rot;
	}
};
OP temp;
std::set<OP>s;

int n, m;
int MU[maxn];

void split(int, bool);
void insert(Tree*, int, int, int);
void split(Tree*, Tree*, Tree*, int);
Tree* merge(Tree*, Tree*);
int query(Tree*, int);

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	using std::cin;
	using std::cout;
	int x;
	cin >> n >> m >> x;
	for (int i = 1; i <= n; ++i) {
		auto _rot = new Tree;
		cin >> MU[i];
		insert(_rot, 1, n, MU[i]); s.insert(OP(i, i, true, _rot));
	}
	for (int j = 1, a, b, c; j <= m; ++j) {
		cin >> a >> b >> c;
		--a;
		split(b, true); split(c + 1, false);
		auto l = s.lower_bound({ 0, b, true, NULL }), r = s.lower_bound({ 0, c + 1, true, NULL });
		auto _tmp = *l;
		for (auto i = s.erase(l); i != r; i = s.erase(i)) {
			_tmp.rot = merge(_tmp.rot, (*i).rot);
		}
		_tmp.l = b; _tmp.r = c; _tmp.up = !a;
		s.insert(_tmp);
	}
	for (int i = 1; i <= n; ++i) {
		int q = i;
		auto _ans = s.lower_bound({ 0, q, true, NULL }); auto ans = *_ans;
		int k = ans.up ? q - ans.l + 1 : ans.r - q + 1;
		q = query(ans.rot, k);
		if (q == x) {
			cout << i << '\n';
			return 0;
		}
	}
	return 0;
}
int query(Tree* u, int k) {
	if (u->l == u->r) return u->l;
	if (!u->ls) return query(u->rs, k);
	if (u->ls->v >= k) return query(u->ls, k);
	return query(u->rs, k - u->ls->v);
}

Tree* merge(Tree* u, Tree* v) {
	if (!u) return v; else if (!v) return u;
	u->v += v->v;
	u->ls = merge(u->ls, v->ls);
	u->rs = merge(u->rs, v->rs);
	return u;
}

void insert(Tree* u, int l, int r, int v) {
	++u->v;
	if ((u->l = l) == (u->r = r)) return;
	int mid = (l + r) >> 1;
	if (v <= mid) insert(u->ls = new Tree, l, mid, v);
	else insert(u->rs = new Tree, mid + 1, r, v);
}

void split(int x, bool isfront) {
	auto k = s.lower_bound({ 0, x, true, NULL }); if (k == s.end()) return; auto t = *k;
	if (t.l == x) return;
	s.erase(k);
	int _k = (isfront ? t.r - x + 1 : x - t.l), len = t.r - t.l + 1;
	if (t.up == isfront) {
		Tree* _rot = new Tree;
		_k = len - _k;
		if (!_k) {
			s.insert(t); return;
		}
		split(t.rot, t.rot, _rot, _k);
		if (!t.up) {
			_k = len - _k; std::swap(_rot, t.rot);
		}
		s.insert({ t.l, t.l + _k - 1, t.up, t.rot });
		s.insert({ t.l + _k, t.r, t.up, _rot });
	}
	else {
		Tree* _rot = new Tree;
		if (!_k) {
			s.insert(t); return;
		}
		split(t.rot, t.rot, _rot, _k);
		if (!t.up) {
			std::swap(t.rot, _rot); _k = len - _k;
		}
		s.insert({ t.l, t.l + _k - 1, t.up, t.rot });
		s.insert({ t.l + _k, t.r, t.up, _rot });
	}
}

void split(Tree* u, Tree* l, Tree* r, int k) {
	l->l = r->l = u->l; r->r = l->r = u->r;
	if (!u->ls) split(u->rs, l->rs ? l->rs : l->rs = new Tree, r->rs ? r->rs : r->rs = new Tree, k);
	else if (k == u->ls->v) {
		l->ls = u->ls; r->rs = u->rs; l->rs = NULL; r->ls = NULL;
	}
	else if (k < u->ls->v) {
		split(u->ls, l->ls ? l->ls : l->ls = new Tree, r->ls ? r->ls : r->ls = new Tree, k);
		r->rs = u->rs; l->rs = NULL;
	}
	else {
		split(u->rs, l->rs ? l->rs : l->rs = new Tree, r->rs ? r->rs : r->rs = new Tree, k - u->ls->v);
		l->ls = u->ls; r->ls = NULL;
	}
	l->pushup(); r->pushup();
}

码农公寓

AtCoder Beginner Contest 237题解

AtCoder Beginner Contest 237

A - Not Overflow

B - Matrix Transposition

C - kasaka

D - LR insertion

E - Skiing

F - |LIS| = 3

G - Range Sort Query

相关文章