题面 题目传送 题目描述 有 $ n $ 件工作要分配给 $ n $ 个人做。第 $ i $ 个人做第 $ j $ 件工作产生的效益为 $ c_{ij} $。试设计一个将 $ n $ 件工作分配给 $ n $ 个人做的分配方案，使产生的总效益最大。 输入格式 第 $ 1 $ 行有 $ 1 $ 个正整数 $ n $，表示有 $ n $ 件工作要分配给…

题面 题目传送 题目描述 $G$ 公司有 $n$ 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 $n$ 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。 输入格式 第 $1$ 行中有 $1$个正整数 $n$，表示有 $n$ 个仓库。 第 $2$ 行中有 $n$ 个正整数，表示 $n$ 个仓库的库存量。…

题面 洛谷 P2763 & LOJ #6006 题目描述 假设一个试题库中有 $ n $ 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 $ m $ 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。 输入格式 第 $ 1 $ 行有 $ 2 $ 个正整数 $ k $ 和 $ n $。$…

题面 题目链接 这是一道模板题。 给出一个  的零矩阵 ，你需要完成如下操作： 1 x y k：表示元素  自增 ； 2 a b c d：表示询问左上角为 ，右下角为  的子矩阵内所有数的和。 思路 一维树状数组的扩展 我们知道，一维树状数组可以求一段区间的和，将其扩展到二维，对于一个矩阵，每一层可以看做一个数，实际上是树状数组，每次求到每一层时求…

题面 洛谷 P2756 飞行员配对方案问题 LOJ #6000.「网络流 24 题」搭配飞行员 因为 LOJ 上的版本比较简洁，所以就放这个版本的题面了。 飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员，需一个正驾驶员（英国）和一个副驾驶员（外籍）。由于种种原因，例如相互配合的问题，有些驾驶员不能在同一架飞机上飞…

题面 题目传送 给你一个长度为 $n$ 的整数序列 ${a_1,a_2,\dots,a_n}$ ，要求从中找出一段连续的长度不超过 $m$ 的子序列，使得这个序列的和最大。 思路 单调队列优化 DP 模板题。 设 $t[i]$ 为 $s[1]+s[2]+\dots+s[i]$，则有状态转移方程 $f[i]=t[i]-min(t[i-1],t[i-2…

题面 题目传送门 在 $N*N$ 的棋盘上放 $K$ 个国王，国王可攻击相邻的 $8$ 个格子，求使它们无法互相攻击的方案总数。 思路 状压 DP 的模板，以前 DP 技能一直没怎么点，现在数据结构什么的都差不多了，开始补 DP。 预处理 对于每一行来说，我们可以用二进制来表示当前这一行的放置状态。然后再压成十进制。 然后预处理出对于一行来说的所有…

题面 题目传送门 展开题面 题目描述 OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道…

题面 题目传送门 展开题面 题目描述 凡凡开了一间宠物收养场。收养场提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。 每个领养者都希望领养到自己满意的宠物，凡凡根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养场的宠物一个特点值。这样他就能够很…

题面 题目传送门 Sherlock 有了一个新女友（这太不像他了！）。情人节到了，他想送给女友一些珠宝当做礼物。 他买了 $n$ 件珠宝。第 $i$ 件的价值是 $i+1$ 。那就是说，珠宝的价值分别为 $2,3,4,.. ,n+1$ 。 Watson 挑战 Sherlock，让他给这些珠宝染色，使得一件珠宝的价格是另一件的质因子时，两件珠宝的颜色…