「模拟测试」背单词-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 建设图

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

查看更多

分享到