Good Bye 2024: 2025 is NEAR A - E
无向图有边权。有 $q$ 个形式为 $(a, b, k)$ 的查询：从顶点 $a$ 到顶点 $b$ 的所有路径中，找出路径 上第 $k$ 大边权的最小值。$n \leqslant 400,\ q \leqslant 3 \times 10^{5}$。
枚举答案 $w$，把边权 $\leqslant w$ 的变成 0，$> w$ 的变成 1。如果 $d_{a\to b}<k$，就说明答案 $\leqslant w$。
本部落格所有文章除特別聲明外，均採用CC BY-NC-SA 4.0 授權協議。轉載請註明來源 小明の雜貨屋！
相關推薦
2025-04-01
【组合计数杂谈】三道 Bingo 游戏题（备份）
本文涉及的知识点：组合数公式，古典概型，Min-Max 反演及推广，卷积优化思想，状态压缩思想与状态压缩 DP，快速数论变换 NTT，快速数论变换 NTT，快速沃尔什变换 FWT。 本系列教程「以题带讲」，以典型题目为载体，着重讲解知识点的适用条件和使用方法，而规避复杂的理论推导。 我不擅长数学，对 CF 和区域赛的数学题，从简单计算到数论组合都望而却步。「tag 是数学吗那不做了。」 可能是因为网上的教程大多是罗列定理，给出大段证明，最后放几个例题链接。我没有耐心和能力读完整篇文章。 2024 ICPC World Finals Astana B. Bingo for the Win! Bingo 游戏，$n$ 个人每人要抢 $k$ 个数，主持人按随机顺序依次报数，报到每个数 $[1,10^{9}]$...
2024-10-27
Codeforces Global Round 27 A-D
A. Sliding12345678910111213141516171819202122#include <bits/stdc++.h>using namespace std;using ll = long long;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { ll n, m, r ,c; cin >> n >> m >> r >> c; ll ans = (n - r) * (2 * m - 1); ans += (m - c); cout << ans << "\n"; } return 0;} B. Everyone Loves Tres 依据样例，奇数是...
2025-03-11
Codeforces Round 1008 (Div. 1) A - C
2077A/2078C - Breach of Faith 取较大的 $\cfrac{n}{2}+1$ 个放在奇数位，较小的放在偶数位。 12345678910111213141516171819202122232425262728293031323334353637#include <bits/stdc++.h>using namespace std;using ll = long long;int main() { int J; cin >> J; while (J--) { int n; cin >> n; vector<int> a(n * 2); for (int i = 0; i < n * 2; i++) { cin >> a[i]; } sort(a.begin(), a.end()); vector<ll>...
2025-02-28
Educational Codeforces Round 175 (Rated for Div. 2) A-E
2070A. FizzBuzz Remixed12345678910111213141516#include <bits/stdc++.h>using namespace std;int main() { int J; cin >> J; while (J--) { int n; cin >> n; cout << (n / 15 * 3 + min(n % 15, 2) + 1) << endl; } return 0;} 2070B - Robot Program 仔细审题 题解 分为两部分考虑，从起点走到 0，从 0 下一次走到 0。 ...
2024-05-08
樹上問題 - 樹形 DP
Diameter 法 1 两次 DFS。 12345678910111213141516171819202122232425262728293031323334vector<pair<int, int> > E[N];int c; // 直径的端点 int lst[N], nxt[N], vis[N];int dep[N], dis[N];void dfs(int u, int fau = 0) { lst[u] = fau; // 记录路径 for (auto [w, v] : E[u]) { if (v != fau) { dep[v] = dep[u] + w; if (dep[v] > dep[c]) c = v; dfs(v, u); } }} // 两轮 DFS 找到距离根节点最远的点 void dfs2(int gfa, int u, int fau =...
2025-02-11
AtCoder Regular Contest 192 (Div. 2)
官方题解 A. ARC Arc 给定 01 串 $a$，问能否构造一个字符串 $t$，使得执行若干次操作后，$a$ 串全为 1。一次操作定义为： 选择一个下标 $i$，满足 $t$ 的 $[i,i+2]$ 三个位置为 ARC 或 CRA，将 $a$ 的 $[i,i+1]$ 两个位置替换为 1。（字符串是循环的，$t{-1}=t{n-1}$） 什么样的 t 串最好，也即什么样的 t 串能覆盖尽可能多的位置？ ARCRARCR... 有可能覆盖所有位置吗？应当如何分类讨论？ ARCRARCR... 的周期是 4。 当 $a$ 串长度 $n$ 是 4 的倍数时，ARCRARCR...ARCR 总是最好的。应当按字符串长度模 4 分类讨论。 另外注意，无解的情形不会很多。 完整解析 ...
評論
