ABC391题解

AtCoder Beginner Contest 391

Ayanami_Rei

805人浏览 · 2025-03-25 20:41:57

Ayanami_Rei · 2025-03-25 20:41:57 发布

A

算法标签: 模拟

在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;

const int N = 8;
map<string, string> mp;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	mp.insert({"N", "S"});
	mp.insert({"S", "N"});
	mp.insert({"E", "W"});
	mp.insert({"W", "E"});

	mp.insert({"NE", "SW"});
	mp.insert({"SW", "NE"});
	mp.insert({"NW", "SE"});
	mp.insert({"SE", "NW"});

	string s;
	cin >> s;
	cout << mp[s] << "\n";

	return 0;
}

B

算法标签: 模拟

在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 60;

int n, m;
char w1[N][N], w2[N][N];

bool check(int x, int y) {
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < m; ++j) {
			if (w1[i + x][j + y] != w2[i][j]) return false;
		}
	}
	return true;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> w1[i];
	for (int i = 0; i < m; ++i) cin >> w2[i];

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (check(i, j)) {
				cout << i + 1 << " " << j + 1 << "\n";
				return 0;
			}
		}
	}

	return 0;
}

C

算法标签:

在这里插入图片描述

思路

鸽子数量 $10 ^ 6$ , 需要线性做法, 开两个数组记录每个鸽子属于哪个巢穴, 以及记录每个巢穴的鸽子数量

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n, m;
int fa[N], cnt[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) fa[i] = i, cnt[i] = 1;

	int curr = 0;
	while (m--) {
		int op;
		cin >> op;
		if (op == 1) {
			int val, target;
			cin >> val >> target;
			int pos = fa[val];
			
			if (cnt[pos] == 2) curr--;
			cnt[pos]--;
			
			if (cnt[target] == 1) curr++;
			cnt[target]++;
			fa[val] = target;
		}
		else cout << curr << "\n";
	}

	return 0;
}

D

算法标签: 离线做法

在这里插入图片描述

思路

因为数据范围很大, 方块的数量是 $10 ^ 5$ 量级, 判断 $t$ 时刻某个方块是否存在, 将询问时间从小到大排序, 就可以边询问边处理, 这样就能降低复杂度到 $O (T)$

具体做法就是, 首先将所有能下落的方块进行下落, 然后判断是否能消除

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;

typedef pair<int, int> PII;
const int N = 2e5 + 10;

int n, w, q;
// ((Y, X), 方块id)
pair<PII, int> block[N];
// ((查询时间T, 方块编号A), 查询id)
pair<PII, int> qs[N];
bool ans[N], alive[N];
deque<int> wait_to_del[N];
// 记录有多少列有方块等待被删除
int cnt = 0;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> w;
	for (int i = 1; i <= n; ++i) {
		cin >> block[i].first.second >> block[i].first.first;
		block[i].second = i;
		alive[i] = true;
	}

	cin >> q;
	for (int i = 1; i <= q; ++i) {
		cin >> qs[i].first.first >> qs[i].first.second;
		qs[i].second = i;
	}

	// 将方块按Y坐标升序排序，查询按时间升序排序
	sort(block + 1, block + n + 1);
	sort(qs + 1, qs + q + 1);

	// 当前处理的方块指针
	int curr = 1;
	for (int i = 1; i <= q; ++i) {
		int t = qs[i].first.first;
		int a_id = qs[i].first.second;
		int q_id = qs[i].second;

		// 处理所有在时间t之前应该下落到底部的方块
		while (curr <= n && block[curr].first.first <= t) {
			int col = block[curr].first.second;
			int id = block[curr].second;
			if (wait_to_del[col].empty()) ++cnt;
			wait_to_del[col].push_back(id);
			curr++;
		}

		// 检查是否最底行已满（所有列都有方块等待删除）
		while (cnt == w) {
			for (int j = 1; j <= w; ++j) {
				// 删除该列最下面的方块
				alive[wait_to_del[j].front()] = false;
				wait_to_del[j].pop_front();
				if (wait_to_del[j].empty()) --cnt;
			}
		}

		// 记录当前查询的答案
		ans[q_id] = alive[a_id];
	}

	// 输出所有查询结果
	for (int i = 1; i <= q; ++i) {
		cout << (ans[i] ? "Yes" : "No") << "\n";
	}

	return 0;
}

