[置顶]竞赛注意事项/通用模版 2022-09-19 注意事项 Set中的Comparator定义 在定义Set的Comparator时,一定要小心保证元素不会因为定义被判定为重复,例如: • 注意这里 Read more...
线段树优化建图 2023-09-04 算法 介绍 线段树优化建图用于解决图中边数过多,不能直接建的问题。 直接看例题: 例1 CF786B. Legacy 题意 给定 $n$ 个点的有向带权图,初始状态下图中没有边。给定 $q$ 个操作 Read more...
笛卡尔树 2023-09-01 算法 定义 笛卡尔树是一种二叉树,每一个结点由一个键值二元组 $(k,v)$ 构成。 性质 $k$ 满足 BST 的性质 $v$ 满足 min-heap 的性质。 如果笛卡尔树的 $k,v$ 值确定,且 $k$ 互不相同,$v$ 互 Read more...
整体二分 2023-07-15 算法 介绍 整体二分是一种思想,用于同时二分多组询问,在题目满足以下条件时可以用: 有多组询问,每组询问可以通过二分解决。 询问离线。 询问之间互相独立。 Read more...
线性筛 2023-06-04 介绍 线性筛不仅能用 $O(n)$ 求出每一个数是否为质数,它还能求出每一个数的因数数量,因数和,甚至更加general的除数函数,莫比乌斯函数等等。 总结来 Read more...
NAC2023 Training Camp Day2 2023-05-27 解题报告 A. Fair Bandwidth Sharing 题意 给定 $n$ 个区间 $[l_i, r_i]$,并且给定 $n$ 个权值 $d_i$,和一个常数 $t$。 定义 $y_i = t \frac{d_i}{\sum\limits_{j=1}^n d_j}$。 求一组 $x_i$,使得满足以下所 Read more...
随机化 2023-05-27 构造题的应用 在 $n$ 较小时,确定一个随机数的seed mt19937 rng(SOME_SEED);,如果在本地成功跑出来结果,就直接把这个seed交上去,这样 Read more...
CodeSprint UCLA 2023 2023-05-22 解题报告 L. Blooper Game 题意 给定 $n$ 个概率 $S_1, S_2, …, S_n$,同时给定一个实数 $P \in (0,1)$。 现在有 $L$ 次操作机会,每次操作可以选择一个 $S_i$,让 $S_i = (S_i) Read more...
Universal Cup 15 (Hangzhou) 2023-05-18 解题报告 L. Barkley 题意 给定长度为 $n$ 的数组 $a_i$,有 $q$ 个询问,每次询问为 $l~r~k$ 回答在 $[l,r]$ 这个区间内,可以去掉至多 $k$ 个数后,得到的最大 gcd 是多少? 其中,$n \leq 10^5, q Read more...
线段树分治 2023-05-17 算法 介绍 线段树分治一般用于处理一些 “只存在/不存在 权值为 $w$“,或者 ”某个特定时间点” 对应状态的问题。 原理是在线段树上进行 DFS,进入 DFS 时加入 Read more...