「SDOI2017」数字表格-数论

Doris 刚刚学习了 fibnacci 数列,用 $f[i]$ 表示数列的第 $i$ 项,那么: $f[0] = 0,f[1] = 1,f[n] = f[n - 1] + fn - 2$ 。

Doris 用老师的超级计算机生成了一个 $n \times m$ 的表格,第 $i$ 行第 $j$ 列的格子中的数是 $f[\gcd(i, j)]$,其中 $\gcd(i, j)$ 表示 $i$ 与 $j$ 的最大公约数。

Doris 的表格中共有 $n \times m$ 个数,她想知道这些数的乘积是多少。

这些数的乘积实在是太大了,所以 Doris 只想知道乘积对 $1000000007$ 取模后的结果。

「SDOI2017」树点涂色-LCT+树链剖分

Bob 有一棵 $n​$ 个点的有根树,其中 $1​$ 号点是根节点。Bob 在每个节点上涂了颜色,并且每个点上的颜色不同。

定义一条路径的权值是,这条路径上的点(包括起点和终点)共有多少种不同的颜色。

Bob 可能会进行这几种操作:

  • 1 x,把点 $x$ 到根节点的路径上的所有的点染上一种没有用过的新颜色;
  • 2 x y,求 $x$ 到 $y$ 的路径的权值;
  • 3 x,在以 $x$ 为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值。

Bob 一共会进行 $m$ 次操作。

「Luogu4449」于神之怒加强版-数学

给定 $n,m,k$ ,计算
$$
\sum_{i=1}^n\sum_{j=1}^m {\gcd(i,j)}^k
$$
对 $1000000007$ 取模的结果

「网络流 24 题」数字梯形-费用流

给定一个由 $n$ 行数字组成的数字梯形如下图所示。梯形的第一行有 $m$ 个数字。从梯形的顶部的 $m$ 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

分别遵守以下规则:

  1. 从梯形的顶至底的 $m$ 条路径互不相交;
  2. 从梯形的顶至底的 $m$ 条路径仅在数字结点处相交;
  3. 从梯形的顶至底的 $m$ 条路径允许在数字结点相交或边相交。

「网络流 24 题」软件补丁-最短路

某公司发现其研制的一个软件中有 $n$ 个错误,随即为该软件发放了一批共 $m$ 个补丁程序。每一个补丁程序都有其特定的适用环境,某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时,往往会加入另一些错误。

换句话说,对于每一个补丁 $i$ ,都有 $2$ 个与之相应的错误集合 $B_1(i)$ 和 $B_2(i)$ ,使得仅当软件包含 $B_1(i)$ 中的所有错误,而不包含 $B_2(i)$ 中的任何错误时,才可以使用补丁 $i$ 。补丁 $i$ 将修复软件中的某些错误 $F_1(i)$ ,而同时加入另一些错误 $F_2(i)$ 。另外,每个补丁都耗费一定的时间。

试设计一个算法,利用公司提供的 $m$ 个补丁程序将原软件修复成一个没有错误的软件,并使修复后的软件耗时最少。

「网络流 24 题」餐巾计划-费用流

一个餐厅在相继的 $n$ 天里,每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾。餐厅可以购买新的餐巾,每块餐巾的费用为 $P$ 分;或者把旧餐巾送到快洗部,洗一块需 $M$ 天,其费用为 $F$ 分;或者送到慢洗部,洗一块需 $n$ 天,其费用为 $S$ 分($S < F$)。

每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 $n$ 天中餐巾使用计划,使总的花费最小。

「随笔」无题

昨天回家的路上,在海淀黄庄路口的西北角上,有一位街头歌手在弹唱着吉他。

「网络流 24 题」方格取数-二分图最大独立集

在一个有 $m \times n$ 个方格的棋盘中,每个方格中有一个正整数。

现要从方格中取数,使任意 $2$ 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。

「网络流 24 题」试题库-网络最大流

假设一个试题库中有 $n$ 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 $m$ 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。

常见最小费用最大流算法学习笔记

众所周知,最小费用最大流向来是一个算法很多的问题,下面总结了几个常用的最小费用最大流算法。

Your browser is out-of-date!

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

×