E

算法标签: 递推, 动态规划, 三叉树, 树形 $d p$

在这里插入图片描述
每个三元组输出保留出现次数最多的那个字符, 计算最少翻转几个位置, 使得最终答案发生改变

如果改变根节点, 那么子节点的选取就要发生改变, 具有递归的性质, 也就是当前问题答案由子问题得到, 设递推状态 $f [i]$ 表示将节点 $i$ 翻转的最小代价

如何计算状态转移?
考虑当前值是如何计算得到的, 也就是第 $n + 1$ 层的状态分类, 分为 $(x, x, x)$ 和 $(x, x, x^{'})$ , 第一种情况找到两个最小代价相加, 第二种在 $(x, x)$ 中选择最小代价, 因为当前层只会取决于 $n + 1$ 层数, 因此可以滚动数组优化

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 10, INF = 0x3f3f3f3f;

string s;
int n;
int f[(N << 2) + 10];
int cnt = 1;

int dfs(int u, int l, int r) {
	if (l == r) {
		f[u] = 1;
		return s[r] - '0';
	}
	int ls = ++cnt, ms = ++cnt, rs = ++cnt;

	int len = r - l + 1;
	int l_val = dfs(ls, l, l + len / 3 - 1);
	int m_val = dfs(ms, l + len / 3, l + len / 3 * 2 - 1);
	int r_val = dfs(rs, l + len / 3 * 2, r);

	int cnt0 = 0, cnt1 = 0;
	if (l_val == 0) cnt0++; else cnt1++;
	if (m_val == 0) cnt0++; else cnt1++;
	if (r_val == 0) cnt0++; else cnt1++;
	int now_val = cnt0 > cnt1 ? 0 : 1;
	f[u] = INF;

	//只需要改一个的情况
	if ((now_val == 0 && cnt1 == 1) || (now_val == 1 && cnt0 == 1)) {
		if (l_val == now_val) f[u] = min(f[u], f[ls]);
		if (m_val == now_val) f[u] = min(f[u], f[ms]);
		if (r_val == now_val) f[u] = min(f[u], f[rs]);
	}
	else {
		f[u] = min(f[u], f[ls] + f[ms]);
		f[u] = min(f[u], f[ls] + f[rs]);
		f[u] = min(f[u], f[ms] + f[rs]);
	}
	return now_val;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> s;
	s = " " + s;
	dfs(1, 1, s.size() - 1);

	cout << f[1] << "\n";
	return 0;
}

F

算法标签: 贪心, 堆, 枚举, 排序, 优先队列

在这里插入图片描述

思路

首先考虑简单的情况, 假设只有两个序列, 有 $N ^ 2$ 对二元组第 $k$ 大的值, $\le 5 \times 10 ^ 5$ , 如果每一步找最大值花的时间很少, 那么可以不停的找, 知道找到 $k$

在这里插入图片描述
对于二维情况, 将 $A_i$ 和 $B_i$ 从大到小排序, 假设 $(i, j)$ 是最大值, 下一个最大值一定是 $(i + 1, j)$ 和 $(i, j + 1)$ 两个数字中选择, 也就是每次扩展一维中的一个, 需要使用 $se t$ 判重, 逐步探索

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <tuple>

using namespace std;

typedef long long LL;
const int N = 2e5 + 10;

int n, k;
int a[N], b[N], c[N];

struct Node {
	int a, b, c;
	LL res;

	bool operator<(const Node &n) const {
		return res < n.res;
	}
};

LL get(int i, int j, int k) {
	return (LL) a[i] * b[j] + (LL) a[i] * c[k] + (LL) b[j] * c[k];
}

LL get_hash(int x, int y, int z) {
	return (LL) x * N * N + (LL) y * N + z;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> k;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) cin >> b[i];
	for (int i = 1; i <= n; ++i) cin >> c[i];

	sort(a + 1, a + n + 1, greater<int>());
	sort(b + 1, b + n + 1, greater<int>());
	sort(c + 1, c + n + 1, greater<int>());

	priority_queue<Node> q;
	set<LL> s;
	
	q.push({1, 1, 1, get(1, 1, 1)});
	s.insert(get_hash(1, 1, 1));

	int cnt = 0;
	LL ans = 0;

	while (!q.empty() && cnt < k) {
		auto [x, y, z, res] = q.top();
		q.pop();
		cnt++;
		ans = res;
		if (cnt == k) break;

		if (x + 1 <= n) {
			LL hash = get_hash(x + 1, y, z);
			if (!s.count(hash)) {
				LL new_res = get(x + 1, y, z);
				q.push({x + 1, y, z, new_res});
				s.insert(hash);
			}
		}

		if (y + 1 <= n) {
			LL hash = get_hash(x, y + 1, z);
			if (!s.count(hash)) {
				LL new_res = get(x, y + 1, z);
				q.push({x, y + 1, z, new_res});
				s.insert(hash);
			}
		}
		
		if (z + 1 <= n) {
			LL hash = get_hash(x, y, z + 1);
			if (!s.count(hash)) {
				LL new_res = get(x, y, z + 1);
				q.push({x, y, z + 1, new_res});
				s.insert(hash);
			}
		}
	}

	cout << ans << "\n";
	return 0;
}

G

算法标签: 动态规划, $d p$ 套 $d p$

在这里插入图片描述

思路

最长公共子序列 $L CS$ , 设 $f [i] [j]$ 表示考虑第一个串的前 $i$ 个字符, 第二个串的前 $j$ 个字符的 $L CS$ 长度, 定义 $g [i] [j]$ 字符串 $T$ 已经填完了前 $i$ 个位置, 并且将前 $i$ 个位置和 $S$ 求 $L CS$ 的所有方案

$g [i] (f [1] [i], f [2] [i], ..., f [n] [i])$

因为转移过程是从 $i$ 到 $i + 1$ , 也就是新加入的状态 $f [*] [i + 1]$ 通过第 $i$ 列的值就能进行转移, 也就是没填一个字符的时候保存前一个字符的状态就可以了

但是, 如果直接创建 $n$ 元组来代表 $g$ 数组的第二维, 空间复杂度非常大 $10 ^ {10}$ 量级

$\ge f[x - 1][i]$
$\ge f[x][i]$

差分数组是 $01$ 串, 可以状态压缩, 时间复杂度 $\cdot 2 ^ {N} \cdot 26 \cdot N)$

