「网络流24题」最长递增子序列 - 网络流
给定正整数序列 ,以下递增子序列均为非严格递增。
- 计算其最长递增子序列的长度 。
- 计算从给定的序列中最多可取出多少个长度为 的递增子序列。
- 如果允许在取出的序列中多次使用 和 ,则从给定序列中最多可取出多少个长度为 的递增子序列。
给定正整数序列 ,以下递增子序列均为非严格递增。
给定有向图 。设 是 的一个简单路(顶点不相交)的集合。如果 中每个顶点恰好在 的一条路上,则称 是 的一个路径覆盖。 中路径可以从 的任何一个顶点开始,长度也是任意的,特别地,可以为 。 的最小路径覆盖是 的所含路径条数最少的路径覆盖。
设计一个有效算法求一个有向无环图 的最小路径覆盖。
W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 ,和进行这些实验需要使用的全部仪器的集合 。实验 需要用到的仪器是 的子集 。
配置仪器 的费用为 美元。实验 的赞助商已同意为该实验结果支付 美元。W 教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。
给定若干个任务 ,表示该任务从第 秒运行到第 秒,它的价值为 ,每次询问给定一个 并由你计算一个 ,查询第 秒时价值最小的 个任务的价值之和,如果第 秒时运行的任务不足 个,则输出此时所有任务的价值和。
给定两个字符串 和 ,求两个字符串的公共子序列个数。
给定一个序列,以及若干次反转区间的操作,要求输出经过若干次反转操作之后的序列。
Kiana最近沉迷于一款神奇的游戏无法自拔。
简单来说,这款游戏是在一个平面上进行的。
有一架弹弓位于 处,每次Kiana可以用它向第一象限发射一只小鸟,小鸟们的飞行轨迹均为形如 的曲线,其中 , 是Kiana指定的参数,且必须满足 。
当小鸟落回地面(即 轴)时,它就会瞬间消失。
在游戏的某个关卡里,平面的第一象限中有 只绿色的猪,其中第 只猪所在的坐标为 。
如果某只小鸟的飞行轨迹经过了,那么第 只猪就会被消灭掉,同时小鸟将会沿着原先的轨迹继续飞行;
如果一只小鸟的飞行轨迹没有经过,那么这只小鸟飞行的全过程就不会对第 只猪产生任何影响。
例如,若两只猪分别位于 和 ,Kiana可以选择发射一只飞行轨迹为 的小鸟,这样两只猪就会被这只小鸟一起消灭。
而这个游戏的目的,就是通过发射小鸟消灭所有的猪。
这款神奇游戏的每个关卡对来说都很难,所以Kiana还输入了一些神秘的指令,使得自己能更轻松地完成这个游戏。这些指令将在「输入格式」中详述。
假设这款游戏一共有 个关卡,现在Kiana想知道,对于每一个关卡,至少需要发射多少只小鸟才能消灭所有的猪。由于她不会算,所以希望由你告诉她。
本题中,我们将用符号 表示对 向下取整,例如:。
蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有 只蚯蚓( 为正整数)。每只蚯蚓拥有长度,我们设第 只蚯蚓的长度为 (),并保证所有的长度都是非负整数(即:可能存在长度为 的蚯蚓)。
每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半。神刀手切开蚯蚓的位置由常数 (是满足 的有理数)决定,设这只蚯蚓长度为 ,神刀手会将其切成两只长度分别为 和 的蚯蚓。特殊地,如果这两个数的其中一个等于 ,则这个长度为 的蚯蚓也会被保留。此外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加 (是一个非负整常数)。
蛐蛐国王知道这样不是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物,但是救兵还需要 秒才能到来 ……( 为非负整数)
蛐蛐国王希望知道这 秒内的战况。具体来说,他希望知道:
蛐蛐国王当然知道怎么做啦!但是他想考考你 ……
组合数表示的是从 个物品中选出 个物品的方案数。举个例子,从 三个物品中选择两个物品可以有 ,, 这三种选择方法。
根据组合数的定义,我们可以给出计算组合数的一般公式:
其中 。
小葱想知道如果给定 , 和 ,对于所有的 , 有多少对 满足是 的倍数。