「51NOD 1195」斐波那契数列的循环节-二次剩余

求斐波那契数列 $\text{mod }n$ 的循环节长度。

查看更多

分享到

「BZOJ 2342」双倍回文-回文自动机

求一个回文串,使得这个回文串的一半也是回文串,输出其最长长度。

查看更多

分享到

「BZOJ 2178」圆的面积并-格林公式

给出 $N$ 个圆,求其面积并。

查看更多

分享到

「BZOJ 1010」玩具装箱-斜率优化

P 教授有编号为 $1 \sim N$ 的 $N$ 件玩具,第 $i$ 玩具经过压缩后变成一维长度为 $C_i$ 为了方便整理,P 教授要求在一个一维容器中的玩具编号是连续的。如果将第 $i$ 件玩具到第 $j$ 个玩具放到一个容器中,那么容器的长度将为 $$x = j - i + \sum\limits_{k = i} ^ j C_k$$。如果容器长度为 $x$。其制作费用为 $(x - L) ^ 2$。其 $L$ 是一个常量。P 教授不关心容器的数目,他可以制作出任意长度的容器,甚至超过 $L$。但他希望费用最小。

查看更多

分享到

矩阵树定理学习笔记

矩阵树定理的学习笔记和部分线性代数的知识,记录三道经典题目及变元矩阵树定理。

查看更多

分享到

常系数齐次线性递推

$h_n = a_1h_{n - 1} + a_2h_{n - 2} + \cdots + a_kh_{n - k}$

求其第 $n$ 项。

查看更多

分享到

「CC GRAPHCNT」-支配树

给定一个 $N$ 个点 $M$ 条边的有向图。统计无序对 $(X, Y)$ 的个数,其中 $(X, Y)$ 满足存在一条从 $1$ 到 $X$ 的路径,和一条 $1$ 到 $Y$ 的路径,且两路径除 $1$ 外无公共点。

查看更多

分享到

「BZOJ 2286」「SDOI 2011」消耗战-虚树

一棵 $n$ 个点,边带权的树,$m$ 次询问,每次给出 $k$ 个关键点,求割掉最小代价的边使 $1$ 号点不能到达任何关键点。

查看更多

分享到

「BZOJ 2243」染色-树链剖分

给定一棵有 $n$ 个节点的无根树和 $m$ 个操作,操作有 $2$ 类:

  1. 将节点 $a$ 到节点 $b$ 路径上所有点都染成颜色 $c$
  2. 询问节点 $a$ 到节点 $b$ 路径上的颜色段数量

查看更多

分享到

「BZOJ 3876」支线剧情-上下界费用流

游戏中有 $N$ 个剧情点,由 $1$ 到 $N$ 编号,第 $i$ 个剧情点可以经过不同的支线剧情,前往 $K_i$ 种不同的新的剧情点。当然如果为 $0$,则说明 $i$ 号剧情点是游戏的一个结局了。

开始处在 $1$ 号剧情点。任何一个剧情点都是从 $1$ 号剧情点可达的。从任意剧情点出发,都不能再回到这个剧情点。要想回到之前的剧情点,唯一的方法就是开始新的游戏,回到 $1$ 号剧情点。可以在任何时刻退出游戏并重新开始。求花费最少的时间,看完所有不同的支线剧情。

查看更多

分享到

「Vijos 1891」「BZOJ 3550」Vacation-线性规划

给出一个长度为 $3n$ 的序列,规定连续 $n$ 个数字中不能选择超过 $k$ 个,问最多能取出的数的权值和是多少。

查看更多

分享到

「BZOJ 1059」矩阵游戏-二分图匹配

给出一个 $n * n$ 的黑白方阵,问能否通过交换行或交换列使得主对角线均为黑色。

查看更多

分享到

「BZOJ 4205」卡牌配对-最大流

有 $X, Y$ 两类卡牌,分别有 $n_1, n_2$ 张,每张卡牌有三个属性值:$A, B, C$。
两张卡牌能够配对,当且仅当,存在至多一项属性值使得两张卡牌该项属性值互质,且两张卡牌类别不同。
游戏的目的是最大化匹配上的卡牌组数,当然每张卡牌只能用一次。

查看更多

分享到

「BZOJ 2095」Bridges-混合图欧拉回路

给出一个 $n$ 个点 $m$ 条边的无向图,每个边有一正一反两个权值;现要从点 $1$ 出发,对每条边经过且仅经过一次;求一种方案使经过的最大权值最小。

查看更多

分享到

「BZOJ 2555」SubString-后缀平衡树

给定一个字符串,要求支持两种操作,在当前字符串后加入一个字符串,询问字符串 $s$ 在当前字符串中出现了几次?

查看更多

分享到