[置顶]竞赛注意事项

Set中的Comparator定义 在定义Set的Comparator时,一定要小心保证元素不会因为定义被判定为重复,例如: int cnt[maxn]; struct Cmp { bool operator()(int i, int

KMP

介绍 KMP算法能在 $O(n)$ 的时间内,求出一个字符串的每个前缀的最长 border 长度。 利用 border 的性质,也可以在 $O(n)$ 的时间内,求出一个字符串 $t$ 在文本串 $s$ 中出现的所有

Treap

介绍 Treap是一个自平衡的 BST (Binary Search Tree)。与普通BST不同的在于,每个节点会有一个随机的优先级 (priority/rank),在不破坏 BST

COMPFEST13

B. Building an Amusement Park 题意 二维平面上给定 $n$ 个点,求一个最小的圆,使得: $(0,0)$ 在圆上。 圆内(包括圆上)包含至少 $k$ 个点。 输出最小圆半径。 其中,$1 \leq n \leq 10^5, 1 \leq k

SWERC 2021-2022

D. Evolution of Weasels 题意 给定两个字符串 $s,t$,字符串中仅包含 $ABC$ 这三个字母。 我们对于 $s$ 可以在任意位置增加/删除子串 $AA,BB,CC,ABAB,BCB

MAPS 2022

M. Yet Another Divisor Problem 题意 设 $f(n)$ 为正整数 $n$ 的 divisor 个数。 给定 $a, b$,求有多少个满足以下条件的数 $n$? $n$ 是奇数。 $n \in [a,b]$。 $f(f(n^n))$ 是 $n$ 的 divisor。 其中

NAQ 2019

I. Slow Leak 题意 $n$ 个节点的带权无向图中有 $m$ 条边,有一个汽车从 $1$ 出发要到 $n$,汽车有油箱,油箱一开始是满的,最多可以装 $d$ 升油。 每走 $1$ 单位距离就要消

斜率优化DP

介绍 斜率DP一般用于解决类似于如下的问题: $$dp[i] = \min\limits_{j<i} \{ g(j) + f(i, j) + h(i)\}$$ • 注意到上述式子中,当我们固定 $i$,仅有的变量为 $j$,需要最小化的是 $g(j) + f(i,