Towers
按给定顺序放立方体,每个新立方体只能放到顶部严格大于它的塔上,求最少塔数。
- 规模提示
- n 可达 2×10^5,需要 O(nlogn)。
- 刷题建议
- 把贪心选择翻译成 multiset 的 upper_bound 操作。
优先写交换论证、贪心不变量或单调谓词,然后再选数据结构。
按给定顺序放立方体,每个新立方体只能放到顶部严格大于它的塔上,求最少塔数。
可以增减每根木棍长度,单位变化代价为 1,求把它们变成相同长度的最小总代价。
给申请人期望面积和公寓面积,允许误差 k,最大化成功匹配数。
把正整数数组切成至多 k 个连续段,使最大段和尽可能小。
每个吊舱最多坐两人且总重量不超过 x,求最少吊舱数。
每位客人有入住和离店日,同一房间的下一位必须在前一位离店之后入住,求最少房间并输出分配。
每台机器生产一个产品需要固定时间,求生产至少 t 个产品的最短时间。
每场电影有开始和结束时间,求一个人最多能完整观看多少场互不冲突的电影。
所有任务都要依次完成,任务奖励为截止时间减完成时间,求最大奖励总和。
两个人都要各自读完所有书,同一本书不能同时被两人阅读,求最短总完成时间。
有 k 位观众,每人不能同时看两场电影,求总共最多完整观看多少场。
给定正整数硬币,每枚最多使用一次,求不能组成的最小正整数金额。
每题先用一句话定义状态,并检查它是否保存了未来需要的全部信息。
两名玩家轮流从数组两端取数且都最优,求先手最终能取得的最大总和。
每个项目有开始日、结束日和奖励,选择时间互不重叠的项目使总奖励最大。
每本书有价格和页数,每本最多买一次,在预算内最大化总页数。
使用若干次 1 到 6 的骰子结果组成总和 n,计算有序序列数量。
每种硬币可无限使用,求组成金额 x 所需的最少硬币数,不可组成则输出 -1。
硬币可重复使用,计算组成金额 x 的有序硬币序列数。
硬币可重复使用,计算组成金额 x 的无序组合数。
从 n 开始,每次减去当前数的一个非零十进制数字,求到 0 的最少步数。
在含障碍的方格中,只能向右或向下,从左上走到右下,求路径数量。
允许插入、删除、替换字符,求把字符串 A 变成 B 的最少操作数。
电梯容量为 x,安排所有人上楼,求最少乘坐次数。
每次沿整数网格把一个矩形切成两个矩形,求切成若干正方形的最少切割次数。
每枚硬币最多用一次,输出所有可以组成的正金额。
数组元素范围为 1..m,相邻差至多 1;部分位置已固定,求完整数组数量。
用 1×2 和 2×1 多米诺骨牌铺满 n×m 网格,计算方案数。
求两个整数序列的一个最长公共子序列,并输出该序列。
画出结点和边的含义。涉及流或 2-SAT 时,要写原问题与图模型的双向对应。
有向网络的每条边有容量,求从结点 1 到结点 n 的最大可传输速率。
在无向图中关闭最少街道,使结点 1 与结点 n 不再连通,并输出这些街道。
给定男生与女生之间允许组成的舞伴关系,求最大匹配并输出配对。
求从结点 1 到结点 n 的最多条边不相交有向路径,并输出每条路径。
每个人提出两个关于配料有或没有的文字条件,要求每个人至少满足一个条件。
统计从城市 1 到城市 n、每座城市恰好访问一次的有向路径数量。
先从约束识别参数边界,再接受指数状态、最小费用流或折半枚举。
每条有向路线有容量和单位费用,要求发送恰好 k 个包裹,求最低总费用。
n 名员工和 n 项任务,每个员工执行每项任务有成本,求一一分配的最低总成本并输出方案。
要求恰好 k 条边不相交的源汇路径,最小化所有路径的总边数并输出路径。
统计数组中元素和恰好为 x 的子集数量。
利用唯一简单路径和无环结构,把全局问题拆成子树或数组区间。
在树中选择最多条边,使任意结点最多属于一条被选边。
求树中任意两结点之间的最大距离。
对树中每个结点,求它到最远结点的距离。
对树中每个结点,求它到所有其他结点的距离之和。
给出许多树上路径查询,统计每个结点被多少条查询路径经过。
支持修改结点值,并查询某结点整棵子树的值之和。
把一般困难性与小 n 精确算法放在一起理解。
给一般无向图的所有结点染色,相邻结点颜色不同,要求颜色数最少并输出方案。
先写输入规模与循环不变量,再实现。不要把热身题当作纯语法练习。
对每个 k×k 棋盘,计算放置两匹互不攻击的马的方法数。
把 1..n 分成两个元素和相等的集合,并输出任意一种方案。
只能增加数组元素,求把整个数组变成非递减数组所需的最少增加量。
把苹果分成两组,使两组重量和的绝对差最小。
把 n 个圆盘从柱 1 移到柱 3,每次只能移动一个圆盘且不能大盘压小盘。