My Blog

自动取模，包含逆元和快速幂

线性筛，也称为埃拉托斯特尼筛法（Sieve of Eratosthenes），是一种用于求解素数的算法。

双模哈希（Double Hashing）是一种解决哈希冲突的方法，它通过使用两个哈希函数来确定冲突时的下一个可用位置。

Dinic算法是一种用于解决最大流问题的图算法，它基于增广路径的思想。最大流问题是在一个有向图中找到从源点到汇点的最大流量的路径。

第三周训练 1. ABC 269 G - Reversible Cards 2 题意 有 \(N\) 张卡，卡正面反面各有数字 \(A_i\)，\(B_i\)，初始朝向正面 \(\sum_1^n(A_i+B_i)=M\) 你可以任意的反转卡，使得所有朝向上的数字之和为 \(K(K=1,2,...,M)\)，求最小反转次数。如果无法完成，输出 \(-1\) 做法 用 \(cnt\) 数组存下所有反转所能使得初始和变化 \(-K,...,0,...,K\) 的可用次数 然后使用 \(dp\)，将所有可能性在 \(dp\) 数组中应用，使用二进制优化 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354/** * @author: XiaFan * @date: 09-20 18:59 **/#include <bits/stdc++.h>using i64 = long long;int main() { std ...

第二周训练 1. ABC E - Chinese Restaurant (Three-Star Version) 题意 圆盘周围坐着 \(n\) 个人。圆盘上有 \(n\) 个菜，各有编号 \(C_i\)。圆盘可以随意转动，要求最小化 \[ \sum_1^n(dis(i, C_i)) \] 做法 每个菜对于那个人的距离实际上是一段 \(2\) 或者 \(3\) 段函数。将函数相加即可。函数用前缀数组 \(b\)，\(k\) 表示。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061/** * @author: XiaFan * @date: 09-12 20:49 **/#include <bits/stdc++.h>using i64 = long long;int main() { std::ios::sync_with_stdio(false); std::cin.t ...

第一周训练 1. ABC 267 D - Index × A(Not Continuous ver.) 题意 \(B\) 是 \(A\) 长度 \(M\) 的子集 求 \(\sum_1^M(i \times B_i)\) 最大值 做法 DP \[ dp[i][j] = max(dp[i][1 ... j - 1], dp[i - 1][j - 1] + i \times a[i]) \] 代码 123456789101112131415161718192021222324252627282930313233/** * @author: XiaFan * @date: 09-05 19:28 **/#include <bits/stdc++.h>using i64 = long long;int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); i64 n, m; std::cin >> n >> m; std::vector< ...