题集

Preface 参考主要来自《算法竞赛入门经典：训练指南》、OIWiki、CP Algorithms等资源和多方博客、课程，在自己的码风下所著 注： 部分实现可能用到较新语言特性，烦请修改后在较老OJ上使用；原则上提供的代码兼容符合Cpp20及以上标准的编译器 Header #include "bits/stdc++.h" using namespace std; typedef long long ll; typedef double lf; typedef pair<ll, ll> II; typedef vector<ll> vec; const inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(0u); cout.tie(0u); } const lf PI = acos(-1); const lf EPS = 1e-8; const ll INF = 1e18; const ll MOD = 1e9 + 7; const ll DIM = 1e5; int main() { fast_io(); /* El Psy Kongroo */ return 0; } 数学 快速幂 // 注：爆int64考虑__int128或相关intrinsic // MSVC: https://codeforces....

Preface 参考主要来自 https://cp-algorithms.com/algebra/fft.html, https://en.wikipedia.org/wiki/Discrete_Fourier_transform, https://oi.wiki/math/poly/fft/ 为照顾某OJ 本文例程（杂项除外）C++标准仅需11；板子传送门,题目传送门 定义 多项式$A$的$DFT$即为$A$在各单位根$w_{n, k} = w_n^k = e^{\frac{2 k \pi i}{n}}$之值 $$ \begin{align} \text{DFT}(a_0, a_1, \dots, a_{n-1}) &= (y_0, y_1, \dots, y_{n-1}) \newline &= (A(w_{n, 0}), A(w_{n, 1}), \dots, A(w_{n, n-1})) \newline &= (A(w_n^0), A(w_n^1), \dots, A(w_n^{n-1})) \end{align} $$ $IDFT$ ($InverseDFT$) 即从这些值$(y_0, y_1, \dots, y_{n-1})$恢复多项式$A$的系数 $$ \text{IDFT}(y_0, y_1, \dots, y_{n-1}) = (a_0, a_1, \dots, a_{n-1}) $$ 单位根有以下性质 积性 $$ w_n^n = 1 \newline w_n^{\frac{n}{2}} = -1 \newline w_n^k \ne 1, 0 \lt k \lt n $$...

691C. Row GCD You are given two positive integer sequences $a_1, \ldots, a_n$ and $b_1, \ldots, b_m$. For each $j = 1, \ldots, m$ find the greatest common divisor of $a_1 + b_j, \ldots, a_n + b_j$. 引理： $gcd(x,y) = gcd(x,y-x)$ 引理： 可以拓展到 **数组 $gcd$数值上等于数组差分 $gcd$ **；证明显然，略 注意该命题在数组及其差分上取子数组时上并不成立，如 991F. Typora怎么快速加页面内链接… 记$g_{pfx} = gcd(a_2-a_1,a_3-a_2,…a_n-a_{n-1})$ 于本题利用$gcd(a_1+b_1,a_2+b_1,…a_n+b_1) = gcd(a_1+b1,a_2-a_1,a_3-a_2,…a_n-a_{n-1}) = gcd(a_1 + b_1, g_{pfx})$即可 int main() { fast_io(); /* El Psy Kongroo */ ll n,m; cin >> n >> m; vector<ll> a(n); for (ll& x: a) cin >> x; // gcd(a_1+b_1,a_2+b_1,....

​ Preface “标题说是专题其实只是题单”系列（1/1） 树型DP 2070D - Tree Jumps https://codeforces.com/problemset/problem/2070/D Idea: 从深度上至下记录$dp[u]$,$u$为路径结尾点，$\sum dp[i]$即可能数量 双指针 2028C - Alice’s Adventures in Cutting Cake https://codeforces.com/problemset/problem/2028/C Idea: $dp_1[u]$记录选前$u$个可以满足的最大怪物数量，双指针维护；同时，逆序后可易求后缀$dp_2[v]$记录后$v$个可以满足的最大怪物数量，维护手段一致 #include "bits/stdc++.h" using namespace std; typedef long long ll; typedef double lf; typedef pair<ll, ll> II; typedef vector<ll> vec; const inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(0u); cout.tie(0u); } const lf PI = acos(-1); const lf EPS = 1e-8; const ll INF = 1e18; const ll MOD = 998244353; const ll DIM = 1e5; int main() { fast_io(); /* El Psy Kongroo */ ll t; cin >> t; while (t--) { ll n,m,v; cin >> n >> m >> v; vec a(n + 1); for (ll i = 1; i <= n;i++) cin >> a[i]; vec pfx = a; for (ll i = 1; i <= n;i++) pfx[i] += pfx[i - 1]; pfx....

1. Candy Rush TL;DR - 串哈希加速比对 + big hash trick 2023-2024 ACM-ICPC Latin American Regional Programming Contest 官方题解：https://codeforces.com/gym/104736/attachments/download/22730/editorial.pdf 取$C_i$出现频率为向量做前缀和后可发现有效区间频率差为$k \cdot 1_n$；直接比对平摊复杂度为$O(nk\log{n})$,$O(k)$来自于比对本身 而比对可以转换为$O(1)$形式，trick如下： 若 $a,b$ 对应区间有效，一定有：$freq_b = k \cdot 1_n + freq_a$ 而在做前缀和是，可以及时消掉$k \cdot 1_n$项：即为全非$0$时全$-1$ 此时的比对即变成$ hash(freq_b) = hash(freq_a) $ 造一个能$O(1)$更新的$hash$即可让最终复杂度可以变为优秀的$O(nlogn)$ 题解$hash$为$(base^i \cdot c_i)%MOD$ - 避免碰撞可以采用更大int类型或模数，或同code开array于不同base计算后比较 #pragma GCC optimize("O3","unroll-loops","inline") #include "bits/stdc++.h" using namespace std; #define PRED(T,X) [](T const& lhs, T const& rhs) {return X;} typedef long long ll; typedef unsigned long long ull; typedef double lf; typedef long double llf; typedef __int128 i128; typedef unsigned __int128 ui128; typedef pair<ll, ll> II; typedef vector<ll> vec; template<size_t size> using arr = array<ll, size>; const static void fast_io() { ios_base::sync_with_stdio(false); cin....

Treap ATTENTION: 出门左转 https://caterpillow.github.io/byot 谢谢喵 又名笛卡尔树，随机BST；支持$log n$插入，删除，查找及闭包操作(push_up) https://cp-algorithms.com/data_structures/treap.html https://oi.baoshuo.ren/fhq-treap A. std::set 类容器 template<typename T> struct treap { struct node { T key; ll priority; ll l, r; // push_up maintains ll size; }; vector<node> tree; vec free_list; private: void push_up(ll o) { tree[o].size = tree[tree[o].l].size + tree[tree[o].r].size + 1; } II split_by_value(ll o, T const& key) { // 偏序 [<, >=] if (!o) return {0,0}; if (tree[o].key < key) { // 左大右小 auto [ll,rr] = split_by_value(tree[o]....

注: segment_tree 均采用 1-Index 访问； segment_tree::reset(vector&) 中vector为0-Index 区间延迟（Lazy）修改模版 C++ 风格实现 template<typename T> struct segment_tree { struct node { ll l, r; // 区间[l,r] T sum_v; T max_v; // lazy值 T lazy_add; optional<T> lazy_set; ll length() const { return r - l + 1; } ll mid() const { return (l + r) / 2; } }; vector<node> tree; private: ll begin = 1, end = 1; void push_up(ll o) { // 向上传递 ll lc = o * 2, rc = o * 2 + 1; tree[o]....