「TJOI2015」弦论-后缀数组

后缀自动机的做法相信大家都会,这里记录一下后缀数组做法。

查看更多

分享到

「ARC 079D」Decrease (Contestant ver.)-构造

给定一个数 $k$,要求构造一个非负整数序列,使得操作 $k$ 次后,最大数 $\leq n - 1$,每次操作选序列中最大值,将其 $-n$,其余数 $+1$。

查看更多

分享到

「ARC 080E」Young Maids-线段树 + 堆

给出一个 $1 \sim n$ 的排列,$p_0, p_2, \cdots, p_{n - 1}$,每次从中选相邻两数删去,加入 $q$ 的前面,求最小字典序的 $q$。

查看更多

分享到

「BZOJ 3589」动态树-树链剖分 + 容斥

维护一棵树,子树修改,询问 $k$ 条链并的权值和。

链接

BZOJ 3589

查看更多

分享到

「模拟测试」20170822

T1 连环

给定一个长度为 $n$ 的字符串 $S$ 和一个长度为 $m$ 的字符串 $T$,现在有 $k$ 个询问,每个询问是给出两个整数 $l, r$,询问任选一对 $(i, j)$ 满足 $0 \leq i \leq l, n \geq j \geq r$,删去 $S$ 的 $[i + 1, j - 1]$ 这个区间的子串,剩下两块拼在一起,$T$ 在其中匹配数的期望。

查看更多

分享到

「ARC 071E」TrBBnsformBBtion

给定两个由 AB 组成的字符串 $S, T$,其中字符 A 可以变为 BBB 可以变为 AAAAABBB 可以被删掉,询问 $S$ 中的一个给定子串能否变为 $T$ 中的一个给定子串。

查看更多

分享到

「ARC 070E」NarrowRectangles-斜率优化

二维坐标系中有 $n$ 个矩形,第 $i$ 个矩形在水平方向上覆盖 $[l_i, r_i]$,在竖直方向上覆盖 $[i - 1, i]$,我们要水平移动这些矩形使得它们全部连通,水平移动的花费是移动的距离,求最小费用。

查看更多

分享到

「Hexo」gitalk 评论

各种评论服务都挂了后,感觉还是 github 最靠谱,Gitalk 是一个基于 Github Issue 和 Preact 开发的评论插件。
这里记录 Hexo 使用 gitalk 作为评论插件的修改方法(支持 markdown + mathjax)。

查看更多

分享到

「BZOJ 4176」Lucas的数论-莫比乌斯反演+杜教筛


$$\sum_{i = 1} ^ n\sum_{j = 1} ^ nd(ij)$$

查看更多

分享到

「BZOJ 3028」食物-生成函数

链接

BZOJ 3028

查看更多

分享到

「POJ 3734」Blocks-生成函数

链接

POJ 3734

题意

有一排砖,数量为 $n$,有红蓝绿黄 $4$ 种颜色,其中染成红和绿颜色的砖块的数量必须为偶数个,求可有多少种染色方案。

查看更多

分享到

「NOI 2016」循环之美-莫比乌斯反演 + 杜教筛

链接

UOJ 221
BZOJ 4652
LOJ 2085

查看更多

分享到

「补档计划」数论

关于数论的总结和专题练习….

查看更多

分享到

「BZOJ 2813」奇妙的 Fibonacci-线性筛

Fibonacci 数列是这样一个数列:
$F_1 = 1, F_2 = 2, F_3 = 3 \cdots$ $F_i = F_{i - 1} + F_{i - 2}$ (当 $i \geq 3$)
pty 忽然对这个古老的数列产生了浓厚的兴趣,他想知道:对于某一个 Fibonacci 数 $F_i$,有多少个 $F_j$ 能够整除 $F_i$ ($i$ 可以等于 $j$),他还想知道所有 $j$ 的平方之和是多少。

查看更多

分享到

「CF 150E」Freezing with Style 点分治

给定一颗由 $n$ 个节点 $n - 1$ 条边构成的树,在所有路径长度不超过 $R$ 且不低于 $L$ 的路径中,对于任意一条路径,将其每条边权值从大到小排序,取第 $\lfloor \frac {len} {2} \rfloor + 1$ 个权值,求使此权值最大时,从哪个节点出发,到哪个节点结束。

查看更多

分享到