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

ABC398题解

news 来源：原创 2025/7/30 17:50:28

A

算法标签: 模拟

在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 110;int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int n;cin >> n;string res;if (n % 2) {int mid = n / 2;for (int i = 0; i < mid; ++i) res += '-';res += '=';for (int i = mid + 1; i < n; ++i) res += '-';}else {int mid = n / 2;for (int i = 0; i < mid - 1; ++i) res += '-';res += "==";for (int i = mid + 1; i < n; ++i) res += '-';}cout << res << "\n";return 0;
}

B

算法标签: 哈希, 模拟

在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>using namespace std;const int N = 7;map<int, int> mp;int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);for (int i = 0; i < N; ++i) {int val;cin >> val;if (mp.count(val)) mp[val]++;else mp.insert({val, 1});}if (mp.size() < 2) {cout << "No" << "\n";return 0;}for (auto [val1, cnt1] : mp) {for (auto [val2, cnt2] : mp) {if (val1 == val2) continue;if (cnt1 >= 3 && cnt2 >= 2) {cout << "Yes" << "\n";return 0;}}}cout << "No" << "\n";return 0;
}

C

算法标签: 哈希, 模拟

在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>using namespace std;const int N = 3e5 + 10;int n, w[N];
map<int, int> mp;
map<int, int> idx_map;int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; ++i) {cin >> w[i];if (mp.count(w[i])) mp[w[i]]++;else {mp.insert({w[i], 1});idx_map[w[i]] = i;}}int res = 0;for (auto [val, k] : mp) {if (k == 1 && val > res) {res = val;}}if (idx_map.count(res) == 0) res = -1;else res = idx_map[res];cout << res << "\n";return 0;
}

D

算法标签: 哈希, 模拟

在这里插入图片描述

思路

$N$ 的范围是 $10 ^ 5$ , 等价于偏移终点位置, 风的偏移方向和人的方向是相反的
固定高桥君的位置, 改变起始产生烟雾的位置

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>using namespace std;typedef pair<int, int> PII;
const int N = 2e5 + 10;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1};int n, r, c;
string s;
map<PII, int> mp;int get(char c) {if (c == 'S') return 0;if (c == 'W') return 1;if (c == 'N') return 2;return 3;
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> r >> c >> s;s = ' ' + s;mp[{0, 0}] = 1;int x = 0, y = 0;for (int i = 1; i <= n; ++i) {int op = get(s[i]);op += 2;op %= 4;x += dx[op], y += dy[op];mp[{x, y}] = 1;cout << mp[{r + x, c + y}];}cout << "\n";return 0;
}

E

算法标签: 博弈论, 二分图, 交互题

在这里插入图片描述

思路

注意到, 没有奇环等价于是二分图, 轮流连边不能破坏二分图的性质
对二分图进行染色, 之间有一些边, 只能点对 $(i, j)$ 分别是白色和黑色, 假设白色点的数量是 $a$ , 黑色点的数量是 $b$ , 那么能够加的边的数量是 $\times b - (n - 1)$ , 如果是奇数必胜, 否则必败

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>using namespace std;typedef pair<int, int> PII;
const int N = 110;int n, w[N][N];
int color[N];
set<PII> s;void dfs(int u, int fa) {for (int v = 1; v <= n; ++v) {if (w[u][v] && v != fa) {color[v] = color[u] ^ 1;dfs(v, u);}}
}int main() {scanf("%d", &n);for (int i = 0; i < n - 1; ++i) {int u, v;scanf("%d%d", &u, &v);w[u][v] = w[v][u] = 1;}dfs(1, -1);// 统计可用的边for (int i = 1; i <= n; ++i) {for (int j = i + 1; j <= n; ++j) {if (!w[i][j] && color[i] != color[j]) s.insert({i, j});}}if (s.size() % 2) puts("First");else puts("Second");fflush(stdout);while (true) {if (s.size() % 2) {auto [u, v] = *s.begin();s.erase(s.begin());printf("%d %d\n", u, v);fflush(stdout);}else {int u, v;scanf("%d%d", &u, &v);if (u == -1 && v == -1) return 0;s.erase({u, v});}}return 0;
}

F

算法标签: 字符串哈希, 回文串

在这里插入图片描述

思路

在这里插入图片描述
对于一个回文串来说, $a = b$ , 因此如果想将当前串补为最短回文串, 就需要找到最长的回文后缀, 因为 $a$ 越长 $b$ 越长, 需要补的长度就越小, 注意到原始字符串长度为 $\times 10 ^ 5$ , 枚举后缀后要迅速判断是否是回文串, 也就不能扫描, 只能用常数做法, 判断正着读是否等于倒着读, 快速判断两个字符串是否是相等的, 使用哈希

判断后缀是否是回文串, 求每个前缀的哈希值, 再翻转, 然后再计算一遍哈希值

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef long long LL;
const int N = 5e5 + 10, MOD = 998244353;int n;
string str;
int pre[N], suff[N];int main() {cin >> str;int n = str.size();str = " " + str;for (int i = n; i >= 1; --i) {suff[i] = ((LL) 26 * suff[i + 1] + (str[i] - 'A')) % MOD;}reverse(str.begin() + 1, str.end());int base = 1;for (int i = 1; i <= n; ++i) {pre[i] = ((LL) pre[i - 1] + (LL) base * (str[i] - 'A') % MOD) % MOD;base = (LL) 26ll * base % MOD;}reverse(pre + 1, pre + n + 1);reverse(str.begin() + 1, str.end());for (int i = 1; i <= n; ++i) {if (pre[i] == suff[i]) {for (int k = 1; k <= n; ++k) cout << str[k];for (int k = i - 1; k >= 1; --k) cout << str[k];cout << "\n";break;}}return 0;
}

G

算法标签: 博弈论, 二分图

在这里插入图片描述
注意到这个图是不一定连通的, 白色点数量和黑色点数量在博弈过程中可以进行更改, 添加边的数量的奇偶性也会更改, 与图的形态没有关系

A

算法标签: 模拟

B

算法标签: 哈希, 模拟

C

算法标签: 哈希, 模拟

D

算法标签: 哈希, 模拟

思路

E

算法标签: 博弈论, 二分图, 交互题

思路

F

算法标签: 字符串哈希, 回文串

思路

G

算法标签: 博弈论, 二分图

相关文章：