「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$ 的平方因子的数。

「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$。

一种最大流数据生成方法

一种构造方法,仅 $532$ 个点,$24115$ 条边的图,使得 Dinic, SAP, ISAP 运行时间均大于 $1s$,
$1198$ 个点,$120796$ 条边运行时间均超过 $1 \mathrm{min}$(当然也可能是我的最大流写得太菜)

「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

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

「BZOJ 5020」在美妙的数学王国中畅游-Link-Cut-Tree

维护一个森林,每个点有一个函数 $f$,要求支持连接两个点,断开两个点,修改某个点的函数,询问路径上函数 $f(x)$ 的和。

「BZOJ 1396/2865」识别子串-后缀数组+单调队列

给定一个字符串 $S$,定义一个位置 $i$ 的识别子串为包含这个位置且在原串只出现一次的字符串,求每个位置的识别子串的长度。

「BZOJ 5104」Fib数列-BSGS+二次剩余

求在 $\bmod 10 ^ 9 + 9$ 的意义下,数字 $C$ 在 $\text{Fib}$ 数列的哪个位置,无解输出 $-1$。

「hihoCoder 1236」Scores-分块+bitset

给 $n$ 个人,每人有 $5$ 科成绩,给出 $q$ 个成绩查询,输出 $5$ 科都比要查询的这 $5$ 科低的数目。

「CodeVs 2819」无尽的毁灭-Voronoi 图

给出 $n$ 个关键点,求出满足以下条件的点的个数及坐标:

  • 距离它最近的关键点有至少 $k$ 个

「模拟测试」小店购物-块状链表

有 $n$ 种物品,个数无限,价值为 $w$,价格为 $p$,要求支持单点修改,询问 $k$ 元能买的最大价值,要求优先购买能买的物品中价值最大的,相同价值选择价格小的。

「模拟测试」纸带-线段树/set/并查集

给出一个序列,每次操作将 $[l, r]$ 染上一种颜色 $i$,问最后有多少种颜色。

「模拟测试」颜色-分块/莫队

给出一个序列,每个位置有同一个颜色,每个颜色有一个价值,要求支持单点修改,查询区间 $[l, r]$ 的权值和,相同颜色只算一次。

「模拟测试」管道-倍增

给出一个无向图,对于每条边,求必须选择这条边的情况下,使得原图连通的最小代价。

「模拟测试」20171030

T2 Game

甲乙两个人轮流那一些物品,甲先手,他可以拿走 $1$ 或 $2$ 个物品。对于后面,若前一个人拿走 $k$ 个物品,当前的人可以拿走 $k$ 或 $k + 1$ 个物品,甲乙的策略都是让自己尽量比别人拿的物品的价值高,求最优策略下,甲最多比乙多拿多少?

「模拟测试」大逃杀

一棵树,经过一条边花费 $c_i$ 的时间,某些点上有障碍,经过额外花费 $t_i$ 时间,每个节点有 $w_i$ 的价值,求 $T$ 秒后获得的最大价值。

「BZOJ 4001」概率论-生成函数

求随机生成的一棵有根二叉树的叶子节点数的期望。

「模拟测试」20171024

T1 建设图

给出一个无向图,求最少添加多少条边使得,无论删掉哪条边任意两点都可以互相到达。

「SuperOJ 2004」姓名匹配-后缀数组+线段树+链表+set

给出 $n$ 个字符串,再给出 $n$ 个字符串,求一一匹配情况下 LCP 的最大长度和。

「UVA 10453」Make Palindrome-区间 DP

给定一个长度为 $n$ 的字符串,你需要在任意位置添加尽量少的字符,使新串是回文串。输出最少添加的字符个数以及新串。

「模拟测试」20171023

T1 Fibonacci

询问一个数能否被分成两个 Fibonacci 数的乘积。

「UVA 10163」Storage Keepers-DP

有 $n$ 个仓库,让 $m$ 个人来看管。一个仓库只能由一个人来看管,一个人可以看管多个仓库。
每个人有一个能力值 $p_i$,如果他看管 $k$ 个仓库,那么所看管的每个仓库的安全值为 $\lfloor \frac {p_i} {k}\rfloor$
如果某个仓库没有人看管,那么它的安全值为 $0$。所有仓库的安全值 $L$ 为所有仓库安全值的最小值
如果雇佣一个人的工资等于他的能力值 $p_i$。
从 $m$ 个人中选择一些人雇佣,问所有仓库的安全值最高是多少,在安全值最高的情况下,求雇佣的最少价钱。

「SuperOJ 1998」「模拟测试」矩阵-DP

有一个 $n \times m$ 的矩阵,请你选出其中 $k$ 个子矩阵,使得这个 $k$ 个子矩阵分值之和最大。注意:选出的 $k$ 个子矩阵不能相互重叠。

「模拟测试」20171019

T1 打牌

给出一些数字,求最多能组成多少个对子 $(x, x)$ 或顺子 $(x, x + 1, x + 2)$。

「UVA 11404」Palindromic Subsequence-DP

给出一个字符串,输出其字典序最小的最长回文子序列。

「UVA 11552」Fewest Flops-DP

给出一个字符串,把它分成 $k$ 块,块内可以任意排序,连续的相同字母算作一段,求最终字符串中的最小段数。

「模拟测试」20171017

T1 购买板凳

有 $n$ 条信息,每条信息包含 $x$ 个人,这 $x$ 个人会在 $A$ 时间到达,$B$ 时间离开,每个人到达后会占用一个板凳,求至少要准备多少个板凳。

「SuperOJ 1979」「模拟测试」拆墙-最小生成树+平面图转对偶图

地主的傻儿子豆豆家很大很大,由很多个区域组成。其中有不少封闭的区域,豆豆觉得很不爽于是决定拆墙,把家打通使得他可以访问到每一个区域(包括家外面无限大的区域)。我们用 $N$ 个端点和 $M$ 条边来描述豆豆的家。第 $i$ 个端点的坐标为($x_i, y_i$),第 $i$ 条边连接端点 $A_i$ 和 $B_i$,拆除所需要花费的力气为 $C_i$ 。保证所有边只在端点相交,也就是这是一个平面图,也没有重边和自环。

现在豆豆想知道他最少一共需要花费多少力气?

「BZOJ 4105」平方运算-线段树

现有一个长度为 $n$ 的序列 ${x_1, x_2, \cdots, x_n}$,要求支持两种操作:

  1. 0 l r 表示将 $i \in [l, r], x_i \leftarrow x_i^2 \bmod p$
  2. 1 l r 询问 $\sum\limits_{i = l} ^ r x_i$
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×