「网络流 24 题」最长递增子序列-dp+网络最大流
· ✏️ 639 words · ☕ 2 mins read

给定正整数序列 $x_1 \sim x_n$ ,以下递增子序列均为非严格递增。

  1. 计算其最长递增子序列的长度 $s$ 。

  2. 计算从给定的序列中最多可取出多少个长度为 $s$ 的递增子序列。

  3. 如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$ ,则从给定序列中最多可取出多少个长度为 $s$ 的递增子序列。


「网络流 24 题」圆桌聚餐-网络最大流
· ✏️ 627 words · ☕ 2 mins read

假设有来自 $m$ 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 $r_i$ 。会议餐厅共有 $n$ 张餐桌,每张餐桌可容纳 $c_i$ 个代表就餐。

为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。

试设计一个算法,给出满足要求的代表就餐方案。


「网络流 24 题」魔术球-二分图最大匹配
· ✏️ 877 words · ☕ 2 mins read

假设有 $n$ 根柱子,现要按下述规则在这 $n$ 根柱子中依次放入编号为 $1, 2, 3, 4, \cdots$ 的球。

  1. 每次只能在某根柱子的最上面放球。
  2. 在同一根柱子中,任何 $2$ 个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在 $n$ 根柱子上最多能放多少个球。


「网络流 24 题」最小路径覆盖-二分图最大匹配
· ✏️ 754 words · ☕ 2 mins read

给定有向图 $G = (V, E)$。设 $P$ 是 $G$ 的一个简单路(顶点不相交)的集合。如果 $V$ 中每个顶点恰好在 $P$ 的一条路上,则称 $P$ 是 $G$ 的一个路径覆盖。 $P$ 中路径可以从 $V$ 的任何一个顶点开始,长度也是任意的,特别地,可以为 $0$ 。 $G$ 的最小路径覆盖是 $G$ 的所含路径条数最少的路径覆盖。

设计一个有效算法求一个有向无环图 $G$ 的最小路径覆盖。


「网络流 24 题」太空飞行计划-最大权闭合子图
· ✏️ 1040 words · ☕ 3 mins read

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 $E = { E_1, E_2, \cdots, E_m }$ ,和进行这些实验需要使用的全部仪器的集合 $I = { I_1, I_2, \cdots, I_n }$ 。实验 $E_j$ 需要用到的仪器是 $I$ 的子集 $R_j \subseteq I$ 。配置仪器 $I_k$ 的费用为 $c_k$ 美元。实验 $E_j$ 的赞助商已同意为该实验结果支付 $p_j$ 美元。W 教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。


「网络流 24 题」搭配飞行员-二分图最大匹配
· ✏️ 564 words · ☕ 2 mins read

飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机,这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。由于种种原因,例如相互配合的问题,有些驾驶员不能在同一架飞机上飞行,问如何搭配驾驶员才能使出航的飞机最多。

因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行。


「SPOJ26374」QTREE5-LCT
· ✏️ 643 words · ☕ 2 mins read

你被给定一棵 $n$ 个点的树,点从 $1$ 到 $n$ 编号。每个点可能有两种颜色:黑或白。我们定义 $dist(a,b)$ 为点 $a$ 至点 $b$ 路径上的边个数。一开始所有的点都是黑色的。

要求作以下操作:

  • 0 i 将点 $i$ 的颜色反转(黑变白,白变黑)
  • 1 v 询问 $dist(u,v)$ 的最小值。$u$ 点必须为白色( $u$ 与 $v$ 可以相同),显然如果 $v$ 是白点,查询得到的值一定是 $0$ 。

特别地,如果作 1 操作时树上没有白点,输出 $-1$ 。


「SPOJ16580」QTREE7-LCT
· ✏️ 647 words · ☕ 2 mins read

一棵树,每个点初始有个点权和颜色(输入会给你)

  • 0 u : 询问所有 $u,v$ 路径上的最大点权,要满足 $u,v$ 路径上所有点的颜色都相同
  • 1 u : 反转 $u$ 的颜色
  • 2 u w :把 $u$ 的点权改成 $w$

「SPOJ16549」QTREE6-LCT
· ✏️ 698 words · ☕ 2 mins read

给你一棵 $n$ 个点的树,编号 $1$~$n$ 。每个点可以是黑色,可以是白色。初始时所有点都是黑色。有两种操作:

  • 0 u :询问有多少个节点 $v$ 满足路径 $u$ 到 $v$ 上所有节点(包括端点)都拥有相同的颜色
  • 1 u :翻转 $u$ 的颜色

「SPOJ913」QTREE2-LCT
· ✏️ 592 words · ☕ 2 mins read

给定一棵 $n$ 个点的树,边具有边权。要求作以下操作:

  • DIST a b 询问点 $a$ 至点 $b$ 路径上的边权之和

  • KTH a b k 询问点 $a$ 至点 $b$ 有向路径上的第k个点的编号

有多组测试数据,每组数据以 DONE 结尾。


「SPOJ375」QTREE1-LCT
· ✏️ 1045 words · ☕ 3 mins read

给定 $n$ 个点的树,边按输入顺序编号为 $1,2,…,n-1$,要求作以下操作:

  • CHANGE i v :将第 $i$ 条边权值改为 $v$
  • QUERY a b :询问从 $a$ 点到 $b$ 点路径上的最大边权

有多组测试数据,每组数据以 DONE 结尾。


「SPOJ2666」QTREE4-LCT
· ✏️ 1467 words · ☕ 3 mins read

你被给定一棵 $n$ 个点的带边权的树(边权可以为负)。每个点可能有两种颜色:黑或白。我们定义 $dist(a,b)$ 为点 $a$ 至点 $b$ 路径上的边权值之和。一开始所有的点都是白色的。

要求作以下操作:

  • C a 将点a的颜色反转(黑变白,白变黑)

  • A 询问 $dist(a,b)$ 的最大值。$a,b$ 点都必须为白色( $a$ 与 $b$ 可以相同),显然如果树上仍存在白点,查询得到的值一定是个非负数。
    特别地,如果进行 A 操作时树上没有白点,输出 They have disappeared.。


「BJOI2014」大融合-LCT
· ✏️ 662 words · ☕ 2 mins read

小强要在 $N$ 个孤立的星球上建立起一套通信系统。这套通信系统就是连接 $N$ 个点的一个树。 这个树的边是一条一条添加上去的。在某个时刻,一条边的负载就是它所在的当前能够 联通的树上路过它的简单路径的数量。

现在,你的任务就是随着边的添加,动态的回答小强对于某些边的负载的询问。


「CF875E」Delivery Club-二分+贪心
· ✏️ 681 words · ☕ 2 mins read

有两个快递员,分别在 $s_1, s_2(0\le s_1,s_2\le 10^9)$ 位置。现在有 $n(1\le n\le 100000)$ 个任务,需要依次完成,每个任务用一个整数 $x_i$ 表示要将货物送到 $x_i$ 位置,让任何一个快递员到 $x_i$ 都可以。

由于快递员之间需要有对讲机联系,请你设计一种方案使得两个快递员之间的最长距离最短。