链接

https://ac.nowcoder.com/acm/contest/9983/B

题意

每个人有 ABCDE 五个等级的预期分数，学校要求得到等级 A 的人不超过 $k$ 个。

给每个人安排一个预期分数，求他们的预期分数最大值和最小值之差最小为多少。

链接

https://loj.ac/p/6121

题意

$n*m$ 的矩阵中，求 $(1,1)$ 走到 $(n,m)$ 的最短路，每秒可上下左右移动一个单位。

相邻两格中间可能有一扇 $g_i$ 类门或者有一堵墙或者无障碍。

有 $s$ 把钥匙， 第 $j$ 把钥匙位于 $(x_j,y_j)$，能打开 $q_j$ 类门。

求左上走到右下的最短时间。

链接

https://loj.ac/p/6008

题意

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

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

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

链接

https://loj.ac/p/6223

题意

给定一个 $N*N$ 的方形网格，设其左上角为起点，坐标为 $(1,1)$，$X$ 轴向右为正，$Y$ 轴向下为正，每个方格边长为 $1$。

一辆汽车从起点出发驶向右下角终点，其坐标为 $(N,N)$。

在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则：

• 汽车只能沿网格边行驶，装满油后能行驶 $K$ 条网格边。出发时汽车已装满油，在起点与终点处不设油库；
• 汽车经过一条网格边时，若其 $X$ 坐标或 $Y$ 坐标减小，则应付费用 $A$，否则免付费用；
• 汽车在行驶过程中遇油库则应加满油并付加油费用 $B$；
• 在需要时可在网格点处增设油库，并付增设油库费用 $C$（不含加油费用 $A$）。

设计一个算法，求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。

链接

https://ac.nowcoder.com/acm/contest/9981/H

题意

求底数为 $a$，层数 $n$ 为的幂塔的个位数 $(1\le a,n\le10^{100000})$。

链接

https://loj.ac/p/6226

题意

在一个 $n*n$ 个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入。

对于给定的 $n*n$ 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。

链接

https://ac.nowcoder.com/acm/contest/9984/G

题意

一个$n*n$ 的初始全零的矩阵，按如下方法填数：

1 2 3

6 5 3

7 8 9

但是这样子太过简单，所以每一次操作会选择一个子矩阵，请你在其子矩阵上进行填数，并在最后输出整个矩阵。

链接

https://ac.nowcoder.com/acm/contest/9984/F

题意

$n$ 个人，$m$ 个物品，每个物品有一个权值，每个物品可以分给 $1$ 或 $2$ 个人。

物品和人是一对一的关系，请问如何分配能使权值和最大？

链接

https://loj.ac/p/6014

题意

$n$ 个开区间，求最长 $k$ 可重区间集。

链接

http://acm.hdu.edu.cn/showproblem.php?pid=4008

题意

树上多次询问：以 $x$ 为树根，$y$ 的 $id$ 最小的儿子节点和子孙节点。