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)$ 的点积最大值。

查看更多

分享到

「BZOJ 4311」向量-线段树分治 + 凸包

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

  1. 插入一个向量 $(x, y)$;
  2. 删除插入的第 $i$ 个向量;
  3. 查询当前集合与 $(x, y)$ 点积的最大值是多少,如果当前是空集输出 $0$。

查看更多

分享到

「LOJ 6053」简单的函数-ExtendedEratosthenesSieve

一个函数 $f(x)$,它满足:

  1. $f(1) = 1$。
  2. $f(p ^ c) = p \oplus c$($p$ 为质数,$\oplus$ 表示异或)。
  3. $f(ab) = f(a)f(b)$($a$ 与 $b$ 互质)。

求 $\sum\limits_{i = 1} ^ n f(i) \bmod 1000000007$。

查看更多

分享到

「SuperOJ 1297」数学题-ExtendedEratosthenesSieve

定义欧拉函数的变种
$$\phi(n, d) = \prod_{k = 1} ^ m (p_k ^ {e_k} + d)$$
特别的,$\phi(1, d) = 1$,求
$$\sum_{i = 1} ^ n \phi(i, d) \pmod {10 ^ 9 + 7}$$

查看更多

分享到

「BZOJ 4916」神犇和蒟蒻-ExtendedEratosthenesSieve

求 $A = \sum\limits_{i = 1} ^ n \mu(i ^ 2), B = \sum\limits_{i = 1} ^ n \varphi(i ^ 2)$

查看更多

分享到

「SPOJ DIVCNT[2/3/k]」-ExtendedEratosthenesSieve

求 $\sum\limits_{i = 1} ^ n \sigma_{0}(i ^ k)$,$n, k \leq 10 ^ {10}, T \leq 10000$。

查看更多

分享到

Extended Eratosthenes Sieve

扩展埃拉托色尼筛法可以在大约 $O(n ^ {\frac {2} {3}})$ (这里以实际运行效果估计,实际复杂度据说和洲阁筛一样)求出一般积性函数的前缀和,消耗 $O(\sqrt{n})$ 的空间

查看更多

分享到

「模拟测试」背单词-AC 自动机+二进制分组

要求支持 $2$ 种操作:

  1. 向字典中加入一个串 $s$,其权值为 $v$(若重复算作多个串)。
  2. 询问一个串 $t$,其中在字典中出现过的单词的权值和(相同单词应被多次计算)。

强制在线。

查看更多

分享到

三模数 NTT 与拆系数 FFT

三模数 NTT 与拆系数 FFT

两个长度为 $10 ^ 5$ 级别的多项式相乘,对 $10 ^ 9$ 级别任意模数取模。

查看更多

分享到

「BZOJ 3510」首都-Link-Cut-Tree

维护一片森林,要求支持加边,询问重心,询问所有树重心编号的异或和。

查看更多

分享到