快速取模优化

void add(int &x, int y) {
	x += y - mod;
	x += x >> 31 & mod;
}

完整代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 16, M = 110, MOD = 998244353;

int n, m;
string s;
int f[2][1 << N], now;
int tmp[N], nxt[N], ans[N];

void s_to_dp(int s, int g[]) {
	g[0] = 0;
	for (int i = 0; i < n; ++i) {
		g[i + 1] = g[i] + (s >> i & 1);
	}
}

int dp_to_s(int g[]) {
	int s = 0;
	for (int i = 0; i < n; ++i) {
		s |= (g[i + 1] != g[i]) << i;
	}
	return s;
}

void get_next_dp(int pre[], int nxt[], int c) {
	nxt[0] = 0;
	for (int i = 1; i <= n; ++i) {
		nxt[i] = max(pre[i], nxt[i - 1]);
		if (s[i] - 'a' == c) {
			nxt[i] = max(nxt[i], pre[i - 1] + 1);
		}
	}
}

void add(int &x, int y) {
	x += y;
	if (x >= MOD) x -= MOD;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> s;
	s = " " + s;

	f[now][0] = 1;
	for (int i = 1; i <= m; ++i) {
		memset(f[now ^ 1], 0, sizeof f[now ^ 1]);

		for (int s = 0; s < 1 << n; ++s) {
			if (!f[now][s]) continue;

			// 将当前状态转化为dp
			s_to_dp(s, tmp);
			// 枚举下一个字符, 计算下一个位置状态
			for (int c = 0; c < 26; ++c) {
				get_next_dp(tmp, nxt, c);
				int next_s = dp_to_s(nxt);
				// 累加答案
				add(f[now ^ 1][next_s], f[now][s]);
			}
		}
		// 数组滚动
		now ^= 1;
	}
	
	
	for (int s = 0; s < 1 << n; ++s) {
		if (!f[now][s]) continue;
		s_to_dp(s, tmp);
		add(ans[tmp[n]], f[now][s]);
	}

	for (int i = 0; i <= n; ++i) cout << ans[i] << " ";
	cout << "\n";

	return 0;
}