2024 CCPC 沈阳
本部落格所有文章除特別聲明外，均採用CC BY-NC-SA 4.0 授權協議。轉載請註明來源 小明の雜貨屋！
相關推薦
2025-04-01
【算法杂谈 + 好题分享】图论中的懒标记 LazyTag 思想
有三件物品可供选择，物品甲重量为 3，物品乙重量为 8，物品丙重量为 5。有一个背包，问选择任意件物品放入背包后，背包总重为 8 的方案数。 列出所有的可能： 选甲，选乙，选丙； 选甲，选乙，选丙； 选甲，选乙，不选丙； 选甲，不选乙，选丙； 选甲，不选乙，不选丙； 不选甲，选乙，选丙； 不选甲，选乙，不选丙； 不选甲，不选乙，选丙； 不选甲，不选乙，不选丙。 每个物品 X 都有两种状态：选 X 或不选 X，而且每个物品的状态相互独立，直接用一个式子表达： （选甲 或 不选甲）且（选乙 或 不选乙）且（选丙 或 不选丙） 这个逻辑表达式包含了上面全部八种情形。这里 且 的含义是，如果 A 且 B，那么 A 必须执行，B 也必须执行。 把物品重量一并列入上面的表达式中： （重量为 3 或 重量为 0）且（重量为 8 或 重量为 0）且（重量为 5 或 重量为 0） 这样写虽然能表达所有的情况，但文字太多还是太麻烦了。希望选取一些数学符号，完全转化为数学表达式。 观察这个式子： （重量为 3 或 重量为 0）且（重量为 8 或 重量为...
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-10-27
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 依据样例，奇数是...
2025-03-11
Codeforces Round 1009 (Div. 3) E - G
2074E - Empty Triangle Hint 1 随机化 平面上 nnn 个点是毫无规律的，就算每个点问一次也只能问到 3×753\times 753×75 个点，这个数远小于 150015001500，想要让每个点地位平等，考虑随机。 Hint 2 从一个已知的三角形往里缩 相比包含特殊点的三角形，不包含的三角形其面积相对较小。而且包含特殊点的三角形内部一定有答案。如果问到一个包含特殊点的三角形，想法是往里缩，直到找到答案。 具体地，如果问到 x−y−zx-y-zx−y−z 里面包含 uuu，可能会考虑继续问 x−y−ux-y-ux−y−u 或 x−u−zx-u-zx−u−z 或 u−y−zu-y-zu−y−z。这里有好几种选择，用随机数选。 123456789101112131415161718192021222324252627282930#include <bits/stdc++.h>using namespace std;mt19937_64...
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...
2026-05-30
01Trie
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121struct Node { std::array<Node*, 2> next{}; int icnt = 0;};void insert(Node*& p, int val, int bit = 30) { if (!p) { p = new Node(); } p->icnt++; if (bit == -1) return; ...
評論