2024 CCPC 沈阳
本部落格所有文章除特別聲明外，均採用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 游戏，nnn 个人每人要抢 kkk 个数，主持人按随机顺序依次报数，报到每个数 [1,109][1,10^{9}][1,109] 的概率相同。已知如果有多名选手要抢某个数字，那么编号小的选手总是优先抢到。问每个人成为最后一名（其他人都抢完了但自己还没抢完）的概率。 ...
2025-01-11
Good Bye 2024: 2025 is NEAR A - E
2053A - Tender Carpenter 123456789101112131415161718192021222324252627#include <bits/stdc++.h>using namespace std;using ll = long long;int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } int cnt = 0; for (int i = 1; i < n; i++) { int j = i - 1; cnt += (2 * a[i] > a[j]...
2024-05-08
樹上問題 - 樹形 DP
TreeDP 树，有根有点权。点集 SSS 满足：若父节点 ∈S\in S∈S，则子节点 ∉S\not\in S∈S。最大化 SSS 点权和。（ 树的最大独立集 ） 12345678910int n, w[N], dp[N][2];void dfs(int u) { dp[u][1] = w[u]; for (auto v : E[u]) { dfs(v); dp[u][0] += max(dp[v][0], dp[v][1]); dp[u][1] += dp[v][0]; }}print(max(dp[rt][0], dp[rt][1])); 树，有根有点权。mmm 元点集 SSS 满足：若子节点 ∈S\in S∈S，则父节点 ∈S\in S∈S。最大化 SSS 点权和。（ 树上背包 ） 123456789101112int n, m, w[N], dp[N][M];void dfs(int u) { dp[u][1] = w[u]; ...
2024-10-27
Codeforces Round 982 (Div. 2)
A. Rectangle Arrangement 取最大值的正确性：凸阶梯形平移后即是矩形，其周长与矩形周长相等。 123456789101112131415161718192021222324252627#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--) { int n; cin >> n; int X = 0, Y = 0; while (n--) { int x, y; cin >> x >> y; X = max(X, x); Y = max(Y, y);...
2025-03-11
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()); ...
2025-02-28
Educational Codeforces Round 176 (Rated for Div. 2) A-D
edu 场神秘分类讨论，神秘推式子。 2075A - To Zero 一次偶数那之后都是偶数。 1234567891011121314151617181920212223#include <bits/stdc++.h>using namespace std;int main() { int J; cin >> J; while (J--) { int n, k; cin >> n >> k; int res = 0; if (n & 1) { n = max(0, n - k); res++; } k--; res += (n + k - 1) / k; cout << res << endl; } return 0;} 2075B - Array...
評論