当前位置：首页 > news >正文

ABC391题解

news 来源：原创 2025/7/27 8:36:30

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;// 将当前状态转化为dps_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;
}

ABC391题解

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({…...

编程日记 2025/7/27 8:36:30

React - LineChart组件编写（用于查看每日流水图表）

一、简单版本 LineChart.tsx // src/component/LineChart/LineChart.tsx import React, {useEffect,useRef,useImperativeHandle,forwardRef,useMemo,useCallback, } from react; import * as echarts from echarts/core; import type { ComposeOption } from echarts/core; …...

编程日记 2025/7/27 8:27:03

A

算法标签: 模拟

B

算法标签: 模拟

C

算法标签:

思路

D

算法标签: 离线做法

思路

E

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

F

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

思路

G

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

思路

快速取模优化

完整代码

相关文章：

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

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