「LOJ 138」类欧几里得算法

给出 $T$ 组询问,每组用 $n, a, b, c, k_1, k_2$ 来描述。对于每组询问,请你求出

$$
\sum_{x = 0} ^ {n} x ^ {k_1} {\left \lfloor \frac{ax + b}{c} \right \rfloor} ^ {k_2}
$$

对 $1000000007$ 取模。

查看更多

分享到

「CC MANYLIST」-树状数组 + map

有 $n$ 个集合,初始都为空,要求支持:

  1. 向第 $[l, r]$ 个集合中加入 $x$。
  2. 求第 $i$ 个集合的元素个数。

查看更多

分享到

「CC GEOCHEAT」-凸包

每次向平面中添加一个点 $P$,求当前点集的直径(任意两点最大距离)的平方。
数据随机

查看更多

分享到

「CC PRIMEDST」Prime Distance On Tree-点分治 + FFT

给一棵树,随机选取两个点,求两点间路径距离为质数的概率。

查看更多

分享到

「CC SUMDIS」Sum of distances-分治 + 树状数组

有一张 $n$ 个节点的有向无环图,节点编号为 $1 \sim n$。图的连边情况如下:

  • $\forall 1 \leq i \leq n - 1$,存在一条节点 $i$ 连向节点 $i + 1$ 的边,权值为 $a_i$。
  • $\forall 1 \leq i \leq n - 2$,存在一条节点 $i$ 连向节点 $i + 2$ 的边,权值为 $b_i$。
  • $\forall 1 \leq i \leq n - 3$,存在一条节点 $i$ 连向节点 $i + 3$ 的边,权值为 $c_i$。

除此之外,图中不存在其它的边。
对于一对节点 $s$ 和 $t$ $(s \lt t)$,记 $d(s, t)$ 为从 $s$ 到 $t$ 的最短路径长度。请你求出所有的 $d(s, t)$ 之和,其中 $1 \leq s \lt t \leq n$。

查看更多

分享到

优化 NTT 的性能

优化 NTT 的速度。

查看更多

分享到

「CC DISTNUM2」Easy Queries-区间树

给出一个数列 $a_i$,有 $q$ 个询问 $(l, r, k)$,每次询问区间 $[l, r]$ 中的数从小到大排序且去重后第 $k$ 大的数,强制在线。

查看更多

分享到

「CC JUMP」Jump mission-DP + 动态凸包 + 树状数组

有 $N$ 座山排成一排,每座山都有一个 $1 \sim N$ 的唯一编号。第 $i$ 座山的编号为 $P_i$,高度为 $H_i$。
大厨从第一座山出发,目标是到达第 $N$ 座山。他可以从第 $i$ 座山跳到第 $j$ 座山上($i < j, P_i < P_j$),并花费 $(H_i - H_j) ^ 2$ 的能量,当大厨处于第 $i$ 座山时,他还会花费 $A_i$ 的能量($A_i$ 可以为负)。

求最小能量花费。

查看更多

分享到

「CC SQRGOOD」Simplify the Square Root-杜教筛 + 二分

求第 $n$ 个含有大于 $1$ 的平方因子的数。

查看更多

分享到

SCOI2018 AFO

翻盘失败,OI 再见……

查看更多

分享到

「BZOJ 4519」不同的最小割-GomoryHuTree

给出一个无向连通图,求所有点对的最小割数值中不同的个数。

查看更多

分享到

「CF 757G」Can Bash Save the Day?-可持久化点分树

给出一个 $n$ 个节点的树,和一个长为 $n$ 的排列 $p$,要求支持:

  1. 求 $\sum\limits_{i = l} ^ r \mathrm{dis}(p_i, x)$
  2. $\mathrm{swap}(p_i, p_{i + 1})$

强制在线。

查看更多

分享到

「BZOJ 1143/2718」毕业旅行-Dilworth 定理

一个 $n$ 个点 $m$ 条边的有向图,求最多能选择多少个点,使得任意两点不连通。

查看更多

分享到

「BZOJ 4137」火星商店问题-线段树分治 + 可持久化 Trie

有 $n$ 个商店,每个商店中各有一个特殊物品,特殊物品会一直供应;按照时间顺序(令时间为 $\mathrm{day}$)有 $m$ 个下列事件:

  1. 第 $s$ 个商店在当日新进一种价值为 $v$ 的商品,$\mathrm{day}++$;
  2. 询问第 $L$ 到第 $R$ 的商店购买 $d$ 天内的商品价值 $\mathrm{xor} \ x$ 的最大值。

查看更多

分享到

「BZOJ 4184」shallot-线段树分治 + 线性基

对于时刻 $1 \sim n$,要求支持:

  1. 加入一个数 $a$;
  2. 删除一个已加入的数 $a$。

求每个时刻所有数的最大异或和。

查看更多

分享到

「BZOJ 3533」向量集-线段树 + 凸包 + 三分

维护一个向量集合,在线支持:

  1. 加入向量 $(x, y)$;
  2. 询问 $[l, r]$ 中的向量与向量 $(x, y)$ 的点积最大值。

查看更多

分享到