Good Bye 2024: 2025 is NEAR A - E

發表於2025-01-11|更新於2025-01-11|筆記練習賽

|瀏覽量:

无向图有边权。有 $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$ 。

文章作者: 小明同學

文章連結: http://kobicgend.top/posts/ba204004.html

版權聲明: 本部落格所有文章除特別聲明外，均採用CC BY-NC-SA 4.0 授權協議。轉載請註明來源小明の雜貨鋪！

ACM 筆記算法題解練習賽

相關推薦

【算法杂谈 + 好题分享】图论中的懒标记 LazyTag 思想

有三件物品可供选择，物品甲重量为 3，物品乙重量为 8，物品丙重量为 5。有一个背包，问选择任意件物品放入背包后，背包总重为 8 的方案数。列出所有的可能：选甲，选乙，选丙；选甲，选乙，选丙；选甲，选乙，不选丙；选甲，不选乙，选丙；选甲，不选乙，不选丙；不选甲，选乙，选丙；不选甲，选乙，不选丙；不选甲，不选乙，选丙；不选甲，不选乙，不选丙。每个物品 X 都有两种状态：选 X 或不选 X，而且每个物品的状态相互独立，直接用一个式子表达：（选甲或不选甲）且（选乙或不选乙）且（选丙或不选丙）这个逻辑表达式包含了上面全部八种情形。这里且的含义是，如果 A 且 B，那么 A 必须执行，B 也必须执行。把物品重量一并列入上面的表达式中：（重量为 3 或重量为 0）且（重量为 8 或重量为 0）且（重量为 5 或重量为 0）这样写虽然能表达所有的情况，但文字太多还是太麻烦了。希望选取一些数学符号，完全转化为数学表达式。观察这个式子：（重量为 3 或重量为 0）且（重量为 8 或重量为...

Codeforces Global Round 27 A-D

A. Sliding 12345678910111213141516171819202122#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 依据样例，奇数是...

Codeforces Round 1008 (Div. 1) A - C

2077A/2078C - Breach of Faith 取较大的 n2+1\cfrac{n}{2}+12n+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()); ...

Educational Codeforces Round 175 (Rated for Div. 2) A-E

2070A. FizzBuzz Remixed 12345678910111213141516#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。 ...

樹上問題 - 樹形 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 =...

2024 CCPC 沈阳

2024 China Collegiate Programming Contest (CCPC) Zhengzhou Onsite (The 3rd Universal Cup. Stage 22: Zhengzhou)

評論