V_Melville - 博客园

[置顶] 算法竞赛中的经典结论总结

摘要：排列的环分解单次交换操作的效果：当交换元素属于不同环时 \(\to\) 合并两个环当交换元素属于同一个环时 \(\to\) 将该环分裂为两个由于所有环的长度之和为 \(N\)，且每个环长度均为正整数，因此不同的环长度数量最多只有 \(O(\sqrt{N})\) 种随机置换的期望循环数为调和阅读全文

posted @ 2025-09-03 16:26 V_Melville 阅读(45) 评论(0) 推荐(0)

[置顶] dp题选做

摘要： 1. 在两个数列之间有两个整数数列 \(a_1,a_2,\cdots,a_n\) 和 \(b_1,b_2,\cdots,b_n\)。我们的任务是找出满足以下条件的数列 \(c_1,c_2,\cdots,c_n\)：对 \(i=1,2,\cdots,n\)，\(a_i \le c_i \le b_ 阅读全文

posted @ 2024-06-19 17:15 V_Melville 阅读(44) 评论(0) 推荐(1)

[置顶] AT题选做

摘要： AGC020C. Median Sum 记原序列的总和为 \(S\) 容易发现如果把空集也考虑进去的话，在左边任取一个子集，其和为 \(x\)，那么一定可以在右边找到一个子集满足它的和为 \(S - x\)。也就是说，位于权值为 \(\frac{S}{2}\) 的左右两边的子集是对称的。于是，我们阅读全文

posted @ 2024-06-07 21:43 V_Melville 阅读(61) 评论(0) 推荐(0)

ARC++221

摘要： A. Two Arithmetic Progressions 在多项式欧几里得算法中，将 \(\gcd\) 的其中一个参数改为常数 \(\rightarrow\) 求出能被各个约数整除的方案数，然后进行约数容斥。 B. Two-Powered Sum 逆向操作。如果复杂度是 \(O(N^4)\)，可阅读全文

posted @ 2026-06-01 14:27 V_Melville 阅读(9) 评论(0) 推荐(0)

ABC460

摘要： C. Sushi 贪心从寿司饭较轻的开始看，尽量匹配较轻的配料代码实现 #include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (n); ++i) using namespace std; int main() { int n 阅读全文

posted @ 2026-05-31 15:17 V_Melville 阅读(14) 评论(0) 推荐(0)

ABC459

摘要： C. Drop Blocks 只需维护以下三个量即可： \(h_i\) 表示第 \(i\) 个格子被放置方块的总次数（从历史上累加，不随删除而改） \(c_i\) 表示记录“有至少 \(k\) 次放置” 的格子数 \(l\) 表示已经执行的“全格子减 1”操作次数（相当于全局基准）。代码实现 #i 阅读全文

posted @ 2026-05-24 10:05 V_Melville 阅读(45) 评论(0) 推荐(1)

ARC++220

摘要： A. Sum of Reciprocals of Squares 给定满足 \(\sum \frac {1} {A_i^2} = 1\) 的序列 \(A\)，可以通过把某个元素 \(A_i\) 替换为四个 \(2A_i\) 来使序列长度增加 \(+3\)。对于 \(∣A∣ \bmod 3 = 0,1 阅读全文

posted @ 2026-05-20 15:48 V_Melville 阅读(23) 评论(0) 推荐(0)

ABC458

摘要： C. C Stands for Center 枚举 C 出现的位置代码实现 #include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (n); ++i) using namespace std; using ll = long l 阅读全文

posted @ 2026-05-17 13:24 V_Melville 阅读(22) 评论(0) 推荐(0)

ABC456

摘要： C. Not Adjacent 找出所有的极长合法子串代码实现 #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; #define rep(i, n) for (int i = 0; i < (n); + 阅读全文

posted @ 2026-05-16 15:29 V_Melville 阅读(8) 评论(0) 推荐(0)

ARC-- 219

摘要： A. Similarity 从 \(2^{\min(20, m)}\) 种可能的 \(01\) 串中找一个不在 \(S\) 中的串，然后将这个串的所有字符翻转一下即可 B. Reverse Permutation 枚举 \(P\) 和 \(Q\) 的 \(\text{LCP}\) 的长度 C. Tr 阅读全文

posted @ 2026-05-11 16:05 V_Melville 阅读(11) 评论(0) 推荐(0)

ABC457

摘要：这场被E偷袭一手，没时间做后面的G了，没想到是个大水题~~ 阅读全文

posted @ 2026-05-10 14:43 V_Melville 阅读(49) 评论(0) 推荐(1)

NDPC

摘要： C. String 将子序列判定进行到什么程度作为 DP 状态。 D. Banknote 将问题视为：针对剩余金额，可以进行 \(+10^k\) 或 \(-10^k\) 的操作，目标是使其归零。当余额满足 \(\pmod{10} = 0\) 时可以执行 \(/10\) 操作，每一层的决策分支始终不超阅读全文

posted @ 2026-05-05 20:23 V_Melville 阅读(34) 评论(0) 推荐(0)

ARC218

摘要： A. Many Sets 各个值出现概率的总和即为种类数的期望值。通过考虑余事件（反面情况）来计算概率。 B. All Minus 如果在自己的回合能够做出两种或两种以上的操作，则可以通过策略偷取策略获胜。 C. Amidakuji 通过循环移位和交换操作进行重新排序。 D. I like Incr 阅读全文

posted @ 2026-05-04 14:18 V_Melville 阅读(12) 评论(0) 推荐(0)

导航

公告

2026年6月1日

2026年5月31日

2026年5月24日

2026年5月20日

2026年5月17日

2026年5月16日

2026年5月11日

2026年5月10日

2026年5月5日

2026年5月4日